Hypersystolic Reed-Solomon decoder

Claim 1

A hypersystolic apparatus for operating upon a serialized Reed-Solomon encoded information stream, said stream possibly corrupted by errors and comprising sequential symbol blocks each of length N symbols and redundancy r for correcting as many as T=errata encountered in each said symbol block of said information stream, comprising (a) data stream splitter for producing a copy of said information stream whereby first and second information streams are initially identical for separate processing and said information streams are initially synchronized, each said information stream comprising consecutive blocks of said N symbols, each said symbol comprising m bits, (b) dual channel digital delay line means for propagating each of said first and second information streams along respective channels to error corrector means, said channel supporting said second information stream further comprising a plurality of joiner means for diverting said second information stream onto respective propagation paths comprising first, second and third folded hypersystolic arrays and returning said second information stream from said lateral propagation paths to said respective channel of said digital delay line, whereby said second information stream is processed in each of said hypersystolic arrays to produce a stream of error corrector information, (c) said first hypersystolic array defining a first lateral folded data path for processing said second information stream to evolve same to a stream of r power sum symmetric functions S of each said Reed-Solomon symbol block, (d) said second hypersystolic array defining said second lateral path for receiving said serialized power sum symmetric functions and determining solutions of the key equation therefor, to obtain serialized polynomials ω(z) and σ(z) of minimum degree satisfying (1+S(z))σ(z)=ω(z) mod z.sup.r where said σ(z) comprise coefficients of the error location polynomial, said ω(z) comprise the error valuator polynomial, said second data stream modified by said second hypersystolic array to comprise T+1 coefficients of said polynomial σ and T coefficients of said polynomial ω, (e) said third hypersystolic array being for receiving said polynomial coefficients σ and ω and producing therefrom a serialized stream of correction information for return to said second channel of said dual channel digital delay line, said correction information stream being synchronized with said first information stream, (f) corrector means for linearly combining each datum of said first information stream with the respective datum of said correction stream to produce a corrected data stream.