United States Patent [19]
`Patterson
`
`[11] Patent Number:
`[45] Date of Patent:
`
`4,623,999
`Nov. 18, 1986
`
`[54] LOOK-UP TABLE ENCODER FOR LINEAR
`BLOCK CODES
`Inventor: Patricia L. Patterson, St. Petersburg,
`Fla.
`
`[75]
`
`[73] Assignee: E-Systems, Inc., Dallas, Tex.
`Appl. No.: 617,167
`[21]
`Jun. 4, 1984
`Filed:
`[22]
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`Int. Cl,4 .............................................. G06F 11/08
`U.S. CI ......................................... 371/37; 371/40;
`371!43; 371/45
`Field of Search ....................... 371/37, 38, 39, 40,
`371/43,45,44; 364/200,900
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,020,461 4/1977 Adams .................................. 371!37
`4,030,067 6/1977 Howell .................................. 371!37
`4,099,160 7/1978 Flagg .................................... 371!37
`4,291,406 9/1981 Bah) ...................................... 371/44
`4,312,069 1!1982 Ahamed ................................ 371/37
`4,359,772 11!1982 Patel ...................................... 371/38
`4,414,667 11/1983 Bennett ................................. 371/39
`4,466,099 8/1984 Meltzer ................................. 371/37
`
`4,473,902 9/1984 Chen ..................................... 371/37
`4,509,172 4/1985 Chen ..................................... 371/38
`Primary Examiner-Michael R. Fleming
`Attorney, Agent, or Firm-Albert M. Crowder, Jr.
`[57]
`ABSTRACT
`An efficient look-up table encoder for encoding k bit
`information words with linear error correcting block
`codes is provided comprising a plurality of read-only
`memories having 2xi, 2x2, ... , and 2xi address locations,
`respectively, where XI +x2+ ... x;=k Each of the
`read-only memories receives a portion of a k bit infor(cid:173)
`mation word that serves to address a respective location
`therein, thereby mapping the portion of the k bit infor(cid:173)
`mation word into an output word stored at the location.
`Corresponding bits of output words from the plurality
`of read-only memories are mod-2 summed by n- k
`exclusive-OR gates to generate a parity word associated
`with the information word. For systematic encoding,
`the parity word is then appended to the information
`word to form a codeword uniquely associated with the
`information word. This encoding scheme obviates look(cid:173)
`up tables having 2kx(n- k) storage locations.
`
`14 Claims, 3 Drawing Figures
`
`14
`
`k
`
`20o
`
`n-k
`
`k
`
`• • •
`
`X·
`I
`
`18n
`(uk-xi+t ... uk)
`
`.!:!P
`
`• • •
`
`• • •
`
`Hughes, Exh. 1027, p. 1
`
`

`
`U.S. Patent Nov. 18, 1986
`
`Sheet 1 of2
`
`4,623,999
`
`I~
`JION k
`INFORM A
`VECTOR
`' u
`
`CODEWORD
`VECTOR, c
`
`}
`
`k
`y
`
`~
`
`n-k
`
`yp
`
`14
`
`/
`
`2k X (n- k)
`LOOK-UP TABLE
`\
`
`FIG. I
`
`10
`
`14
`
`k
`
`k
`
`x2
`
`18b
`... ux1 x )
`(ux
`+ 2
`1+1
`
`• • •
`
`X· I
`
`18n
`(Uk-Xj +1 ... Uk)
`
`20b
`
`n-k
`
`+
`I
`I
`p
`p
`(u
`~ 24
`+···+U
`x1+1 x1+1
`x1+x2 xl+x2
`
`22
`
`yp
`
`•
`•
`•
`
`•
`•
`•
`
`(uk+Xj+1p
`
`1
`
`k-Xj +1+ ... + UkP
`
`1
`
`k)
`
`F/6. 2
`
`Hughes, Exh. 1027, p. 2
`
`

`
`U.S. Patent Nov. 18, 1986
`
`Sheet2of2
`
`4,623,999
`
`~0
`
`28-..
`
`A5
`
`A4
`
`A3
`{P) ROM
`A2
`
`~
`
`26 ....
`
`AI
`
`Ao
`
`A5
`
`A4
`
`Bo
`810
`
`A3
`{P)ROM
`A2
`
`AI
`
`Ao
`
`Bn
`
`FIG. 3
`
`\
`
`\
`
`I D--P1o
`D--Ps
`I
`D--Ps
`I
`D--p7
`~I
`r-J, D--Ps
`D--p5
`--' l
`D--p4
`I
`D--p3
`D--p2
`J I
`~PI
`J
`''-<32
`J ~Po
`
`J
`
`I
`
`_).
`
`__l
`
`Hughes, Exh. 1027, p. 3
`
`

`
`1
`
`4,623,999
`
`LOOK-UP TABLE ENCODER FOR LINEAR
`BLOCK CODES
`
`TECHNICAL FIELD
`The present invention relates generally to encoding
`schemes and particularly to an efficient look-up table
`encoder for linear block codes.
`
`10
`
`BACKGROUND OF THE INVENTION
`The use of linear block codes for error detection and
`correction in digital data transmission is well-known.
`Such codes act on information in blocks, each block
`forming an information word to be transmitted or !5
`stored. In the case of cyclic linear block codes, a code(cid:173)
`word uniquely related to each information word is pro(cid:173)
`duced during the encoding scheme, this codeword
`being divisible by a fixed generator word. At the re(cid:173)
`ceiver, a received codeword is divided by the generator 20
`word. If a non-zero remainder results from this division,
`then errors have occurred during transmission. More(cid:173)
`over, this remainder, or syndrome, is uniquely related to
`an error pattern which is then corrected.
`Suitable codewords. for such schemes have been gen- 25
`erated in a variety of ways. For systematic encoding of
`cyclic codes, one such method utilizes serial data input(cid:173)
`/output wherein each information word is applied to an
`(n- k)-stage shift register with feedback connections
`based on a generator polynomial. After the information 30
`bits are shifted into the register and simultaneously into
`the communication channel, then- k parity bits formed
`in the register are shifted into the channel, thus forming
`the complete codeword. This approach, however, is
`incompatible with parallel data input/output. To over- 35
`come this problem, suitable codewords have also been
`generated by table look-up encoding schemes which
`serve to map the k bits of each information work to
`n- k parity bits. These n- k parity bits are then ap-
`pended to the k.bits of each information word to define
`the codeword uniquely associated with each informa(cid:173)
`tion word.
`Standard look-up table encoding, however, requires
`memory devices with 2k address locations. Such encod- 45
`ing schemes are thus impractical for medium length
`information words, and prohibitively complex and ex(cid:173)
`pensive when k is large. There is therefore a need for an
`efficient table look-up encoding scheme for linear block
`codes which obviates such large memory requirements. 50
`SUMMARY OF THE INVENTION
`The present invention describes an efficient look-up
`table encoder for encoding k bit information words
`with a linear error correcting block code which does 55
`not require storage devices having 2k address locations.
`In the preferred embodiment, the encoder includes a
`plurality of storage devices having 2x1, 2x2, ... , and 2xi
`address locations, respectively, where XI +x2 + ...
`+xi=k. Each of the storage devices receives a portion 60
`of a k bit information word that serves to address a
`respective location therein, thereby mapping the por(cid:173)
`tion of the k bit information word into an output word
`stored at the location. The output words from the plu(cid:173)
`rality of storage devices are then summed to generate a 65
`parity word associated with the information word. For
`systematic encoding of a linear block code, the parity
`word is appended to the information word to form a
`
`40
`
`2
`codeword uniquely associated with the information
`word.
`Preferably, each of the storage devices is a program(cid:173)
`mable read-only memory (PROM). For systematic en(cid:173)
`coding, corresponding bits of output words from the
`plurality of PROM's are mod-2 summed by n- k exclu(cid:173)
`sive-OR gates to generate the parity word, which is
`then appended to the information word to form the
`unique codeword.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`For a more complete understanding of the present
`invention and the advantages thereof, reference is now
`made to the following Description taken in conjunction
`with the accompanying Drawings in which:
`FIG. 1 is a block diagram of a standard look-up table
`encoder of the prior art for encoding systematic linear
`block codes;
`FIG. 2 is a block diagram of the look-up table en(cid:173)
`coder according to the present invention for encoding
`systematic linear block codes; and
`FIG. 3 is a schematic diagram of a look-up table
`encoder for a Golay linear block code.
`
`DETAILED DESCRIPTION
`Referring now to the drawings wherein like refer(cid:173)
`ence characters designate like or similar parts through(cid:173)
`out the several views, FIG. 1 is a block diagram of a
`standard look-up table encoder of the prior art. This
`encoder is utilized to generate a lengthened codeword
`vector c uniquely related to each information word
`vector, u. Referring to FIG. 1, the information word
`vector u, which is a component vector of k information
`bits, is applied to the look-up table 10 via line 12. The
`look-up table 10 has 2k address locations each of which
`stores an n-k length digital word. In the case of sys(cid:173)
`tematic encoding of a linear block code, the information
`word vector u also forms part of the codeword vector
`c via line 14. In operation, the information word vector
`u serves as an address to the look-up table 10 to select a
`parity word of n- k parity bits located at one of the 2k
`address locations. The look-up table 10 thus maps the
`information word vector u to uP where P represents a
`parity check matrix unique to a given block code. As
`seen in FIG. 1, the first k bits of the codeword vector c
`are the same as the k information bits. The standard
`look-up-table encoding scheme then maps the k infor(cid:173)
`mation bits to the n- k parity bits of the parity word
`given by uP. These parity bits are then appended to the
`information bits to define a codeword uniquely associ(cid:173)
`ated with the information word.
`Standard implementation of the look-up table en(cid:173)
`coder 10 of FIG. 1 requires storage devices with 2k
`address locations n- k bits in length. Such prior art
`look-up table encoders are therefore impractical even
`for medium length information words. Moreover, when
`k is large, look-up table encoders such as shown in FIG.
`1 are prohibitively expensive due to these large memory
`requirements.
`To ameliorate this problem, according to the present
`invention, the 2kx (n-k) memory device 10 of FIG. 1 is
`replaced with 2~i<k smaller memory devices of 2x1,
`2x2, ... , and 2xi address locations, respectively, where
`XI +x2+ ... +xi=k. To appreciate the advantages of
`the present invention, it should first be noted that the
`n- k parity bits given by uP may be written in the form:
`
`Hughes, Exh. 1027, p. 4
`
`

`
`3
`
`[PIIP~2 · · · Pl(ll-k) ]
`
`Pk!Pk2 • · · Pk(n-k)
`
`.
`
`!f.P = [UIU2 . .. Uk]
`
`4,623,999
`
`(I)
`
`4
`information word vector u. This portion of the informa(cid:173)
`tion word vector selects an output word of n- k parity
`bits at one of the 2xi address locations and is represented
`by the vector:
`
`[Uk-xi+ 1Uk-xi+2 · • • Uk].
`
`(7)
`
`The output of storage device 16a is provided on line
`20a and as discussed above, is an n- k bit output word.
`In particular, the XI bit vector applied to the storage
`device 16a serves to identify the output word:
`
`(8)
`
`Similarly, the output of storage device 16b is pro(cid:173)
`vided on line 20b and has the following form:
`
`(9)
`
`If each of the row vectors of the parity check matrix P
`in equation (1) is written as p'k, then the n-k parity
`check bits can be designated as:
`
`10
`
`(2)
`
`
`
`= UJP'I + U2J)'2 + · · · + UkP'k
`
`)5
`
`!f.P = [UIU2 ... Uk]
`
`P'2
`
`:
`
`P'I]
`[
`
`Pk
`
`Now, if each of the elements of the information word 20 Likewise, the output of storage device 16n is provided
`on line 20n and is represented by::
`vector u, which has 2k possible values, is partitioned as
`follows:
`
`(10)
`
`[u1u2 ... uk]=[UIU2 ... Uxi."Uxi+IUxJ+2· · · UxJ+x2:
`·· · ."Uk -xi+ I · · · Uk],
`
`then equation (2) can be written as:
`
`<3> 25
`
`!f.P = (u1p' 1 + U2J)'2 + . · . + Ux1P'x1l + (Uxl + lp'xl +I + · · · +
`
`(4)
`
`Uxl+x2P'xl+x2) + · · · + (Uk-xi+IP'k-xi+l + · · · + UkP'k)·
`
`35
`
`40
`
`As will be discussed in more detail below, the associa(cid:173)
`tion of vectors as set forth in equation (4) allows r~-
`placement of the 2kx(n-k) look-up table 10 as shown m
`FIG. 1 with 2~i<k memory devices of2xl, 2x2, ... and
`2xi address locations, respectively, where XI +x2+ ...
`+Xi=k.
`Referring now to FIG. 2, a block diagram of the
`look-up table encoder of the present invention is shown.
`In particular, the look-up table 10 of FIG. 1 is re(cid:173)
`placed by a plurality of storage devices 16a, 16b, ...
`16n. The k bit information word vector u is supplied to
`the look-up table encoder via line 12, and to the storage
`4
`devices 16a, 16b, ... 16n via the lines 18a, 18b, ... 18nxlt 5
`respectively. More specifically, storage device 16a has 2
`address locations which are addressed by an XI bit-in(cid:173)
`length portion of the information word vector u. In
`particular, the portion of the information wor~ vector
`supplied via line 18a to the storage device 16a ts repre(cid:173)
`sented by the vector:
`
`Therefore, it can be seen that when summed, the
`output words provided from the storage devices 16a,
`16b, ... 16n represent the various association of vectors
`set forth in equation (4).
`Referring back to FIG. 2, each of the output words or
`30 vectors on lines 20a, 20b, ... 20n, respectively, are then
`applied to n- k mod-2 adders represented generally by
`the symbol 22. The n- k adders 22 sum the output
`words applied thereto to form the n- k parity bits uP
`which are then output from the look-up table encoder
`via line 24. As discussed above, the n- k parity word
`bits uP are then appended to the k information word bits
`during systematic encoding of the linear block code.
`Therefore, according to the present invention associ(cid:173)
`ation of the vectors as set forth in equation (4) allows
`replacement of a 2kx(n-k) storage device with 2~i<k
`smaller storage devices of 2Xl, 2X2, ... and 2Xi address
`locations, respectively, where XI +x2+ ... +xi=k.
`Each of these storage devices receives a portion of a k
`bit information word that serves to address a respective
`location therein, thereby mapping the portion into an
`output word associated with each storage device. The
`output words are then summed in n-k mod-2 adders to
`generate a parity word associated with each informa(cid:173)
`tion word.
`In the preferred embodiment of the invention, the
`storage devices 16a, 16b, ... 16n of FIG. 2 are read-only
`memories (ROM's), or programmable read-only memo(cid:173)
`ries (PROM's) where appropriate, such devices being
`programmed with binary information defining the par-
`55 ity check matrix P unique to a given block code. It
`should also be appreciated that the amount of storage
`locations in the memory devices 16a, 16b, ... 16n may
`be equal or variable. More specifically, the values of XJ,
`x2, ... Xi may be identical or take on different values
`60 such that the number of address locations 2XI, 2X2, •.•
`2xi, respectively, for each storage device may vary. The
`only constraint on the size of these storage devices is
`that XI +x2+ ... +xi=k By way of example only, if
`k= 10, i.e., a 10 bit information word is desired to be
`transmitted, then the table look-up encoder of the pres(cid:173)
`ent invention may utilize two ROM's having 28 and 22
`address locations, respectively, or two ROM's each
`having 25 address locations, or three PROM's having 23,
`
`50
`
`[UIU2 ... UxJl
`
`(5)
`
`This portion of the information word vector addresses
`the storage device 16a to select an output word of n- k
`bits at one of the 2x1 address locations. Similarly, the
`storage device 16b having 2X2 address locations is ad(cid:173)
`dressed by a x2 bit-in-length portion of the information
`word vector u. As seen in FIG. 2, this portion of the
`information word vector selects an output word of n- k
`parity bits at one of the 2x2 address locations and is
`represented by the vector:
`
`[uxl +lUx I +2 ... Uxl +x2l
`
`(6) 65
`
`Finally, the storage device 16n having 2xi address loca(cid:173)
`tions is addressed by an Xi bit-in-length portion of the
`
`Hughes, Exh. 1027, p. 5
`
`

`
`4,623,999
`
`5
`23 and 24 address locations, respectively, and so forth. It
`can be seen therefore that the table look-up encoder of
`the present invention obviates the large memory de(cid:173)
`vices normally associated with prior art look-up
`schemes. Moreover, except for the n-k mod-2 adders,
`which are relatively inexpensive as compared to the
`cost of memory, no additional hardware is required by
`the encoder.
`Referring now to FIG. 3, a schematic diagram of a
`Golay linear block code encoder is shown which incor- 10
`porates the table look-up scheme of the present inven(cid:173)
`tion. This encoder includes two storage devices,
`(P)ROM 26 and (P)ROM 28. As seen in FIG. 3, the 12
`bit information word is separated into two portions
`having bits Do-Ds, and D6-DJ 1, respectively. The 15
`(P)ROM 26 has address inputs Ao-As for receiving the
`first portion of the 12 bit information word comprising
`bits Do-Ds. Similarly, (P)ROM 28 includes address
`inputs Ao-As for receiving the second portion of the 12
`bit information word comprising bits D6-DJJ. There- 20
`fore, in the Golay encoder of FIG. 3, two (P)ROM's are
`provided with XJ=X2=6. Referring back to FIG. 3,
`each (P)ROM 26 and 28 has eleven outputs Bo-B10
`corresponding ton-k where n=23 and k= 12. The bits
`Bo-BJO of (P)ROM 26 form a first output word, while 25
`the bits Bo-Bw of (P)ROM 28 form a second output
`word. Corresponding bits of the first and second output
`words are then mod-2 summed as discussed above with
`respect to FIG. 2 to form the respective parity bits
`Po-Pw of a parity word associated with the infmmation 30
`word. In particular, bits Bo from the (P)ROM's 26 and
`28 are mod-2 summed in the exclusiv,e-OR gate 30 to
`produce the parity bit Po of a parity word. Similarly,
`bits B1 output from the (P)ROM's 26 and 28 are mod-2
`summed in the exclusive-OR gate 32 to produce the 35
`parity bit P1, and so forth. In systematic encoding of the
`Golay linear block code, the parity bits Po-Pw are then
`appended to the information word bits Do-D11 to form
`the codewords uniquely associated with the 212 possible
`information words.
`It should be recognized that the use of two (P)ROM's
`as set forth.in FIG. 3 is simply a matter of choice. As
`discussed above, the Golay encoder ,could also have
`been formed utilizing three (P)ROM's and 22 exclusive(cid:173)
`OR gates, or alternatively 12 (P)ROM's and 121 exclu- 45
`sive-OR gates, and so forth.
`The present invention therefore provides an efficient
`look-up table encoder for linear block codes which is
`more practical and flexible than presently existing look-
`up table encoding schemes. This flexibility is provided 50
`by replacement of the standard 2kx (n- k)xl storage
`device with 2~i<k smaller storage devices of 2x1, 2x2,
`... and 2xi address locations, respectively, where
`XJ +x2+ ... +xi=k, and with n-k exclusive-OR
`gates. By way of example only, while standard look-up 55
`table encoding of a (63,45,3) BCH linear block code
`requires a plurality of large storage devices for storing
`the 245=3.5X 1QI3 entries, the present invention re(cid:173)
`quires only 5 (P)ROM's each having 29 address loca-
`tions or a total of 512 entries per (P)ROM.
`The present invention may also be used in non-sys(cid:173)
`tematic encoding of a linear block code whereby the
`first portion of the lengthened codeword does not cor(cid:173)
`respond to the information word itself. In this case, the
`entire generator matrix is utilized instead of just the 65
`parity check matrix P. Accordingly, in operation a
`portion of the k bit information word is mapped into an
`n bit output word by each 2k x n storage device, and the
`
`40
`
`6
`n bit output words are mod-2 summed to generate an n
`bit codeword.
`Moreover, the present invention is also applicable to
`the encoding of M-ary non-binary (M>2) linear block
`codes in which case each vector component represents
`a symbol comprised of log2 M bits. In a non-binary
`block code, such as a Reed-Solomon code, a plurality
`(log2 M) of bits are utilized to define galois field symbols
`in the information words. Accordingly, when the look(cid:173)
`up table encoder of the present invention is utilized to
`encode k symbol information words (each having k
`log2 M bits) with a linear error correcting non-binary
`block code, portions XJ log2 M, x2log2 M, ... , and Xi
`log2 M of the information word vector are supplied to
`the various storage devices 16a, 16b, . . . , and 16n,
`respectively, and each such portion must include an
`integral number of symbols. Specifically, all the bits
`which comprise a symbol must be applied to a respec(cid:173)
`tive storage device, and the generated output words
`also include an integral number of symbols. The struc(cid:173)
`ture of the look-up table encoder of the present inven(cid:173)
`tion is the same as shown in FIG. 2 except that the
`storage devices 16a 16b ... 16n have: 2x1 log2 M, 2x2 log2
`M, ... , and 2xi log2 M address locations, respectively.
`Finally, it should also be appreciated that the look-up
`table encoder of FIG. 2 may be utilized to effect syn(cid:173)
`drome calculation in a receiver. Specifically, as noted
`above, a decoding algorithm in the receiver calculates a
`syndrome uniquely related to an error pattern. The
`look-up table encoder of the present invention can be
`utilized at the receiver to encode corrupted received
`information bits with the linear block code, with the
`output thereof being mod-2 summed with the received
`corrupted parity word to calculate the syndrome.
`Although the invention has been described and illus(cid:173)
`trated in detail, it is to be clearly understood that the
`same is by way of illustration and example only and is
`not to be taken by way of limitation. The spirit and
`scope of this invention are to be limited only by the
`terms of the appended claims.
`I claim:
`1. A look-up table encoder for encoding a k bit infor(cid:173)
`mation word with a linear error correcting block code
`to generate an n-k bit parity word, where nand k are
`positive integers, comprising:
`a plurality of storage means respectively having 2x1,
`2x2, ... , and 2xi address locations, where i= 1,2,3 .
`.. and XJ +x2+ ... +x1 =k, each of said address
`locations storing an output word having n-k bits;
`means for applying a portion of the k bit information
`word to each of said storage means, said portion
`serving to address a respective location therein to
`map the portion into an output word stored at the
`respective location; and
`means for summing the output words from said plu(cid:173)
`rality of storage means on a bit position-by-bit posi(cid:173)
`tion basis to generate the parity word associated
`with said information word.
`2. The look-up table encoder as described in claim 1
`wherein each of said storage means is a read-only mem(cid:173)
`ory.
`3. The look-up table encoder as described in claim 1
`wherein x1=X2= ... =Xi.
`4. The look-up table encoder as described in claim 1
`wherein XF;i=X2* ... *Xi.
`5. The look-up table encoder as described in claim 1
`wherein XJ =X2= ... =/=Xi.
`
`60
`
`Hughes, Exh. 1027, p. 6
`
`

`
`4,623,999
`
`7
`6. The look-up table encoder as described in claim 1
`wherein said means for summing includes n-k exclu(cid:173)
`sive-OR gates for receiving corresponding bits of said
`output words from said plurality of storage means.
`7. The look-up table encoder as described in claim 6
`wherein each of said n- k exclusive-OR gate generates
`a bit of said parity word.
`8. A look-up table encoder for encoding a k bit infor(cid:173)
`mation word with a linear error correcting block code
`to generate an n- k bit parity word, where n and k are 10
`positive integers, comprising:
`a plurality of programmable read-only memories
`respectively having 2XI, 2X2, ... ' and 2Xi address
`locations, where i= 1,2,3 ... and XJ +x2+ ...
`+x1 =k, each of said address locations storing an 15
`output word having n-k bits;
`means for applying a portion of the k bit information
`word to each of said programmable read-only
`memories, said portion serving to address a respec(cid:173)
`tive location therein, to map the portion into an 20
`output word having n- k output bits; and n- k
`exclusive-OR gates for summing the output words
`from said programmable read-only memories on a
`bit position-by-bit position basis to generate the
`parity word associated with said information word. 25
`9. The look-up table encoder as described in claim 8
`wherein x1=X2= ... =Xi·
`10. The look-up table encoder as described in claim 8
`wherein XJ::f=X2::f= ... ::f=xi.
`11. The look-up table encoder as described in claim 8 30
`wherein XJ=X2= ... ::f=xi.
`12. The look-up table encoder as described in claim 8
`wherein each of said n- k exclusive OR gates generates
`a bit of said parity word.
`13. A look-up table encoder for encoding a k bit 35
`information word with a linear error correcting block
`code in non-systematic form to generate an n- k bit
`
`8
`parity word, where n and k are positive integers, com(cid:173)
`prising:
`a plurality of storage means respectively having zxl,
`2X2, ... ' and 2Xi address locations, where i = 1,2,3 .
`.. and where XJ +x2+ ... +xi=k. each of said
`address locations storing an n bit output word;
`means for applying a portion of the k bit information
`word to each of said storage means, said portion
`serving to address a respective location therein to
`map the portion into an output word stored at the
`respective location; and
`means for summing the n bit output words from said
`plurality of storage means on a bit position-by-bit
`position basis to generate the n bit codeword asso(cid:173)
`ciated with said information word.
`14. A look-up table encoder for encoding a k symbol
`information word with a linear error correcting M-ary
`(M>2) non-binary block code to generate a parity
`word, wherein groups of log2 M bits are used to define
`symbols in said information word, comprising:
`a plurality of storage means respectively having 2x1
`log2 M, 2 x2 log2M, .•• , and 2Xi log2 M address locations,
`where i= 1,2,3 ... and X! +x2+ ... +xi=k, each
`of said address locations storing an output word;
`means for applying a portion of the k symbol informa(cid:173)
`tion word to each of said storage means, the por(cid:173)
`tion including an integral number of said symbols
`and serving to address a respective location therein
`to map the portion into an output word stored at
`the respective location, the output word having an
`intergral number of said symbols; and
`means for summing said output words for said plural(cid:173)
`ity of storage means on a symbol position-by-sym(cid:173)
`bol position basis to generate the parity word asso(cid:173)
`ciated with said information word.
`* *
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Hughes, Exh. 1027, p. 7