·1
`j
`I
`I
`I
`I
`I
`I
`I~ I
`It I
`•
`I
`I
`l'
`I
`
`I ,
`
`I
`
`t
`I
`
`!
`I
`
`I
`
`I
`
`I
`
`I
`. I
`I
`I
`I
`I
`'I
`, , I
`
`I
`I
`
`I
`I
`i
`!
`I
`
`· I
`. I
`
`· I
`• I
`I I
`I I
`I I
`
`C. Britton Rorabaugh
`
`ERROR
`CODING
`COOKBOOK
`
`Practical C/C++
`Routines and Recipes
`for Error Detection
`and Correction
`
`DISK
`Inc luded
`
`1
`'
`
`Page 1 of 88
`
`SAMSUNG EXHIBIT 1009
`
`

`

`BLDSC
`
`IMPORTANT
`
`NCB
`RESTRICTED
`STOCK
`NOT FOR HOME
`READING
`
`This item must be consulted on
`library premises only
`
`NOT FOR LONG LOAN
`
`PLEASE DO NOT USE
`VAN SCHEME
`FOR RETURN
`
`Please
`DO NOT REMOVE
`This wrapper
`
`Page 2 of 88
`
`

`

`I
`
`. Error Coding
`Cookbook
`Practical CIC++
`Routines and Recipes for
`Error Detection and Correction
`C. Britton Rorabaugh
`
`•
`
`-~ ,
`"' . .
`
`• \
`
`f'•
`
`- , ..
`. ... _
`.
`'\,,,.,,, ..... ~... -
`D,vf'\·v"
`• •
`l l FEB 1997
`
`•!
`
`~
`
`i
`
`.,;_
`
`•
`
`-
`
`#
`
`._
`
`...
`... -•· .,, ·; I
`l :, ~1'\" &..l \.- .
`
`L - - - - --
`
`McGraw-HIii
`N.w York S.n Francisco Washington, O.C. Auckland Bogota
`Caracaa Lisbon Lornton Madrid M(cid:127) xlco City M.ilan
`Montreal New Delhi S.n Juan Singapore
`Sydn.y Tokyo Toronto
`
`. -
`
`•
`
`I
`•
`'
`
`-
`,
`
`_j
`
`Page 3 of 88
`
`

`

`McGraw-Hill
`I /)ms:011 o/ nic,\,f.Gru11,'Hill(ornpa,1~
`
`i2
`
`©199fi by The McGraw-Hill Companies.
`
`Printed in thP United States of America. All rights reserved. The publisher takes no
`responsibility for the use of any matenals or lllPthods described m this l>ook, nor for
`the products thereof.
`
`he
`
`1 2 :3 -l 5 6 7 8 9 DOC/OOC 9 0 0 9 8 'i fi
`
`Produ<:t or brru1d names used in this book may be trade names or trademarks. Where WP. believe
`that thnt> may be proprietary claims to such trade names or trademarks, the name tw been
`used with an irnha.l capital or it has b4"t•n capitalized in the style used by the name claimant
`Reg,ardli>Ss of th<.> capitalization used, all t.uch names have been used in an editorial manner
`without any mtent to conwy endorsement of or other affiliation with the name daunant Neither
`the author nor the puhli«her intends to Pxpress any judgment as to the validity or legal status of
`any such proprietary claims
`
`IJbrary of Congress Cata.loging-in-Pnblicatlon Data
`Rorabaugh, C Bntton.
`Error coding cookbook: practical CIC++ routines and recipes for error
`detection and correction/ by C. Britton Rorabaugh.
`p.
`cm.
`Includes index.
`ISBN 0-07-911720 I (h)
`1 C (Computer program language) 2. Debugging in computer
`science. I. Title.
`QA76.73.C15R67 1995
`005. 7'2-dc20
`
`95-22892
`CIP
`
`McGraw Hill books are available at special quantity discoW1ts to w.e as premiums and
`sales promotions, or for use in corporate training prograrns. For more infonnation ,
`please writf' to the Director of Special Sales, McGraw-Hill, 11 West 19th Street, New
`York, NY 10011 Or contact your local bookstore
`
`Acquisitions edit.or: Steve Chapman
`Editorial tf'anr Lori Flal1erty, Executive Editor
`Andrew Yoder, Book Editor
`Produrtion lt>am: Kathenne G. Brown, Director
`Lisa M. Mellott. Coding
`Wanda S. Ditch, Desktop Operator
`Joann Woy, Indexer
`Design team: Jaclyn J. Boone, Designer
`Katherine Lukaszewicz, Associate Designer
`
`9117201
`EL3
`
`Page 4 of 88
`
`

`

`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`Contents
`
`Introduction xi
`
`1 Strategic Issues 1
`1.1 Why Code? 1
`1.2 Data Errors 1
`1.2.1 Binary Symmetric Channel 1
`1.2.2 Burst Channel 1
`1.2.3 Binary Erasure Channel 2
`1.3 Software Notes 2
`
`2 Mathematical Tools for Coding 5
`2.1 Modulo Anthmetic 5
`2.1.1 Modulo-2 Anthmetic 6
`2.2 Finite Fields 9
`2.2.1 Groups 9
`2.2.2 Fields 11
`2.3 Introduction to Polynomials 13
`2.4 Extension Fields 16
`2.5 Binary Extension Fields: Manual Construction 20
`2.5. i Constructing the Field 22
`2.5.2 Representing the Field Elements 24
`2.6 Computer Methods tor Galois Fields 26
`2 6.1 Representing Field Elements 27
`2.7 More About Polynomials 30
`2.8 Cyclotomic Cosets 33
`2.9 Finding Minimal Polynomials 36
`
`3 Block and Cyclic Codes 41
`3.1 Introduction 41
`3.2 Linear Block Codes 44
`
`Page 5 of 88
`
`

`

`3.2.1 Encoding for Linear Block Codes 44
`3.2.2 Constructing the Generator Matrix 47
`3.2.3 Parity-Check Matrix 47
`3.3 Cyclic Codes 49
`3.4 Manual Encoding Methods for Cyclic Codes 51
`3.5 Modifications to Cyclic Codes 52
`3.5.1 Extended Codes 53
`3.5.2 Punctured Codes 54
`3.5.3 Expurgated Codes 54
`3.5.4 Augmented Codes 55
`3.5.5 Shortened Codes 56
`3.5.6 Lengthened Codes 56
`3.6 Hamming Codes 56
`3.6.1 Shortened Hamming Codes 58
`
`4 BCH and Reed-Solomon Codes 61
`4.1-BCH Codes 61
`4.1.1 Genesis of the Codes 62
`4.1.2 Types of BCH Codes 63
`4.1.3 Critical Features 63
`4.1.4 Constructing the Generator Polynomial 68
`4.1.5 Algorithmic Approach 71
`4.1.6 Computer Approach 73
`4.2 Nonbinary BCH Codes 79
`4.3 Reed-Solomon Codes 82
`
`5 Encoders and Decoders 85
`5.1 Division Method tor Encoding Cyclic Codes 85
`5.1.1 Hardware Implementation 85
`5.1 .2 Software Implementation 88
`5.2 Standard Array 89
`5.2.1 Hazards in Standard Array Decoding 92
`5.3 Syndromes for BCH Codes 93
`5.4 Peterson-Berlekamp Method 97
`5.5 Error Location 102
`
`6 Convolutional Codes 105
`6.1 Canonical Example 105
`6.1 .1 Convolutional Encoder Viewed as a Moore Machine 106
`
`Page 6 of 88
`
`

`

`6.1.2 Convolut,onal Encoder Viewed as a Mealy Machine 106
`6.1.3 Moore Machines vs. Mealy Machines 109
`6.1.4 Notation and Terminology 112
`6.2 Tree Representation of a Convolutional Encoder 116
`6.3 Trellis Representation of a Convolutional Encoder 119
`6.4 Distance Measures 123
`
`7 Viterbi Decoding 127
`7 .1 Introduction to Viterbi Decoding 127
`7.2 Viterbi Decoding Failures 141
`7.2.1 Minimum Free Distance 146
`7.2.2 Weight Distribution 147
`7.2.3 Information Sequence Weight 147
`7.3 Vrterb1 Decoding with Soft Decisions 147
`7.4 Practical Issues 152
`7 4.1 Decoding Depth 153
`
`8 Sequential Decoding 155
`8 1 Stack Decoding Algonthm 155
`8.1.1 Fano Metric 161
`8.2 Software for Stack Decoding 168
`8.2.1 Implementing the Stack 171
`8.2.2 Received Symbol Buffering 177
`8.2.3 State Table 179
`8.3 Fano Decoding Algorithm 180
`
`Appendices
`A Minimal Polynomials of
`Elements in GF(2m) for Chapter 2 191
`B Stack Tables for Example 8.1 197
`C Stack Tables for Example 8.2 207
`D Stack Tables for Example 8.3 215
`E Software 227
`Index 245
`About the Author 251
`Disk Warranty 260
`
`Page 7 of 88
`
`

`

`Introduction
`
`Error-correction coding has traditionally been one of the most
`mathematically challenging of the various specialized disciplines
`that come together to make modern data communication and data
`storage possible. A good bit of the difficulty no doubt stems from
`the use of a type of arithmetic that is different from the usual
`"standard" arithmetic that we all use every day. This book is an at(cid:173)
`tempt to change all that. After Chapter 1 provides a brief intro(cid:173)
`duction to the strategic issues involved in error correction coding,
`Chapter 2 demystifies those elements of abstract algebra and Ga(cid:173)
`lois field arithmetic that are essential for successful implementa(cid:173)
`tion of encoders and decoders. Some basic software modules for
`generating Galois fields and performing arithmetic within these
`fields are also developed in Chapter 2. Chapter 3 uses techniques
`from Chapter 2 to introduce the basics of block and cyclic codes.
`Chapter 4 covers the specific details of BCH codes and Reed(cid:173)
`Solomon codes, which together account for perhaps 80% of all
`block codes used in practical applications. In Chapter 5, the details
`of encoders and decoders for block and cyclic codes are intro(cid:173)
`duced and particularly efficient decoding techniques for BCH
`codes are covered in some detail. The major emphasis is on soft(cid:173)
`ware implementations rather than hardware implementations, but
`digital hardware designers will be readily able to "port" the various
`software constructions into the corresponding hardware construc(cid:173)
`tions. In addition to Block and Cyclic codes, there is another large
`class of codes called convolutional codes, which are also widely
`used in practical applications. Chapter 6 introduces convolutional
`codes and the notation and terminology commonly associated
`with them. Viterbi decoding of convolutional codes is covered in
`Chapter 7. This coverage includes the development of software
`modules for performing the Viterbi algorithm. Although it enjoys
`widespread use, Viterbi decoding does have some limitations. Be(cid:173)
`cause of these limitations, alternative decoding techniques, such
`as stack decoding or Farro decoding, must often be used. These al-
`
`Introduction
`
`Page 8 of 88
`
`

`

`ternative techniques, along with software for performing them, are
`covered in Chapter 8.
`
`The subject of error correction coding is vast, and this book covers
`only a small part of it. However, the codes and techniques covered
`are the most widely used in practical applications. This, after all,
`accomplishes this book's original motive, which is to place power(cid:173)
`ful coding techniques as well as the knowledge needed to imple(cid:173)
`ment these techniques in the hands of individuals who need to use
`error-correction coding-even though these individuals are not
`coding experts.
`
`i\lii1<LJ!l~iiMJ
`
`Introduction
`
`ii.IE: iW
`
`l.iiet~~-JEa,;;;liiiJ..;}:!ll!I, !.:
`
`Page 9 of 88
`
`

`

`Strategic Issues
`
`1.1 Why Code?
`Coding is performed for several different reasons. Cryptographic
`codes are used to protect information from unauthorized recep(cid:173)
`tion and to authenticate that a message was in fact sent by the
`party listed in the message as the originator. Data compression
`codes are used to reduce the amount of bandwidth needed to
`transmit data or to reduce the amount of memory needed to store
`a message. Error control codes, which are the subject of this
`book, are used to detect and/or correct errors that might be intro(cid:173)
`duced into digital data when it is transmitted or stored.
`
`1.2 Data Errors
`There are several different mechanisms by which errors are intro(cid:173)
`duced into a data signal. The strategy for coding the signal to protect
`it against errors is often tailored to the particular error mechanism
`known or assumed to be operating in application of interest.
`
`1.2.1 Binary Symmetric Channel
`As shown in Fig. 1-1, in a binary symmetric channel (BSC), the
`probability of a 1 to O error and the probability of a O to 1 error are
`equal. This mechanism is most often assumed to be the dominant
`error-producing mechanism for errors produced by additive Gauss(cid:173)
`ian noise. If the probability of error is independent from bit-to-bit,
`the BSC can be further characterized as being a discrete memory(cid:173)
`less channel (DMC) .
`
`1.2.2 Burst Channel
`In many situations, the noise in a channel will vary over time, be(cid:173)
`ing weak during some situations and strong during other intervals.
`Errors will be more likely to occur in bursts that coincide with in(cid:173)
`tervals of strong noise. Such a channel is referred to as a burst
`channel, or a channel with memory.
`
`""Qik""ilil-kC""-'""""' ---·•m-~!lidl ... ~ Z J@£.i:&tiJ.:l:J
`
`Data Errors
`I £.1""""'· ... _ ... ,.,,...,...,HBHm--w .W .W .~
`ifflllilli!IJB'Ulh:.T.W.:.oo:z;;:;;;J~.JJi&SIZWXJi!W4J~~~l,;W! li!!iE ~ it tit£ ~ ...
`
`Page 10 of 88
`
`

`

`1-p
`(cid:127) 1-1 Transition probabilities in the binary
`symmetric channel.
`
`1.2.3 Binary Erasure Channel
`Consider a baseband pulse transmission system in which a pulse of
`-1 volt is transmitted for a O and a pulse of + 1 volt is transmitted
`for a 1. At the receiver, a pulse voltage less than -0. 7 volt is inter(cid:173)
`preted as a 0. A pulse voltage greater than +0.7 is interpreted as a
`1. The voltage range between-0.7 and +0.7 is considered as a "no(cid:173)
`man's land" or deadband. Pulse voltages received in this range are
`deemed "too close to call" and are not interpreted as either O or 1.
`Such decisions not to decide is called erasures, and a channel that
`produces erasures is called a binary erasure channel (BEG).
`The probability of a transmitted O being so corrupted that the re(cid:173)
`ceived voltage exceeds 0.7 is so small that it is assumed to be im(cid:173)
`possible. Likewise for the probability of a transmitted 1 being so
`corrupted that the received voltage falls below -0.7. The probabil(cid:173)
`ities of a 0-to-erasure failure or !-to-erasure failure are not negli(cid:173)
`gible, and special coding strategies are often used for correcting
`erasures. The BEC is depicted in Fig. 1-2, with erasures denoted
`asx.
`
`1.3 Software Notes
`The programs in this book were constructed as a set of modules.
`Modules have been described as "poor folks' objects" 1 and they are
`about as close as we can conveniently get to "true" objects without
`stepping up from C to C++. Modules support a subset of object(cid:173)
`oriented programming that has been dubbed object-based pro(cid:173)
`gramming. Modules don't support inheritance, but they do support
`abstraction and encapsulation. Modules are implemented in C as
`separate source files. This means that the programs in this book
`
`1 McConnell: Code Complete, Microsoft Press, 1993.
`
`Strategic Issues
`
`~~~~~~~~mi~;; -~ f f . i l : t !i! ;-
`
`B!ii&l:-W,ft2i11&. :Sliii '.m:llffl'!E~
`
`Page 11 of 88
`
`

`

`1-p
`
`1-p
`(cid:127) 1-2 Transition probabilities in the binary
`erasure channel.
`
`are organized into modules that make sense in the context of what
`we're trying to accomplish, but which do not necessarily match up
`with the way chapter contents are organized.
`
`Each file contains both data and functions which can be declared
`static to make them visible only within the file. Module variables
`are static variables, which are global within the file. Not every
`function in a module makes use of every module variable, so as
`each function is presented in the text, in the way that it interacts
`with module variables is also covered. The software accompanying
`this book is described in Appendix D.
`
`Software notes
`
`Page 12 of 88
`
`

`

`Mathematical Tools
`for Coding
`
`Many of the calculations used to perform encoding, decoding, and
`performance analysis for the codes in this book make use of pecu(cid:173)
`liar arithmetic and other mathematical techniques that are a bit out
`of the ordinary. These techniques, which are essential for the work
`in subsequent chapters, include modulo-p arithmetic, extension
`fields, and polynomial arithmetic. These topics sound a lot more
`difficult than they really are, and this chapter attempts to intro(cid:173)
`duce and explain this material in a way that is relatively painless.
`This goal is consistent with the hands-on "cookbook" approach
`chosen for this book. However, presenting these techniques as iso(cid:173)
`lated, unconnected rote procedures will prove somewhat unsatis(cid:173)
`fying to many readers and might actually make it more difficult for
`these readers to embrace these new techniques and begin using
`them. Therefore, this chapter is a compromise between extremes.
`The individual sections present the necessary foundation material
`embedded in a broader mathematical fabric for interested readers.
`However, wherever it is appropriate, the sections begin with a box
`entitled "The Basic Idea." The contents of this box briefly explains
`how the subsequent material in the section fits into the overall
`study of coding with an emphasis on why it is important for prac(cid:173)
`tical coding applications. Most sections end with a box entitled
`"The Bottom Line." This box summarizes the information that the
`reader needs to become familiar with and carry forward into sub(cid:173)
`sequent sections and chapters.
`
`2.1 Modulo Arithmetic
`
`~~~ ; , , ) . i
`
`Modulo Arithmetic
`:~..,wg;;,..,Ei!fi"""! ~'""EJ""""""""""'Mffi,""-'""''""'w ... J.&""iiS.IJi_;&i .......... ..,..,,, _ _ .i.£ ...
`
`SIRS#fil , r~ ... ~11::l!l ...
`
`il t""SL-l l\.1~1~ISIDilli el!W•lo:usm.
`
`Page 13 of 88
`
`

`

`,,.
`
`,,.
`
`,,
`
`,,
`
`/
`
`/
`
`/
`
`I
`
`,,.
`
`//r
`
`4
`
`II'/~
`/./
`/
`I
`,--1..L
`T
`I
`
`/ ,,.
`
`5
`,,,,.--+-------- .....
`O
`.,,.-1--...._
`-5
`
`'
`
`.... '
`
`\
`.,..
`- 4 I
`I
`I
`
`I
`I
`I
`9 -L
`I
`I
`
`l
`\
`I
`\
`
`\
`
`'
`' ' '
`
`....
`
`' ' ' ' '\
`
`\
`
`\
`-.Jal
`
`',
`'-\
`\ 6
`'\
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`
`Modulo arithmetic can be viewed as the result of "wrapping" the
`integers aroWld a circle (Fig. 2-1) for the specific case of modulo-
`5 arithmetic. This wrapping causes 5 to be "the same as" or con (cid:173)
`gruent to 0. This forces 6 to be congruent to 1, 7 to be congruent
`to 2, 10 to be congruent to 0, and so on. The congruences need not
`be limited to just positive integers. As shown in the figure, -1 is
`congruent to 4, -3 is congruent to 2, etc. The usual mathematical
`notation for congruence is a triple-bar equals sign, "=." Thus "1 =
`16" is read as "1 is congruent to 16."
`
`10
`.,,..,..---t---- .... _ ....
`
`'
`
`.... ....
`
`....
`
`s'I...., ..._ .... ______ _.
`(cid:127) 2-1 The modulo-5 number system can be
`viewed as the set of integers "wrapped" around a
`circle to establish congruences between O and 5,
`1 and 6, - 1 and 4, etc.
`
`2.1.1 Modulo-2 Arithmetic
`The vast majority of the computations used to perform encoding and
`decoding involve modulo-2 arithmetic. This is due primarily to the
`close relationship between modulo-2 arithmetic and the Boolean al(cid:173)
`gebras commonly used by designers of digital logic circuits.
`
`Mathematical Tools for Coding
`""""""""""""''""""""""""""'""""'""""-.."""'"'"""""""""""""""""'""""-~~~~;;~1121li1%1,ZM&kii,il£JJW:J!l1 i
`
`JliiilLl£l&l,)..JiiWil&jilJ.i..W
`
`Page 14 of 88
`
`

`

`Boolean Algebras
`Encoders and decoders (not to mention computers) are con(cid:173)
`structed from logic circuits of various types. The logical behavior
`of these circuits can be modeled and analyzed using a particular
`type of algebra called Boolean algebra (which is named in honor
`of its inventor George Boole). Strictly speaking, Boolean algebra
`includes several different algebras, each of which uses different
`sets of logical operations, such as {AND, OR, INVERT} or {NAND, NOR,
`INVERT}. In the particular Boolean algebra of interest here, there
`are two elements or values as well as two logical operations. The
`values are TRUE or FALSE, and the operations are AND, and XOR (ex(cid:173)
`clusive or). The results of these operations are listed in Tables 2-1
`and 2-2.
`
`II Table 2-1 The logical AND
`operation of Boolean algebra.
`
`AND
`F
`T
`
`F
`F
`F
`
`T
`F
`T
`
`II Table 2-2 The logical XOR
`operation of Boolean algebra.
`
`XOR
`F
`T
`
`F
`F
`T
`
`T
`T
`F
`
`Modulo-2 Arithmetic
`A mathematical analog or isomorphism to the logical 0 valued
`Boolean algebra of Tables 2-1 and 2-2 uses values of O and 1, and
`operations of modulo-2 multiplication and addition, as shown in
`Tables 2-3 and 2-4. The. value O corresponds to FALSE, and the
`value 1 corresponds to TRUE. Modulo-2 multiplication corresponds
`to the logical AND operation. The result of (a AND b) is true only if
`a and bare both TRUE.
`Similarly, the result of a x bis 1 only if a and b both equal 1. Mod(cid:173)
`ulo-2 addition corresponds to the logical XOR operation. The result
`of (a XOR b) is 1 only if either a orb (but not both) is TRUE. The re(cid:173)
`sult of a + b is 1 only if either a orb (but not both) is 1.
`
`~~~ i t@ '~~~ . 1 : 0 ·~ . , , ,..,. _ _ _ _ _ .... """"'·""'• """"'""""'""""'·'T~1"'~/2?~~~~,#ffili;".{!I:'~,EI(EJ( ~:!=Im.
`
`Modulo Arithmetic
`
`Page 15 of 88
`
`

`

`(cid:127) Table 2-3
`Binary multiplication.
`
`X
`0
`1
`
`0
`0
`0
`
`1
`0
`l
`
`(cid:127) Table 2-4
`Modulo-2 addition.
`
`+
`0
`1
`
`0
`0
`1
`
`1
`1
`0
`
`Programming Considerations Modulo arithmetic can be implemen(cid:173)
`ted in C for arbitrary moduli using the remainder operator. The
`expression x%y returns the remainder produced by dividing x by y.
`Assuming that x and y are both "legal" values modulo-q (i.e. 0::;; x
`< q and O ::; x < q) then modulo-q addition and multiplication can
`be easily implemented, as shown in the following code fragment.
`
`int x, y, q, sum, product
`/*************************************/
`/* Note: if q==O, a divi de-by-zero */
`/* error wil l occur.
`*/
`
`/* modulo-q addition */
`sum= (x+y ) %q;
`
`/* modulo -q mul t iplicat i on */
`product = (x*y) %q;
`
`/** end of fragment **/
`
`Modulo-2 arithmetic occurs so frequently that it might lead to
`greater program efficiency if we use Boolean operations in place of
`the remainder operation for modulo-2 arithmetic. As shown in the
`following code fragment, there are a number of possibilities.
`
`int x, y, q, suml, sum2, sum3, prodl, prod2
`
`/* modulo-2 addition */
`
`suml = x A y;
`I*
`s umZ = x != y;
`/*
`s um3 = ! ( x && y) ; I*
`to
`
`uses bitw i se XOR */
`uses NOT EQUALS */
`uses l ogi cal NOT with
`impl ement logical NANO
`
`logical AND
`*I
`
`Mathematical Tools for Coding
`
`_,---·----------·"··-··· --------------------
`
`Page 16 of 88
`
`

`

`/* modulo-2 multiplication */
`prodl = x & y
`/* uses bitwise AND */
`prod2 = x && y
`I* uses logical ANO */
`/** end of fragment **/
`
`2.2 Finite Fields
`
`2.2.1 Groups
`Modulo-2 addition is an example of a mathematical structure
`called a group, and we can use modulo-2 addition to illustrate a
`number of important properties that are shared by all groups:
`1. The set of integers (1,0} is said to be closed under the
`operation of modulo-2 addition, because the modulo-2
`addition of any two elements in the set produces a result that
`is also in the set.
`2. The modulo-2 addition operation is associative, meaning that
`(a+ b) + c =a+ (b + c)
`for all a, b, and c which are elements of (0,1).
`3. The element 0 is called the identity element and has the
`property that
`
`a+0=0+a=a
`for all a, which are elements of (0,1).
`4. For each element a in (0,1), there is an element -a that when
`added to a produces a result of 0:
`0+0=0
`1+1=0
`The element -a is called the additive inverse of a. (In
`modulo-2 addition, each element is its own inverse, but in
`general, this will not be true of other groups.)
`
`1 R. J. McEliece: Encyclopedia of Mathematics and Its Applications, Vol. 3: The
`Theory of Information and Coding, Addison-Wesley, Reading MA, 1977.
`
`Finite Fields
`
`Page 17 of 88
`
`

`

`The group formed by modulo-2 addition is further identified as a
`commutative group or abelian group because a + b = b + a for
`all a and b, which are elements of {0,1).
`It turns out that modulo-q addition forms a commutative group for
`any value of q = 2,3,4, ...
`
`Example 2.1 Show that modulo-3 addition forms a commutative
`group.
`
`Solution Modulo-3 addition results are summarized in Table 2-5.
`
`(cid:127) Table2-5
`Modulo-3 addition.
`
`+
`0
`l
`2
`
`0
`0
`1
`2
`
`1
`1
`2
`0
`
`2
`2
`0
`1
`
`Each of the five prerequisites for a commutative group are satisfied:
`
`D Inspection of Table 2-5 reveals that modulo-3 addition is
`closed. All results are elements of the set {0,1,2).
`(cid:143) Modulo-3 addition is associative.
`(cid:143) The identity element for modulo-3 addition is 0.
`D Inspection of Table 2-5 reveals that each element has an
`additive inverse. Specifically,
`-0 = 0
`-1 = 2
`
`-2 = 1
`
`\end{array}
`(cid:143) Table 2-5 is symmetric about its main diagonal; therefore, the
`operation is commutative.
`
`Modulo-3 multiplication also forms a commutative group over
`the nonzero elements {l, 2}. The results for modulo-3 multiplica(cid:173)
`tion are summarized in Table 2-6.
`
`(cid:127) Table 2-6
`Modulo-3 multiplication.
`
`X
`0
`1
`2
`
`0
`0
`0
`0
`
`1
`0
`1
`2
`
`2
`0
`2
`1
`
`Page 18 of 88
`
`

`

`The five prerequisites (some of them reworded slightly for multi(cid:173)
`plication) are satisfied:
`(cid:143) Inspection of the table reveals that modulo-3 multiplication is
`closed over {l, 2).
`(cid:143) Modulo-3 multiplication is associative.
`(cid:143) The identity element for multiplication ( or multiplicative
`identity) is 1.
`(cid:143) Inspection of Table 2-6 reveals that each element in { 1, 2} has
`a multiplicative inverse. Specifically,
`lxl=l
`2x2=1
`(cid:143) In algebraic form, the multiplicative inverse of a is denoted as
`a-1.
`
`(Note: In general, each element will not be its own
`multiplicative inverse as it is here. For example, in modulo-5
`multiplication, the multiplicative inverse of 2 is 3.)
`
`It turns out that the set of nonzero elements {l, 2, ... , p - l} mod(cid:173)
`ulo-p with multiplication forms a group over for all prime values of
`p. However, for composite (i.e., nonprime) values of q, modulo-q
`multiplication does not form a group over the set {l, 2, ... , q - l}.
`Example 2-2 Show that modulo-4 multiplication does not form a
`group over the elements {l, 2, 3}.
`Solution Modulo-4 multiplication results are summarized in Table
`2-7. The set of nonzero values (1, 2, 3} is not closed under modulo-
`4 multiplication because examination of the table reveals that 2 x
`2 = 0. Furthermore, there is no multiplicative inverse for the ele(cid:173)
`ment 2.
`
`II Table 2-7
`Modulo-4 multiplication.
`
`X
`0
`1
`2
`3
`
`0
`0
`0
`0
`0
`
`I
`0
`1
`2
`3
`
`2
`0
`2
`0
`2
`
`3
`0
`3
`2
`l
`
`2.2.2 Fields
`A set F, in conjunction with two operations (one "addition-like"
`called addition and one "multiplication-like" called multiplication)
`
`Finite Fields
`
`Page 19 of 88
`
`

`

`defined over the elements of F forms a mathematical structure
`called afield if and only if the following conditions are satisfied:
`1. The elements of F form a commutative group under the
`operation of addition.
`2. The nonzero elements of F (that is all elements except the
`additive inverse) form a commutative group under the
`operation of multiplication.
`3. The multiplication operation distributes over the addition
`operation.
`
`The number of elements in a field can be either finite or infinite.
`The set R of real numbers, in conjunction with ordinary addition
`and multiplication, is an example of an infinite field. In coding the(cid:173)
`ory, we will be concerned exclusively with finite fields.
`Definition 2.1 The number of elements in a field is called the order
`of the field.
`
`Finite fields are also called Galois fields in honor of Evariste Ga(cid:173)
`lois who outlined the connection between groups and polynomial
`equations in a letter to his friend Auguste Chevalier written on
`the eve of a duel on May 30, 1832 in which Galois was fatally
`wounded.2 A Galois field of order q is denoted as GF(q). The field
`specified by Tables 2-3 and 2-4 is thus denoted as GF(2). This field
`has 2 elements and makes use of modulo-2 addition and modulo-2
`multiplication. It is possible to extend this idea to a field withp el(cid:173)
`ements using modulo-p arithmetic, provided that p is prime. Such
`a field is called a prime field. As you will see in Section 2.4, it is
`also possible to construct fields GF(q), where q = pm, m = 1, 2, ...
`
`2 I. Stewart: Galois Theory, 2nd ed., Chapman & Hall, London, 1989.
`
`Mathematical Tools for Coding
`&Ea ... , __ , ____ .., _____ ,....,,,..~ ... = ffi--i!iiiim""'M"'""'""""' __ .., .. _;fail~l:i!:w.iElil "
`
`imf!E.&:ffl'.l~til! 3
`
`i !U im.:::Z ;zc =~II§
`
`~ Rilllllllil~~-l~ll~ffl :lillilml!II
`
`Page 20 of 88
`
`

`

`2.3 Introduction to Polynomials
`
`Much of coding theory (including the construction of extension
`fields to be covered shortly) is based on polynomial arithmetic.
`A polynomial in xis simply a weighted sum of powers of x. Some
`examples of polynomials in x are
`f 1(x)=5x2 + 3x+l
`f 2(x)=x4 +x3 +1
`fs(x) =X3 -2
`The degree of the polynomial is the highest power of x appearing
`in the polynomial. The degree off1 (x) is 2; the degree off/x) is 4;
`and the degree offlx) is 3.
`
`zJ:Jil!lllblll!!$l~lHJl~;;sll
`
`Introduction to Polynomials
`oom;~
`
`lmlif.iil™
`
`u~~ ±JI
`
`Page 21 of 88
`
`

`

`In coding theory, we will often be interested in polynomials in
`which the coefficient of each term is either O or 1. In the context
`of coding theory, such a polynomial is called a polynomial over
`GF(2). Of the three example polynomials shown,J;(x) is the only
`polynomial over GF(2). When performing arithmetic on polynomi(cid:173)
`als over GF(2), powers of x can be multiplied in the usual way;
`that is,
`
`x2-x3=x5
`X • x7 = x8
`X•X=X2
`
`However, the addition of coefficients is performed using modulo-2
`addition. For example,
`x 2 + x 2 = 1 • x 2 + 1 • x 2 = (1 + 1) • x 2 = 0 • x 2 = 0,
`
`(x + 1) + (x2 + x) = 1 • x + 1 + 1 • x 2 + 1 • x
`= l •x2+ (1 + 1) •X+ 1
`=l•x2 +0•x+l=x2 + 1
`
`and
`
`x 5 + x 5 + x 5 = (1 + 1 + 1) • x 5 = 1 • x 5 = x 5
`
`Because each element in GF(2) is its own inverse, subtraction of
`polynomials over GF(2) is the same as addition:
`x3+x+I=x3+x+l
`-(x3 + x2 + 1) = + (x3 + x2 + 1)
`x 2 +x+l
`
`However, this is not true for polynomials over GF(p) p > 2. Con(cid:173)
`sider the subtraction of two polynomials over GF(3):
`x3+x+l=x3 +x+l
`-(2x3 + x2 + 2) = +(x3 + 2x2 + 1)
`2x·3 +2x2 + x +2
`
`[Note that in GF(3), -2 = 1, -1 = 2.]
`
`A general polynomial of degree N can be written as
`f(x) = bNxN + bN_1xN- I + ... + b2x 2 + b1x + b0
`(2.1)
`where some of the bn might be zero for n < N. (If bN = 0, the degree
`of the polynomial is not N.) A more compact notation is
`N
`f(x) = .I, bnxn
`n= O
`
`(2.2)
`
`Page 22 of 88
`
`

`

`e
`
`y
`
`..
`'
`
`Programming Considerations How can a polynomial such as Eqs. 2.1
`or 2.2 be represented in software? We can store the coefficients of
`f(x) in an array, for example coef[], with the coefficient for x 11 in lo(cid:173)
`cation n. When the polynomial is represented this way, it is easy to
`multiply or divide the polynomial by a power of x . To multiply J(x)
`by xk, fork~ 0, simply shift the coefficients upward by k locations
`in the array, as shown in the following code fragment:
`
`/**
`
`fragment to multiply polynomial by x**k **/
`
`/* shift original N coefficients */
`
`for( n=N; n>=O; n--)
`
`{
`coef[n+k]
`}
`
`coef [n ];
`
`/* store zeros for the k lowest-order new coefficients */
`
`for( n=k-1; n>=O; n--)
`{
`coef[n] = 0;
`}
`
`/*
`
`increase degree of polynomial by k */
`
`N += k;
`
`/** end of fragment **/
`
`To dividej(x) by xk fork 2: 0, shift the coefficients downward by k
`locations in the array as shown in the following program fragment.
`The k lowest-order terms in the original polynomial will become
`the remainder of the division operation.
`
`/**
`
`fragment to divide polynomial by x**k **/
`
`/* save remainder */
`for( n=O; n<k ; n++)
`(
`remainder[n]
`}
`
`coef[n];
`
`/* downshift the higher-order coefficients by k places */
`
`for( n=O; n<=(N·k); n++)
`{
`coef[n]
`)
`
`coef[n+k];
`
`/* store zeros i n locations originally occupied by k
`higher -order terms */
`
`""
`
`~~1':mmi'.!~ill&iidi2:IJ
`
`il!f," lfcil?mlJitii.m!S $'.
`
`l\:D)lla\:BI~ g IE! m;:mmim: Eawh~A)H!~ i j
`
`.iL.Slii%:i~r1-il!lM;;;;;c;,1..:1s;s;:j&L lR wa:i:;;;:;;;;z;:z;: ..m@k.&,&:::Whi.i!i::lr&M:.!i!l ~£m·l#Zii:.i.~ · .·
`
`Introduction to Polynomials
`
`Page 23 of 88
`
`

`

`for( n=(N-k+l); n<=N; n++)
`{
`coef[n]
`l
`
`0;
`
`/** end of fragment **!
`
`2.4 Extension Fields
`
`As demonstrated in Section 2.1, it is a simple matter to construct
`a field GF(p) for any prime p by using modulo-p addition and mul(cid:173)
`tiplication. In working with various codes, it turns out to be very
`useful if all of the necessary manipulations can be performed
`within a field having 2m elements, with each element being an m(cid:173)
`bit binary value. But so far, we have seen only fields in which the
`number of elements is a prime number; and of course, 2m is not
`prime form> l. What happens if we try to construct a field with
`2rn elements using modulo-2m arithmetic?
`Example 2.3 Consider the specific case of 2m = 23 = 8. The opera(cid:173)
`tions of modulo-8 addition and modulo-8 multiplication are de(cid:173)
`fined in Tables 2-8 and 2-9. Examination of Table 2-8 reveals that
`modulo-8 addition does form a commutative group (see Section
`2.2.2). However, examination of Table 2-9 reveals that there are no
`multiplicative inverses for the even numbers 2, 4, and 6. This
`means that the integers 1, 2, 3, 4, 5, 6, and 7 do not form a group
`under modulo-8 multiplication; therefore, modulo-8 arithmetic
`cannot be used to construct a field GF(2m).
`
`Although it is not possible to construct a Galois field GF(2m) using
`modulo-2m multiplication, it is possible to construct such a field
`using polynomial ari thmetic.
`
`Mathematical Tools for
`
`Page 24 of 88
`
`

`

`II Table 2-8 Modulo-a addition.
`
`0
`0
`1
`2
`3
`4
`5
`6
`7
`
`I
`1
`2
`3
`4
`5
`6
`7
`0
`
`2
`2
`3
`4
`5
`6
`7
`0
`l
`
`3
`3
`4
`5
`6
`7
`0
`1
`2
`
`4
`4
`5
`6
`7
`0
`1
`2
`3
`
`5
`5
`6
`7
`0
`1
`2
`3
`4
`
`6
`6
`7
`0
`1
`2
`3
`4
`5
`
`II Table 2-9 Modulo-8 multiplication.
`
`0
`0
`0
`0
`0
`0
`0
`0
`0
`
`I
`0
`1
`2
`3
`4
`5
`6
`7
`
`2
`0
`2
`4
`6
`0
`2
`4
`6
`
`3
`0
`3
`6
`I
`4
`7
`2
`5
`
`4
`0
`4
`0
`0
`0
`4
`0
`4
`
`5
`0
`5
`2
`3
`4
`1
`6
`3
`
`6