United States Patent
`
`[191
`
`[11] Patent Number:
`
`4,907,233
`
`[45] Date of Patent:
`Deutsch et al.
`Mar. 6, 1990
`
`[54] VLSI SINGLE-CHIP (255,223)
`REED-SOLOMON ENCODER WITH
`INTERLEAVER
`
`[75]
`
`Inventors: Leslie J. Deutsch, Sepulveda;
`In-Shek Hsu; Trieu-Kie Truong, both
`of Pasadena; Irving S. Reed, Santa
`Monica, all of Calif.
`The United States of America as
`represented by the Administrator of
`the National Aeronautics and Space
`Administration, Washington, D.C.
`
`[73] Assignee:
`
`[21] Appl. No.: 195,226
`
`[22] Filed:
`
`May 18, 1988
`
`mance of Concatenated Codes,” Jet Propulsion Labora-
`tory, Pasadena, California, Sep. 1, 1981.
`R. F. Rice, “End-to-End Image Information Rate Ad-
`vantages of Various Alternative Communication Sys-
`tems,” Publication 82-61, Jet Propulsion Laboratory,
`Pasadena, California, Sep. 1, 1982.
`E. R. Berlekamp, “Bit—Serial Reed—Solomon Encod-
`ers,” IEEE Trans. Inform. Theory, vol. IT-28, No. 6,
`pp. 869-874, Nov. 1982.
`I. S. Hsu, I. S. Reed, T. K. Truong, K. Wang, C. S. Yeh
`and L. J. Deutsch, “The VLSI Implementation of a
`Reed—Solomon Encoder Using Berlekamp’s Bit—Serial
`Multiplier Algorithm”, IEEE Trans. on Computers,
`vol. C-33, No. 10, Oct. 1984.
`
`Int. Cl.4 ............................................ .. G06F 11/03
`[51]
`[52] U.S. Cl. ................................ .. 371/37.4; 371/38.1;
`371/39.1; 371/41; 371/43
`[58] Field of Search ....................... 371/37, 38, 39, 40,
`371/41, 43, 44, 45
`
`Primary Examiner—Jerry Smith
`Assistant Exam[ner—Stephen M. Baker
`Attorney, Agent, or Fz’rm——Thomas H. Jones; John R.
`Manning; Charles E. B. Glenn
`
`[57]
`
`ABSTRACT
`
`A concatenated coding system consisting of a (255,223)
`Reed-Solomon outer code and a convolutional inner
`code is provided with either a block of preinterleaved
`frames or an interleaver of frames in a block of data
`symbols to be coded in the outer decoder. By interleav-
`ing, errors are constrained to occur in only one symbol
`in a frame, which can be corrected by the Reed-Solo-
`mon outer decoder. After transmission and inner decod-
`ing, the data symbols are deinterleaved for outer decod-
`ing. Instead of preinterleaving at the source, or inter-
`leaving before inner encoding, the frames of data sym-
`bols may be interleaved at the receiver after inner de-
`coding and then combined with the inner decoded
`check symbols for outer decoding. The outer encoder is
`a bit-serial Reed-Solomon encoder with programmable
`interleaving, and the inner decoder is a Viterbi decoder.
`
`4 Claims, 6 Drawing Sheets
`
`[56]
`
`References Cited
`. U.S. PATENT DOCUMENTS
`
`8/1974 Trafton ............................... .. 371/39
`3,831,143
`3,988,677 10/1976 Rice et al.
`.
`371/40
`4,162,480
`7/1979 Berlekamp
`.371/37
`4,410,989 10/1983 Berlekamp
`. 371/40
`4,649,541
`3/1987 Lahmeyer ............................. 371/37
`OTHER PUBLICATIONS
`
`
`
`Odenwalder, Joseph P., “Concatenated Reed—Solo-
`mon/Viterbi Channel Coding for Advanced Planetary
`Missions: Analysis, Simulations, and Tests”, Jet Propul-
`sion Laboratory, Dec. 1, 1974.
`IEEE Communications Magazine, Berlekamp, E., et al,
`“The Application of Error Control
`to Communica-
`tions”, vol. 25, No. 4, Apr. 1987, pp. 44-57.
`Lin et al., “Error Control Coding”, Prentice Hall, Inc.,
`pub., 1983, Pp. 271-272, 535-538.
`R. L. Miller, L. J. Deutsch and S. A. Butman, “On the
`Error Statistics of Viterbi Decoding and the Perfor-
`
`22
`‘
`— — — ‘ ‘ ‘ ’ ‘I
`QUOTIENT UNIT 4
`
`23
`
`PRODUCT
`UNIT
`
`'
`
`REMAINDER AND
`INTERLEAVER UNIT
`
`(FIG. 3)
`
`ERICSSON EXHIBIT 1006
`
`
`
`
`CONTROLUNIT
`
`CLK
`
`LM
`
`

`
`U.S. Patent
`
`1...
`
`6
`
`4,907,233
`
`
`
` __mm._%m.,.fiMnwmmwwxwoomy._mzz<:o._<zo_S._o>zoomm><u._fi.:.z_zos_o..omBummowmmmmm.__o_
`
`
`
`
`._.IIII|I|||lII|...llll||lIlII..._
`
`,m9¢_m.
`
`_mE.:>._mzz<:o_mooofizz.-_Sxza«:3zo.2o._omSumnunw.mmaoomoEcomaohuoooE50mm><m..mmFz_
`
`
`
`
`
`
`
`
`
`
`C.m_<mo_mn:_OE
`
`
`

`
`U.S. Patent Mar. 6, 1990
`
`Sheet 2 of6
`
`4,907,233
`
`mm
`
`52.05
`
`._._2_...
`
`
`
`._._ZDmm_><u._mm.ez_
`
`az<muoz_<2um
`
`8.9“:
`
`m.©_n_
`
`mu
`
`rNIIIIII.IIwu:2...
`pzmfioao
`
`.L|Nfl 'IOHJ.NOO
`
`x._o
`
`S...
`
`
`

`
`US. Patent Mar. 6,1990
`
`Sheet 3 of6
`
`4,907,233
`
`T3:
`
`T30
`
`Tl
`
`To
`
`d
`
`0
`
`I
`
`3:
`
`I
`
`so
`
`I
`
`I
`
`TI
`.
`H H TURN,
`H H
`K.K.—.K.1l$.. T2
`N0.
`
`1.L_;._.!EI. T
`
`No-
`
`K.K._.K.1E. Ts
`
`$191.5“ [1
`.?IEI.|...'“J.E* ::
`Eifii
`gig
`
`No-
`
`TURN 4
`No-
`
`FIG. 3
`
`

`
`U.S. Patent Mar. 6, 1990
`
`Sheet 4 of 6
`
`4,907,233
`
`FIG.4‘
`
`CLK
`
`START
`
`DOUT
`
`

`
`US. Patent Mar. 6, 1990
`
`Sheet 5 of 6.
`
`%
`
`4,907,233
`
`dzz<_..o
`4<.zo_S..o>zoo
`
`moooE22.
`
`mmooozm
`
`.
`
`__
`
`mm><m._mm:z_J
`
`zos_o._omBum
`
`
`
`mooo~m_So
`
`mmooozm
`
`momaom
`
`4.2..
`
`
`
`
`
`IIIII|nu|n..l.I.I||.l.|||.||I.|.|lIll||.|I||l||.|Il|IlluII||.IL_.
`
`__
`
`
`
`mmooouoV
`
`Eooomo
`
`v_z_m<...<ozos_o._cmBum_$mE>.mzz<_._o_
`
`
`
`
`moooE5088E22.AIIIIIIIIJ
`
`HHH
`
`2.1
`
`
`
`
`
`
`
`

`
`U.S. Patent Mar. 6, 1990
`
`Sheet 6 of 6
`
`4,907,233
`
`
`
`..<zo_.S..o>zoo38E22...m_zz<:o
`
`
`
`mmoouzm
`
`om><m._mEz_
`
`xzaE3.
`
`<29
`
`mm_><u._mEzm_n_
`
`<._.<n_
`
`mm><m._mmFz_
`
`<._.<o
`
`mcoo0amooomommM000
`
`m._oms_>mxomxo
`
`zos_o._omBum
`
`m_m._.DO
`
`3><.u.._mm.rz_
`
`mooommzz.
`
`mmooomo
`
`_.m._E:>
`
`M58550
`
`mmooozu
`
`mOE
`
`
`
`zos_3omSum<._.<a
`
`momzom
`
`
`
`
`
`
`

`
`1
`
`4,907,233
`
`VLSI SINGLE-CHIP (255,223) REED-SOLOMON
`ENCODER WITH INTERLEAVER
`
`ORIGIN OF THE INVENTION
`
`The invention described herein was made in the per-
`formance of work under a NASA contract, and is sub-
`ject to the provisions of Public Law 96-517 (35 USC
`202) in which the Contractor has elected not to retain
`title.
`
`TECHNICAL FIELD
`
`The invention relates to a concatenated Reed-
`Solomon/convolutional encoding system consisting of
`a Reed-Solomon outer code and a convolutional inner
`code for downlink telemetry in space missions, and
`more particularly to a Reed-Solomon encoder with an
`interleaving capability of the information symbols and
`code correcting symbols in such a concatenated encod-
`ing system.
`
`BACKGROUND ART
`
`In the field of space communications, a convolutional
`code has been used by NASA’s Voyager project for
`greater reliability in transmission of information. A
`Reed-Solomon (RS) code has also been used as a cyclic
`symbol error correcting code. And finally, a concate-
`nated Reed-Solomon/convolutional encoding system
`has been adopted by the European Space Agency, Na-
`tional Aeronautics and Space Administration, and the
`Jet Propulsion Laboratory for the deep-space down-
`link. The performance of such a concatenated code
`scheme has been investigated by R. L. Miller, L. J.
`Deutsch and S. A. Butman, “On the Error Statistics of
`Viterbi Decoding and the Performance of Concate-
`nated Codes,” Jet Propulsion Laboratory, Pasadena,
`Calif., Sept. 1, 1981. It is shown that this concatenated
`channel provides a coding gain of almost 2 dB over a
`channel using only the convolutional code at a decoded
`bit error rate of 10-5.
`One of the benefits of concatenated coding, and one
`of the main motivations for its adoption as a standard
`system, is that it provides for nearly error free commu-
`nication links at fairly low signal power levels. This
`means that source data compression techniques can be
`used to help increase channel throughput without a
`substantial change in overall error rate. Data compres-
`sion algorithms, while promising to remove substantial
`information redundancy are very sensitive to transmis-
`sion errors. Study of a system using concatenated cod-
`ing with data compression can be "found in R. F. Rice,
`“End-to-End Image Information Rate Advantages of
`Various Alternative Communication Systems,” Publi-
`cation 82-61, Jet Propulsion Laboratory, Pasadena,
`Calif., Sept. 1, 1982.
`A Reed-Solomon code is basically a polynomial code
`first presented in a paper by Irving S. Reed, et al.,
`“Polynomial Codes Over Certain Finite Field,” J. Soc.
`Industr. Appl. Math, Vol. 8, No. 2, pp. 300—304, June,
`1960. For encoding,
`it
`is implemented by a circuit
`which performs polynomial division in a finite field. See
`U.S. Pat. No. 4,162,480 to Elwyn R. Berlekamp titled
`“Galois Field Computer.” The major problem in de-
`signing a small encoder is the large quantity of hard-
`ware that is necessary. A conventional encoder for the
`(255, 223) RS code requires 32 finite field multipliers
`usually implemented as full parallel or table look-up
`multipliers. The use of either prohibits the implementa-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`tion of the encoder on a single medium density VLSI
`Chip.
`'
`Fortunately E. R. Berlekamp, “Bit-Serial Reed-Solo-
`mon Encoders,” IEEE Trans. Inform. Theory, Vol.
`IT-28, No. 6, pp. 869-874, November 1982, describes a
`serial algorithm for finite field multiplication over a
`binary field. Berlekamp’s algorithm requires only shift-
`ing and exclusive-OR operation. See also U.S. Pat. No.
`4,410,989 titled “Bit Serial Encoder” to Berlekamp,
`Both references are incorporated herein by reference.
`Recently, it has been known that this multiplication
`algorithm makes possible the design of a workable
`VLSI architecture and that a new dual-basis (255, 223)
`RS encoder can be realized readily on a single VLSI
`chip with NMOS technology. See I. S. Hsu, I. S. Reed,
`T. K. Truong, K. Wang, C. S. Yeh and L. J. Deutsch,
`“The VLSI Implementation of a Reed-Solomon En-
`coder Using Berlekamp’s Bit-Serial Multiplier Algo-
`rithm,” IEEE Trans. on Computers, Vol. C-33, No. 10,
`October 1984. This technical paper is also incorporated
`herein by reference.
`In a concatenated coding system, inner decoder er-
`rors may occur in bursts, which are occasionally as long
`as several constraint lengths. The outer RS decoder
`remains undisturbed by errors which occur within a
`given 8-bit symbol (about one constraint length of the
`convolutional inner code). However, performance of
`the RS decoder is degraded by longer burst errors, i.e.,
`errors occurring among successive symbols, as may
`occur in the operation of the inner decoder. As a conse-
`quence, interleaving the RS outer code is required for
`best performance,
`i.e., for preventing or minimizing
`correlated errors among successive symbols in the
`Viterbi inner decoder, as has been studied and reported
`by Joseph P. Odenwalder in a Final Report distributed
`by Linkabit Corporation of San Diego, Calif., under a
`contract for Jet Propulsion Laboratory dated Dec. 1,
`1974,
`titled
`“Concatenated Reed-Solomon/Viterbi
`Channel Coding for Advanced Planetary Missions:
`Analysis, Simulations and Tests.”
`The concatenated coding system block diagram con-
`sidered in that report included a symbol interleaving
`buffer in the transmitter and a symbol deinterleving
`buffer at the receiver generalized by FIG. 1 in this
`application. Interleaving is defined as dispersing the
`original sequence of symbols in an RS codeword or
`frame in a block of frames by reordering the sequence to
`include in the block the first symbol of every frame in
`the block followed by the second, third, etc., until all
`symbols of the block have been included. Deinterleav-
`ing is simply the inverse process. However, the process
`of interleaving would require too many components to
`be feasible for implementation on a single VLSI chip
`where that is required, that is in a system for communi-
`cation from a spacecraft or a compact disk recorder,
`both of which may have a need for small size and/or
`weight, and high throughput which cannot tolerate the
`delays introduced by long leads interconnecting many
`chips.
`
`STATEMENT OF THE INVENTION
`
`_ Accordingly, it is an object of the invention to pro-
`vide an architecture for a Reed-Solomon encoder with
`interleaving for a concatenated Reed-Solomon/convo-
`lutional encoding system that minimizes the compo-
`nents required.
`
`

`
`4,907,233
`
`-
`
`10
`
`25
`
`30
`
`35
`
`3
`A further object is to provide an interleaving RS
`encoder with a programmable depth of interleaving.
`These and other advantages are achieved in accor-
`dance with the present
`invention in a concatenated
`Reed-Solomon/convolutional
`encoding
`system by 5
`preinterleaving information symbols received from a
`data source grouped into frames of, for example, 223
`data symbols, and generating 32 check symbols in a
`Reed-Solomon encoder, or alternatively interleaving
`frames of information symbols to match the interleaving
`of the check symbols generated, either before encoding
`with a convolutional inner code prior to transmission
`through a channel, or after using a Viterbi decoder on
`the convolutional inner code at the receiver. In any of
`the alternatives, after convolutional inner code encod- 15
`ing,
`the concatenated Reed-Solomon/convolutional
`encoded information symbols are transmitted.
`Interleaving of information symbols and of check
`symbols is achieved by entering N associated groups of
`each, such as N frames of 223 information symbols each 20
`and of 32 associated check symbols, in two sets of N
`registers in a column, one set for the information sym-
`bols, and the other set for the associated check symbols,
`and then reading out vertically for transmission of the
`first symbol of information in every register of the first
`set and second set, then the second symbol in every
`register, etc., until all of the symbols have been inter-
`leaved and transmitted. The process of convolutional
`inner code encoding of the interleaved symbols is then
`followed for transmission to a receiver in the usual
`manner. Instead of interleaving the information symbols
`at the transmitter, it is preferred to preinterleave the
`information symbols at the data source, or to interleave
`only the check symbols at the transmitter and interleave
`the data symbols after the Viterbi inner decoder at the
`receiver, to match the interleaving of the check sym-
`bols. These two preferred alternatives have the advan-
`tage of requiring the minimum that need be included in
`a VLSI chip at the transmitter. In any case, the RS
`outer code encoded symbols must then be deinterleaved
`at the receiver for decoding. In the case of interleaving
`at the receiver, the process of interleaving is inverted to
`deinterleave after RS outer code decoding. The re-
`ceiver will normally be on the ground where space and
`weight is not a factor to be considered so that it is feasi-
`ble to have both interleaving and deinterleaving at the
`receiver.
`The novel features that are considered characteristic
`of this invention are set forth with particularlity in the
`appended claims. The invention will best be understood
`from the following description when read in connection
`with the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`4
`information symbols as shown and an interleaver for
`parity check symbols implemented in the same manner
`as shown in FIG. 3 for the embodiment of FIG. 2, and
`a deinterleaver for information and check symbols that
`is the inverse of the interleaver for information symbols.
`FIG. 6 illustrates yet another alternative embodiment
`of the present invention which sifts the burden of data
`interleaving and deinterleaving to the receiver.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`A prior art block diagram of a concatenated coding
`system with interleaving is shown in FIG. 1 as having at
`the transmitter a Reed-Solomon outer code encoder 10,
`interleaver 11, and a convolutional inner code encoder
`12, and at the receiver an inner code decoder 13, dein-
`terleaver 14 and Reed-Solomon outer code decoder 15.
`The inner code decoder 13 at the receiver constitutes a
`Viterbi (maximum likelihood) decoder. The RS outer
`code encoder 10 and decoder 15 use a high rate block
`code. It is demonstrated by Miller, et al., supra, that this
`concatenated channel provides more than 2 dB of cod-
`ing gain over the convolutional-only channel. How-
`ever, the performance of the recommended Reed-Solo-
`mon coding scheme in the concatenated coding system
`can only be achieved when the bursts of errors appear-
`ing at the output of the Viterbi inner code decoder 13
`are dispersed in such a manner that the RS symbols at
`the input of the outer decoder 15 are randomized suffi-
`ciently.
`Before describing the first embodiment of this inven-
`tion, the process of interleaving will be described with
`reference to the following table.
`
`Registers For
`SEQUENTIAL
`FRAME
`Information
`Registers For
`
`STORE
`Symbols
`Check Symbols
`—>
`Frame #1
`A l,2,...,223
`A l,...,32
`Frame #2
`B 1,2,. ..,223
`B l,
`.
`.
`. ,32
`
`—»
`
`Frame #5
`READ
`INTER-
`LEAVED
`FRAMES
`
`E l, .
`
`.
`
`. ,223
`
`E l,
`
`.,32
`
`l...l
`
`J,...l
`
`The frames of symbols (five in this example) are
`grouped together forming one block. The scheme of
`interleaving five frames in a block of symbols from the
`RS outer code encoder 10 is referred to as interleaving
`to a depth of five frames. Assuming the numbers used in
`the table above represent a block of five frames of 223
`information symbols plus 32 parity check symbols per
`frame, and the letters represent the association of the
`registers for the two sets of 223 and 32 associated sym-
`bols,
`it is evident that as information symbols are re-
`ceived,
`the parity check symbols generated are also
`stored in the same sequence of registers corresponding
`to the data registers. The process of interleaving and
`deinterleving follows in a coordinated manner using
`two blocks of registers, one for the information symbols
`processed to generate parity check symbols, and one for
`the check symbols generated. Once the information
`symbols are received sequentially, frame by frame, for
`example 5 frames, and stored in shift registers, and
`check symbols are generated frame by frame and stored
`in the second set of shift registers, they may be read out
`
`40.
`
`45
`
`50
`
`55
`
`FIG. 1 illustrates in a general block diagram the prior
`art of the present invention.
`FIG. 2 illustrates a block diagram of a (255, 223) RS
`encoder having a remainder and an interleaver unit for
`a Reed-Solomon encoder embodying the present inven-
`tion of interleaving parity check symbols generated for
`block information symbols.
`FIG. 3 illustrates a block diagram of the remainder
`and interleaver unit of FIG. 2.
`FIG. 4 is a timing diagram for control signals used in
`the synchronous bit-serial multiplication algorithm of 65
`the RS encoder shown in FIG. 2.
`FIG. 5 illustrates in a block diagram the organization
`of an alternative embodiment having an interleaver for
`
`60
`
`

`
`4,907,233
`
`5
`sequentially across (vertically) as shown in the above
`table.
`Thus, as the information to be transmitted is received
`from a data source, the RS outer code encoder 10 pro-
`cesses the input data and outputs the RS code frames
`containing 255 symbols (223 information symbols and
`32 check symbols). Each code frame of 255 symbols
`may be preinterleaved, or interleaved by storing in
`separate sets or banks of registers, two registers for each
`depth of interleaving, here shown as five, one set of
`registers for the information symbols, and the other set
`of register for the generated code symbols. The five
`code frames of 255 symbols form a block. Once the
`block of code words are stored, they are read out seri-
`ally by column Al, B1,. .., B1; A2, B2, .
`.
`.
`, E2; A3,
`B3, .
`.
`.
`, E3; etc., until all five code frames have been
`transmitted to the inner code encoder 12. That consti-
`tutes a block of interleaved RS coded data transmitted.
`In the case of having preinterleaved data from the
`source, the interleaver 11 simply generates the check
`symbols for the interleaved data in an interleaved form,
`as will be described for the preferred embodiment with
`reference to FIG. 2.
`As a result of this interleaving, a burst error event of
`the Viterbi decoder 13 will tend to affect only one sym-
`bol of each frame depending on the length of the burst
`and the number of rows in each interleaving array of
`registers. This number of rows has been defined as the
`interleaving depth, shown as five in the table, but in the
`preferred embodiment described below with reference
`to FIG. 3, the interleaving depth is programmable to be
`from 2 to 5.
`Berlekamp’s bit—serial multiplication algorithm for a
`(255, 223) RS encoder over GF (23) is presented by Hsu,
`et al., supra. A block diagram of the (255, 223) RS en-
`coder of that paper is shown in FIG. 2 with the pro-
`grammable interleaving depth shown in FIG. 3. The
`circuit of FIG. 2 is divided into five units: control unit
`21, quotient unit 22, product unit 23, input/output (I/O)
`unit 24, and a remainder and interleaver unit 25, which
`contains storage for the remainder out of the product
`unit 23 for interleaved parity check symbols. The use of
`the remainder storage alone is explained in detail in Hsu,
`et al., for the special case of an interleaving depth of
`one; what is new in this embodiment is the feature of
`providing the remainder storage in the remainder and
`interleaver unit 25 differs from that in the paper by Hsu,
`et al., in that an interleaving function is included. Conse-
`quently, the unit 25 is called the “remainder and inter-
`leaver unit.”
`Before describing the remainder and interleaver unit
`15 shown in FIG. 3, the architecture designed to realize
`a (255, 223) RS encoder using Berlekamp’s multiplier
`algorithm will first be described with reference to FIG.
`2, assuming that the depth of interleaving is one, i.e.,
`assuming no interleaving. This description is taken from
`the paper by Hsu, et al., supra, at pp. 908, 909.
`An RS code is a block sequence of Galois field sym-
`bols. Each symbol is a field element in GF(2"') where
`GF(2'") denotes the finite field of 2”‘ binary symbols.
`This sequence of symbols can be considered to be the
`— coefficients of a polynomial. The code polynomial C(x)
`of such a code is C(x)=co+c1x+ .
`.
`. +c,,_1x"-1
`where c,-eGF(2’").
`The parameters of an R5 code are summarized as
`follows:
`m=number of bits per symbol;
`n=2"'—l=the length of a codeword in symbols;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`4-5
`
`50
`
`55
`
`60
`
`65
`
`6
`t=maximum number of error symbols that can be
`corrected;
`d = 2t+ 1 = design distance;
`2t=number of check symbols;
`k=n—-2t=number of information symbols.
`In the example of the present invention, m=8, n=255,
`t=16, d=33, 2t=32, and k=223. This is the (255,233)
`RS code. This particular code is capable of correcting a
`maximum of 16 symbol errors or 32 erasures.
`The generator polynomial of an RS code is defined
`by *
`
`x =
`gm
`
`2:’J'=b
`
`2t
`.
`.
`(x-~/>=,,gOg.x'
`
`l
`O
`
`where b is a nonnegative integer, often chosen to be 1,
`and 'y is a primitive element in GF(2"'). In order to
`reduce‘ the complexity of the encoder, it is desirable to
`make the coefficients of g(x)
`symmetric so that
`g(x)=x*d-1g(l/x). To accomplish this b must be
`chosen to satisfy 2b+d—-2=2'"—l. Thus,
`for
`the
`(255,223) RS code, b=1l2.
`. +c,,_1x"-1 and
`.
`Let I(x)=c2,x2’+c2,+1x2‘+1+ .
`P(x)=co+c1x+ .
`.
`. +cz,_1x2’—1 be the information
`polynomial and the check polynomial, respectively.
`Then the encoded RS code polynomial is represented
`by
`
`C(x)=I(x)+P(x)
`
`(2)
`
`To be an RS code C(x) must be also a multiple of g(x).
`That is, C(x)=q(x)g(x). The encoding process is to find
`P(x) from I(x) and g(x). This is achieved by the division
`algorithm. Dividing I(x) by g(x) yields
`
`I(x)=q(x)g(x)+r(x)»
`
`(3)
`
`then q(x)g(x)=I(x)—y(x-
`If one lets P(x)= —y(x),
`)=I(x)+P(x)=C(x). Hence, C(x) is given by Equation
`(2) where P(x)= —r(x).
`Thus, the RS encoder of FIG. 2 performs the above
`division process to obtain the check polynomial P(x),
`where FIG. 3 illustrates a block diagram of the inter-
`leaver for the check symbols with the programmable
`depth of interleaving assumed to be set to one, and FIG.
`4 illustrates in a timing diagram the required control
`signals. In FIG. 2, R for O§i§2t—-2 and Q are m-bit
`registers. Initially, all registers are set to zero, and a
`control signal SL applied to gates G2 and G4 establish a
`first condition A.
`, cz, are fed into
`.
`.
`The information symbols c,,_1, I
`the quotient unit (division circuit) 22 of the encoder and
`also transmitted by the I/O unit from the encoder one
`under this first condition A by one. The quotient coeffi-
`cients are generated and loaded into the Q register se-
`quentially. The remainder coefficients are computed
`successively. Immediately after cg, is fed to the circuit,
`the control signal SL is set to turn off gates G2 and G4
`and turn on gates G3 and G5 for a second condition B.
`At the very same moment c2,_1 is computed and trans-
`mitted. Simultaneously, c,- is computed and loaded into
`register R for 0§i§2t—2. Next, c2,_2,
`.
`.
`.
`, co are
`transmitted from the encoder one by one. cg,_2, .
`.
`. , Co
`retain their values because the content of Q is set to zero
`when the upper gate G4 is turned off to turn on gate G5
`in the second condition B.
`The complexity of the design of an RS encoder re-
`sults from the computation of the products zg; for
`
`

`
`4,907,233
`
`7
`0§i§2t— 1. These computations can be performed in
`several ways, but none of them is suited to the pipeline
`processing structures usually seen in VLSI design. For-
`tunately, Berlekamp has disclosed a bit-serial multiplier
`algorithm that has the features needed to solve this 5
`problem. See his paper “Bit-serial Reed-Solomon en-
`coders,” IEEE Trans. Inform. Theory, Vol. IT-28, No.
`6, pp. 869-874, November 1982, cited above. In this
`invention, Berlekamp’s method is applied to the design
`of a (255,223) RS encoder with interleaving which can
`be implemented on a single VLSI chip.
`In order to understand Berlekamp’s multiplier algo-
`rithm, some mathematical preliminaries are needed.
`Toward this end,
`the mathematical concepts of the
`trace and a complementary (or dual) basis are intro-
`duced.
`Definition 1: The trace of an element B belonging to
`GF(p'"), the Galois field of pm elements, is defined as
`follows:
`
`m—1
`W = .2. B”
`
`k
`
`In particular, for p=2,
`
`me) = E01 52*
`
`The trace has the following properties:
`(1) [Tr(,8)P=B+,8P+ .
`.
`. +BP’"‘1=Tr(,8) where Be
`GF(p’"). This implies that Tr(/3) e GF(p), i.e., the
`trace is in the ground field GF(p);
`(2) T1‘(i3+’>')=Tr(/3)+Tr(7): Where /3. ‘Y6 GF(P’");
`(3) Tr(c/3)=cTr(,8) where c e GF(p);
`(4) Tr(1)Em(mod p).
`Definition 2: A basis {W} in GF(p"') is a set of m
`linearly independent elements of GF(p'").
`Definition 3: Two bases {uj} and {M} are said to be
`complementary or the dual of one another if
`
`25
`
`30
`
`35
`
`1,
`
`Trfujhk) ={O
`
`if _/'=k
`j¢k
`
`(5)
`
`45
`
`The basis {p._,-} is called the original basis, and the basis
`{M} is called the dual basis.
`Lemma: If a is a root of an irreducible polynomial of 50
`degree In in GF(p”'), then {ak} for 0§k§m—1 is a
`basis of GF(p"'). The basis {ak} for O§k§m—l
`is
`called the normal or natural basis of GF(pm).
`Theorem 1: Every basis of a Galois field over GF(2)
`has a complementary basis.
`Corrolary 1: Suppose the bases {W} and {M} are
`complementary. Then a field element 2 can be ex-
`pressed in the dual basis {M} by the expansion
`
`55
`
`m——-1
`z= 2
`
`m — l
`
`2/Jsk = kio TV(ZP-k)7\k
`
`60
`
`(6)
`
`where zk=Tr(zp.k) is the kth coefficient of the dual
`basis.
`Proof: Let z=zo7to+z1>t1+ .
`
`. +z,,,_1}t,,,_1. Multi-
`
`.
`
`65
`
`ply both sides by cck and take the trace. Then by Defini-
`tion 3 and the properties of the trace
`
`10
`
`20
`
`Tr(za/‘) = Tr (mi 1 z,(>.,p;,) J: zk Q.E.D.
`i=0
`
`This corollary provides a theoretical basis for the new
`RS encoder algorithm.
`For a more complete description. of the Berlekamp
`bit-serial multiplier, refer to Berlekamp’s paper, supra.
`The paper of Hsu, et al., supra, uses a simple example to
`illustrate the operation of Berlekamp’s bit-serial multi-
`plier algorithm. Both papers are incorporated herein by
`reference. The architecture of FIG. 2 is designed to
`implement a (255, 223) RS encoder using Berlekamp’s
`multiplier algorithm, which can be quite readily real-
`ized on a single NMOS VLSI chip.
`The main function of the encoder with a remainder
`and interleaver unit 15 will not be described. CLK is a
`clock signal, which in general is a periodic square wave.
`The information symbols are fed into the chip from the
`data-in pin DIN, bit by bit, and in interleaved sequence
`A1, B1. .
`. B1; A2, B2, .
`.
`. E2; A223, B223,
`.
`.
`. E223. Simi-
`larly, the encoded check symbols out transmitted out
`from the data-out pin DOUT in interleaved sequence
`A1, B1,
`.
`.
`. E1; A2, B2,
`.
`.
`. E2; A32, B32,
`.
`.
`. E32. The
`control signal load mode (LM) is set to logic 1 while the
`information symbols are loaded bit by bit. Otherwise,
`LM is set to O.
`
`The input data and LM signals are synchronized by
`the CLK signal, while the operations of the circuit and
`output data signal are synchronized by two nonoverlap-
`ping clock signals qbl and 4>2 generated in a control unit
`21. The timing diagram of DIN, LM, CLK, ¢1,
`(1)2,
`START, and DOUT signals are shown in FIG. 4. The
`delay of DOUT with respect to DIN is due to the input
`and output flip-flops, F1 and F0. The circuit in FIG. 2 is
`divided into four units besides the control unit 21.
`Each unit is discussed in the following:
`(1) Quotient Unit: In the quotient unit 22 Q is a 7-bit
`shift register with reset. R represents an 8-bit buffer
`register with feedback Tfand parallel load. The parallel
`load operation of R is controlled by a load control sig-
`nal LD. Registers R and Q store the currently operating
`coefficient and the next coefficient of the quotient poly-
`nomial, respectively. z,~for O§i§7 are loaded into regis-
`ter R every eight clock cycles. Immediately after all 223
`information symbols have been fed into the circuit, a
`control signal SL changes to logic 0. Thenceforth, the
`contents of the registers Q and R are set to zero so that
`the check symbols generated in the product unit 23 in
`cooperation with the remainder unit 25 sustain their
`values in the remainder unit which also provides the
`important interleaving function.
`(2) Product Unit: The product unit 23 is used to com-
`pute T/, T31, .
`.
`.
`, To. This circuit is realized by a pro-
`grammable logic array (PLA) circuit. Since To=T31,
`T1=T3o, .
`.
`.
`, T15=T17, only Tf, T31, .
`.
`.
`, T17 and T15
`are actually implemented in a standard PLA circuit. To,
`.
`.
`.
`, T15 are connected directly to T31, .
`.
`. , T17, respec-
`tively. A standard PLA circuit has the advantage over
`other circuits of being easy to reconfigure.
`(3) Remainder Unit: The remainder unit 25 without
`interleaving is used to store the coefficients of the re-
`mainder during the division process. In FIG. 3, S; for
`0§i_—<_3l are 8-bit shift registers with reset. Addition in
`the circuit is a modulo 2 addition or the EXCLUSIVE
`QR operation. While C32 is being fed to the circuit on is
`
`

`
`9
`being computed and transmitted sequentially from the
`circuit. Simultaneously, C1‘ is computed and then loaded
`into S,-or 0§i§3l. Then c31, .
`.
`.
`, co are transmitted out
`of the encoder bit by bit. For interleaving, a shift regis-
`ter S31 is added, and N similar shift registers are in-
`cluded in a column, where N is a number specifying the
`depth of interleaving. N=5 is this exemplary embodi-
`ment of the invention.
`(4) I/O Unit: The I/O unit 24 handles the input/out-
`put operations. In FIG. 2, both F11 and F1 are flip-flops.
`A gate (pass) transistor G1 controlled by (1)1 is inserted
`before flip-flop F1 for the purpose of synchronization. A
`gate transistor G2 passes the data into an output terminal
`DOUT. The flip-flop F0 is inserted before the output
`terminal for synchronization. Control signal SL selects
`whether a bit of an information symbol or a check sym-
`bol from the remainder and interleaver unit 25 is to be
`transmitted.
`(5) Control Unit: The control unit 21 in FIG. 2 gener-
`ates the necessary control signals. This unit is further
`divided into three parts. The first part of the control
`unit is used to generate two overlapping clock signals
`(1)1 and 11:2 from CLK. The second part is used to gener-
`ate control signals START and SL. The third part is a
`divide-by-8 binary counter. This counter generates the
`LD signal to load z,~’s into the buffer register R. The
`START signal
`resets all
`registers and the binary
`counter before the encoding process begins for a frame
`of information symbols.
`The circuit accepts one bit of an information symbol,
`transmits one bit of thevencoded code, and performs one
`step of Berlekamp’s algorithm in one time unit. Immedi-
`ately, after all of the information symbols are received
`by the encoder for a frame, the check symbols are avail-
`able in the remainder unit. After transmitting the check
`symbols, the encoder is ready to process the next frame.
`In this invention, the check symbols just generated are
`shifted down one register position. When all five regis-
`ters have been filled for an interleaving depth of 5, the
`check symbols are transmitted in sequence, one column
`of registers at a time, thus achieving the desired inter-
`leaving.
`Since a frame of data contains 255 symbols, the com-
`putation of a complete encoded frame requires 255
`“symbol cycles.” A symbol cycle is the time interval
`needed to execute a complete cycle of Berlekamp’s
`algorithm. Since a symbol has 8 bits, a symbol cycle
`contains 8-bit cycles. Here a bit cycle is defined to be
`the time interval needed to execute one step of Ber-
`lekamp’s algorithm. In this design, a bit cycle requires
`one period of the clock cycle.
`Having described the architecture of a (255,223) RS
`encoder using the Berlekamp serial multiplier a