Static information storage and retrieval – Addressing – Plural blocks or banks
Reexamination Certificate
2001-04-12
2003-10-28
Elms, Richard (Department: 2824)
Static information storage and retrieval
Addressing
Plural blocks or banks
C365S189040, C365S189050
Reexamination Certificate
active
06639865
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to memories which are used in digital devices to temporarily store data, and to Reed-Solomon decoders. More particularly, the present invention relates to circuits and methods for the buffering of data using dual-bank memories, and even more particularly, the present invention relates to the buffering of data in a high-speed block pipelined Reed-Solomon decoder.
2. Description of the Related Art
When transmitting or storing large quantities of digital data, errors inevitably occur in the data channels or transmission media. A variety of techniques are known which attempt to identify such errors and restore the data when feasible. Among these techniques, Reed-Solomon coding has become widely adopted. Reed-Solomon codes are block-based error correcting codes that exhibit excellent error correction capabilities and efficient coding and decoding characteristics, and thus have a wide range of applications in digital communications and storage.
Generally, a Reed-Solomon encoder forms a codeword containing n symbols (e.g., 8-bit bytes) by adding 2t parity symbols to a data block having k symbols of data, whereby 2t=n−k. Reed-Solomon codewords are commonly designated by the characters RS(n,k). For example, in the code RS(255,223), each codeword contains 255 codeword bytes, of which 223 bytes are data and 32 bytes are parity.
On the other hand, a Reed-Solomon decoder processes each codeword in an attempt to correct errors which occur during transmission or storage, and to recover the original data. The decoder is capable of correcting up to t error symbols in each codeword. For example, in the code RS (255,223), n−k=2t=32, and therefore up to 16 error symbols in each codeword can be corrected.
In general, the Reed Solomon decoding process can be partitioned into eight (8) major computational steps when both error and erasure correction are executed. An “erasure” occurs where the value of a symbol is incorrect, but the position of the symbol is known. An “error” occurs where no information is known with regard to an incorrect symbol. The computational steps of error and erasure decoding include (1) computing a syndrome from the received/retrieved input codeword to detect the existence of an error, (2) buffering erasure flags which are supplied in synchronization with the input codeword, (3) modifying the syndrome using the erasure flags, (4) producing an erasure locator polynomial, (5) computing coefficients of the error locator polynomial and an error evaluator polynomial using the modified syndrome values and the erasure locator polynomial, (6) searching the roots of the error locator polynomial, (7) computing the magnitude of error values, and (8) correcting the errors using the value obtained in step (4) and the location obtained in step (3). For error correction only (i.e., no erasure correction), steps (2), (3) and (4) are omitted.
The above steps (1) and (8) require memory access. That is, the received codeword is temporarily stored in a memory at step (1), and is later retrieved from the memory to be corrected in step (8).
The decoding computations (and associated hardware and/or software) of the Reed-Solomon decoder are more complex than those of the encoding process, and it is often difficult to realize decoders having sufficiently high processing speeds. This can be especially problematic in view of the present demand for higher-speed digital data processing systems.
In an effort to increase speeds, pipelining of the computations of the Reed Solomon decoder is a possible solution. However, the computations have different latencies depending on the number of errors and the lengths of the codewords, and accordingly, pipelining is limited by the unit or block having the longest latency. Moreover, even if latencies of the processing blocks were reduced to a single frame of n cycles (i.e., one codeword), the memory for temporarily storing the input codeword prior to correction creates a bottleneck in that at least 2n cycles are required to first store the codeword, and to then retrieve the codeword for correction thereof.
SUMMARY OF THE INVENTION
It is an objective of the present invention to provide a memory device, and a method of accessing a memory device, which execute read/write operations at high speeds, and which thus may be advantageously used in conjunction with a high-speed block pipelined Reed-Solomon decoder, and to provide a high-speed block pipelined Reed-Solomon decoder which exhibits a minimal memory access time.
According to one aspect of the invention, writing to and reading from a plurality of dual-bank RAMs is enabled during each of successive frame periods such that each bank of the dual-bank RAMs is read every given number of frame periods and is written every same given number of frame periods, and such that a read bank is contained in a different one of the plurality of dual-bank RAMs than is a write bank in each of the successive frame periods.
According to another aspect of the present invention, a memory includes a first dual-bank RAM having a first bank and a second bank, a second dual-bank RAM having a third bank and a fourth bank, and a third dual-bank RAM having a fifth bank and a sixth bank. Reading from the first through sixth data banks is enabled in order during successive frame periods such that each one of the first through sixth data banks is read every six frame periods, and writing to the first through sixth data banks is enabled in order during the successive frame periods such that each one of the first through sixth data banks is written every six frame periods. Further, during each of the frame periods, a one of the first through sixth data banks for which reading is enabled is contained in a different one of the first through third dual-bank RAMs than is a one of said first through sixth data banks for which writing is enabled.
According to still another aspect of the present invention, during each frame period, an offset from a data bank for which reading is enabled to a data bank for which writing is enabled is four (or three) data banks, such that each of the first through sixth data banks that is written in a frame period a is later read in a frame period a+4 (or a+3), where a is an integer.
According to yet another aspect of the present invention, the dual-bank memories mentioned above are utilized in combination with a plurality of pipelined processing units which receive input Reed-Solomon codewords and which execute computations to identify error locations and error values contained in the input codewords. Preferably, the plurality of pipelined processing units and the memories are operative in response to a same clock signal rate.
According to still another aspect of the present invention, each codeword contains n bytes, and each of the memory banks has a capacity of n bytes, where n is a positive integer. Preferably, a maximum latency of each of the plurality of pipelined processing units is n cycles, and each of the memory access frame periods is n cycles.
REFERENCES:
patent: 4725987 (1988-02-01), Cates
patent: 4745576 (1988-05-01), Hasegawa et al.
patent: 4845713 (1989-07-01), Zook
patent: 4868812 (1989-09-01), Kruger et al.
patent: 5446743 (1995-08-01), Zook
patent: 5570320 (1996-10-01), Runas
patent: 5771199 (1998-06-01), Lee
patent: 5774648 (1998-06-01), Kao et al.
patent: 5961660 (1999-10-01), Capps, Jr. et al.
patent: 6023745 (2000-02-01), Lu
patent: 6031783 (2000-02-01), Proebsting
patent: 6044206 (2000-03-01), Kohn
patent: 6079046 (2000-06-01), Tamura et al.
patent: 6081920 (2000-06-01), Morelos-Zaragoza
patent: 6134145 (2000-10-01), Wong
patent: 6137807 (2000-10-01), Rusu et al.
patent: 0 224 691 (1987-06-01), None
patent: 0 261 751 (1988-03-01), None
patent: 0 658 871 (1995-06-01), None
patent: WO 95/12850 (1995-05-01), None
Elms Richard
Nguyen Hien
LandOfFree
Memory device, method of accessing the memory device, and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory device, method of accessing the memory device, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory device, method of accessing the memory device, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149855