Decoding the Golay Code E. R. Berlekamp’ Communications Systems Research Section A procedure is described for correcting all patterns of three or fewer errors with the (23, 12) or (24, 12) Golay code. The procedure decodes any 24-bit word in about 26 “steps,” each of which consists of only a few simple operations such as counting the number of ones in a 12-bit word. The procedure is based on the circulant view- point introduced by Karlin (1969). In addition it is shown how the (24,12) Golay code can be used to correct certain patterns of more than three errors. |. Introduction Recently there has been a revival of interest in the use of binary block codes for deep space telemetry, since such codes can be used as the “outer” codes in concatenation schemes. These concatenation schemes are an attractive method of providing the very low bit error probabilities which will be required for the nonvideo science experi- ments on future deep space missions, One of the most powerful known block codes is the Golay (24, 12) code, which is known to be capable of correcting. all pattems of three or fewer bit errors. In Section II we describe a simple method of actually cor- recting these errors; this makes the Golay code (perhaps. interleaved enough to deal with the bursts caused by the “inner” channel) a very attractive candidate for the “outer” code in certain concatenation schemes. In Section III we show how the Golay code can be used to correct certain patterns of more than three errors, Consultant, Department of Mathematics and Electrical Engineering, University of California, Berkeley JPL TECHNICAL REPORT 32-1526, VOL. XI I. The Algorithm It is known that the parity-check matrix of the (24, 12) Golay code may be written as [ya where I is the 12 12 identity matrix and 11011100010 1 01101110001. 1 10110111000 1 01011011100 1 00101101110 1 00010110111 1 A=} loo1011011 1 11000101101 1 11100010110 1 1110001011 1 10111000101 1 mu 0 al‘Let A denote the 11 > 11 upper left submatrix of A, Ais a circulant matrix, each row of which is obtained by a eyclic right shift of the previous row. If the rows and columns of A are labeled from 0 to 10, then __ (Lif ~ iis 0 or a quadratic residue modulo 11 0 if j — i is a quadratic nonresidue modulo 11 From this, itis easily seen that 4 At Each codeword of the (24,12) code may be written as a row veetor C, which satisfies the equation HC! = 0. If is transmitted and R is received, then the channel error pattern is E = R ~ C. The syndrome of R is the 12-dimensional column vector s* defined by st = HR Since HE! = HR' ~ HC! = HR’, the syndrome of the received word is the same as the syndrome of the error word, and this is the sum of the columns of the Hf matrix corresponding to the error locations. Let uy, ‘+ th: denote the 12 unit row vectors in 12 dimensions (e.g, uy ~-[001000000000}); let As, As, denote the rows of A, so that A Ae A= and let Af, Af, "+ + .Af, denote the columns of A, so that A=TAQIAGL 1Ag] ‘The syndrome s! ~ HES may now be represented as 3 BAL s= 3 Bw Similarly, Als = A'HE = [A‘|I]-E whence 82 If we now assume that |E| 3, then at least one of the following must be true: Case I: [Eu Ein o** Ead| = Case IL Eye ++ ,Ead]| =1, there exists 4), 13- for which Alea 3B Bw asta, Case IIL ILE. Es ++ ,Ex]]=0, [8A] = [A's 3 Bina =sA Case IV: Te ]| = 1, there exists a;,1=j=12 for which Js + Ay] =2, SALA; Hence, the decoding can be accomplished simply by weighing each of these 26 vectors: 88+ Ags + Ay sAsA + ASA tA, ws As, wsA+ Ay For example, suppose s = 100011010010. Since |s} > 3, we compute s + A: = s + 110111000101 = 010100010111, Since |s+A;|>2, we compute |s-+ As] =6>2, [s+ As] = 6>2 [s+ A] =8>2 |s + A] =6>2, [s+ Ad] 852, |stA|=4>2, |s+ Al =4>2 |s +A] 10>2, |s+ Aro] =8>2, [5+] =6>2, [s+ Aro] =6>2. Itis now clear that if |E] =3, then |[E., Ez", Ese]| > 1 and henee |[Ess, Ess, Ex4]| = 1, So we continue by computing A's‘ = sA sA +A, = 010001100010, |sA + A,| =4>2, |sA +A, 6>2,|sA+As|=6>2, [sd + A.J =6>2, [sA + Al 852, |sA + Ac] =4>2, 8A + A; = 000100010000. Since |sA+A;| =2, E, = and E =0000001000000000100010000. 100LIOLOOLLL, |sA] = 7>3, Most of the decoding effort is counting the weights of the 26 relevant 12-bit vectors, For this reason, this decod- ing algorithm is particularly well-suited to computers JPL TECHNICAL REPORT 32-1526, VOL. XIwhich have this instruction built in, such as the CDC 6400, £6500, 6600, and 7600. If programmed on a machine which is unable to count the weight of a 12-bit word in a single instruction, the easiest way to obtain this quantity is, usually to break up the 12-bit word into pieces (say 2 pieces of 6 bits each or 3 pieces of 4 bits each) and obtain the weight of each piece by looking it up in a table. Ill, Decoding More Than Three Errors ‘The Golay code has 2” codewords of length 23, and since (83) + (39) + (23) + 23) =", every coset contains ‘one word of weight =3. However, the extended Golay code, which has 2'* codewords of length 24 has (3) + (%4) = 2" cosets of odd weight and another 2° (38) = Gl) + WCB) cosets of even weight. It is thus pos- sible to correct 4% of the (24) possible error patterns of weight 4. Some of these words of weight 4 correspond to short bursts. Even though the space channel itself is mem- oryless, the convolutional code will occasionally make mis- takes which the Golay code will see as error bursts. For this reason, short bursts of weight 4 are more probable error patterns than long bursts of weight 4. ‘The sum of any two words of weight 4 from the same coset is a codeword of weight 8. Hence we may gain a considerable amount of information about which words of weight 4 are correctable and which are not by studying the codewords of weight 8. Since there is exactly one codeword of weight 8 which has 1s in any given five positions, the total number of codewords of weight 8 is 24 23 X 22 x 21 20/8 X7 X6X5X4=3 x 11 X 23, Each codeword of weight 8 has 23 distinct cyclic shifts. The codewords of weight 8 lie in 33 sets of 23 codewords each. Furthermore, each code- word of weight 8 can be mapped into 11 different code- words by the permutation C(x) C (x*) mod (x* + 1), for 1=0,1, + ,10, Under this permutation, there are only 3 equivalence classes of codewords. The 11 members of each class are listed in Table 1 ‘The most probable error pattems of weight 4 are those which are due to the sum of one or more short bursts. The solid burst of length 5 occurs in codeword number 23 of Table 1. By inspecting this word, we see that the solid burst of length 5 in positions 0, 1, 2, 3, 4 lies in the same coset as, the pattern of three isolated errors in positions 7, 10, and 12. Hence, if all error patterns of weight = 3 are cor- rected, then a solid burst of length 5 cannot be corrected. JPL TECHNICAL REPORT 32-1526, VOL. XI ‘There are five codewords which contain solid bursts in positions 0, 1, 2, 3. These words may be found as cyclic shifts of lines numbered 1, 22, 23, 23, and 26 of Table 1. Since no codeword of weight 8 contains two disjoint solid bursts of length 4, all solid bursts of length 4 may be cor- rected by the extended Golay code of length 24. A burst of length 5 and weight 4 must be of one of the following three types: 11101, 11011, 10111. Type 11101 is contained in Table 1 codewords numbered 2, 6, 22, 23, 24, ‘Type 11011 in codewords numbered 1, 6, 11, 14, 23, and ‘Type 10111 in codewords numbered 1, 2, 5, 12, 23. ‘The most probable error patterns of weight four are those which are due to the sum of one or two short bursts. "These types of error patterns and the codewords of Table 1 which contain them are as follows: " Errortype Reference numbers of Table 1 codewords, “Tplasd—1,3,4,5, 6,11, 12, 17 21, 22, 23, 24,26, 28, 93 1,3,4,6,8,9, 10,11, 12, 14 17,21, 25, 26, 27,29, 30, 91, 32, 33 11 plus 11 ‘An examination of the conflicts between the goal of correcting 111 plus 1 and 11 plus 11 reveals the following dangerous codewords through positions 0, 1, 2: Reference amma number 012 7,89, @ 4 ane, ® wars 4 01,2, 45, @, 1819 6 a12 10,1,13.4, 1" 012, 5,6, nw ® 2 ‘This shows that any pair of two sets of double adjacent errors can be corrected and that one can also correct any error pattern of the type 111 plus 1 (ie., a solid burst of length 3 and an additional isolated error) unless the iso- lated error follows the burst by 6, 9, 10, 13, 17, 15, or 19 digits. If the isolated error follows the burst of length 3 by 9, 19, of 15, the syndrome is the same as for a pair of bursts of length 2; if the isolated error follows the burst of 3 by 13, 17, 6, or 10, then there is ambiguity with another error pattern of the same type.a4 jiography Berlckamp, E. R., Algebraic Coding Theory, McGraw-Hill Book Co., New York, 1968 (see Sec. 15.2, pp. 352-361, particularly Eq. 15.242, p. 357). Karlin, M., “New Binary Coding Results by Circulants," IEEE Trans, Inform. Th., Vol. 15, pp. 81-92 (see Fig. 1, p. 82) JPL TECHNICAL REPORT 32-1526, VOL. XITable 1. One codeword of weight 8 from each of the Reference number 12 13 “4 5 16 7 18 19 20 21 22 23 25 26 aT 28 29 30 31 32 3 8 16 9 18 1B 3 6 BR 1 2 4 16 18 13 2 3 6 12 1 2 4 8 16 8 18 7 M 5 10 20 rg n 22 aL 19 15 5 10 20 fa u 2 21 19 15 5 10 20 1 n 22 a1 19 5 1 “ 10 20 Ww u 2 21 19 15 7 “ 5 2 16 18 13 10 20 7 u 2 a 133 eyeli¢ equivalence classes Positions of Is in the codeword 13 u 2, a1 19 15 “i Teengths (origin) 400), 322) 205) sito) oi22) ‘of solid bursts 27) 2(20) 3am) 3i21)_22) 2116) 208) 210) 212) 3t4) ua) 222) 216) 2116) 2(22) en) 2113) 265) 216) 312) #0 sto) 30) 214) 49 218) 6) 2) 205) 216) 200) 300 2122) 205) 2109) 2014) 20) 2(20) an) 210) 206) 210) 2(22) 208) 2122) 202) 208) 215) 207) 210) 202) JPL TECHNICAL REPORT 32-1526, VOL. x! 85