Excavating
Patent
1987-06-08
1989-07-04
Atkinson, Charles E.
Excavating
G06F 1110
Patent
active
048457132
ABSTRACT:
For decoding a Reed-Solomon codeword with (n-K) check characters an error/erasure locator (32) executes a codeword cycle comprising (n-K) "coefficient" iterations followed by (n-K) "modified syndrome" iterations. The error/erasure locator (32) includes a bank (52) of simultaneously loadable syndrome registers and a bank (56) of coefficient registers. The syndrome registers are connected to one another in a circular shift path (91). The error/erasure locator (32) further includes a cascading arrangement of PISO multipliers (54), a SIPO multiplier (60), and PISO multipliers (61). The PISO multipliers (54) operate upon the contents of the syndrome registers (52) (expressed in a conventional basis representation) and the contents of the coefficient register (56) (expressed in dual basis representation) to obtain a serial current discrepancy d.sub.n. The SIPO multiplier 60 multiplies the serial current discrepancy d.sub.n by a parallel-formatted multiplicative inverse d.sub.m.sup.-1 .beta..sub.i of a prior discrepancy (expressed in dual basis representation) to obtain in one set of clock cycles, the product d.sub.n d.sub.m.sup.-1. During a second set of clock cycles the discrepancy product d.sub.n d.sub.m.sup.-1 is further multiplied using a second bank (61) of PISO multipliers by the contents of corresponding auxiliary registers (62) to obtain a serial product useful for updating the coefficient registers (56). The syndrome registers (52) perform the dual purpose of storing the original syndromes during the coefficient iteration and of storing the modified syndromes produced during the modified syndrome iteration.
REFERENCES:
patent: 4162480 (1979-07-01), Berlekamp
patent: 4410989 (1983-10-01), Berlekamp
patent: 4494234 (1985-01-01), Patel
patent: 4559625 (1985-12-01), Berlekamp
patent: 4584686 (1986-04-01), Fritze
patent: 4633470 (1986-12-01), Welch et al.
patent: 4642808 (1987-02-01), Baggen
patent: 4649541 (1987-03-01), Lahmeyer
patent: 4665523 (1987-05-01), Citron et al.
patent: 4675869 (1987-06-01), Driessen
IEEE Transactions on Computers, vol. C33, No. 10, Oct. 1984, IEEE, In-Shek Hsu et al.: "The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm", pp. 906-911.
The 10th Annual International Symposium on Computer Architecture, Conference Proceedings, 1983, ACM, A. L. Fisher et al.: "Architecture of the PSC: A Programmable Systolic Chip", pp. 48-53.
IEEE Transactions on Computers, vol. C-31, No. 2, Feb. 1982, IEEE, Kuang Y. Liu: "Architecture for VLSI Design of Reed-Solomon Encoders", pp. 170-175.
MILCOM 86, 1986 IEEE Military Communications Conference, 5-9 Oct. 1986, Monterey, California, Conference Record, vol. 3 of 3, IEEE (US), G. K. Maki et al.: "VLSI Reed Solomon Decoder Design", pp. 46.5.1-46.5.6.
IEEE Transactions on Computers, vol. C-34, No. 5, May 1985, IEEE, H. M. Shao et al.: "A VLSI Design of a Pipeline Reed-Solomon Decoder", pp. 393-403.
IEEE Transactions on Computers, vol. C-33, No. 2, Feb. 1984, IEEE, K. Y. Liu: "Architecture for VLSI Design of Reed-Solomon Decoders", pp. 178-189.
Carhoun, D. O., Johnson, B. L., and Meehan, S. J., "Transform Decoding of Reed-Solomon Codes, vol. I: Algorithm and Signal Processing Structure," ESD-TR-82-403, vol. I, Nov. 1982.
Massey, J. L., "Shift Register Synthesis and BCH Decoding: IEEE Transactions on Information Theory", IT-15, No. 1, pp. 122-123, Jan. 1969.
Atkinson Charles E.
Exabyte Corporation
LandOfFree
Method and apparatus for determining the coefficients of a locat does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining the coefficients of a locat, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining the coefficients of a locat will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-858151