Method and apparatus for performing error correction code operations

A method for processing encoded data using error control coding in accordance with the present invention includes: a) obtaining Q codewords and P codewords from a storage location, wherein the Q codewords and the P codewords are all obtained in a single pass through the storage location, b) calculating P partial syndromes for said P codewords, c) calculating Q partial syndromes for the Q codewords, and d) storing the Q partial syndromes and the P partial syndromes in a buffer that is separate from the main memory. In some embodiments, storing the Q partial syndromes and the P partial syndromes in the buffer includes storing the Q partial syndromes in a first buffer, and storing the P partial syndromes in a second buffer.

TECHNICAL FIELD 
This invention relates generally to digital data storage and transmission, 
and more particularly methods and apparatus for implementing error control 
codes for data storage and transmission. 
BACKGROUND ART 
The CD-ROM and recordable CD, i.e., CD-R, evolved out of the original audio 
CD. In general, CD-ROMs and CD-Rs are considered to be pervasive and 
ubiquitous media because of their ability to store large amounts of data, 
typically over 630 MB of data. 
Relatively high error rates are often associated with optical media such as 
the audio CD (ie., CD Audio), the CD-ROM, and CD-R. In order to address 
and reduce the relatively high error rates, the CD Audio conventionally 
included a Cross-Interleaved Reed-Solomon Code (CIRC) to reduce the error 
rate to an acceptable rate for audio material. 
The CD-ROM and CD-R were, in terms of sectoring, designed to overlay the 
basic physical structure of the CD Audio. For error compensation, the 
CD-ROM and CD-R retained the Cross-Interleaved Reed-Solomon code but added 
an additional Reed-Solomon Product Code (RSPC) to accommodate the more 
stringent error rates required for computer data storage, as specified in 
the ISO/IEC 10149:1995(E) standard of ISO/IEC, which is incorporated 
herein by reference. 
As computers have become faster, the need for transferring information from 
the CD-ROM and CD-R at higher rates has increased as well. In order to 
achieve a higher rate of information transfer, CD-ROM/CD-R drive 
manufacturers have increased the rotational speed of the CD-ROM/CD-R 
drives. 
Since CD-ROM/CD-R drives are attached to and, therefore, interface with 
computers, it is generally necessary to have an interface controller to 
process the data from the CD-ROM/CD-R and deliver the data to an 
associated computer. Figure la shows a typical system block diagram for an 
interface controller that is associated with a CD-ROM and a CD-R which is 
in read mode. A CD-ROM 110 is in communication with a disk interface 112. 
Since a CD-R is recordable, it has a read mode and a write mode. As such, 
it should be appreciated that when a CD-R is in read mode, the data flow 
is from the CD-R to host interface 114, as it is for CD-ROM 110. 
Data read from CD-ROM/CD-R 110 is passed through a DRAM 113, which is a 
memory. Data may be stored in DRAM 113, which is in communication with an 
error control coding (ECC) arrangement 115 that is used to reduce the 
error rate associated with data stored in DRAM 113. ECC 115 generally 
includes a Reed-Solomon decoder, as will be appreciated by those skilled 
in the art. From DRAM 113, data is provided to a host interface 114. 
While the data flow for a CD-R in read mode and a CD-ROM is from the 
CD-ROM/CD-R to a host, the data flow for a CD-R in write mode, 
alternatively, is from the host to the CD-R. FIG. 1b is a typical system 
block diagram for an interface controller that is associated with a CD-R 
which is in write mode. A host interface 130 provides data to a DRAM 132, 
which is in communication with an ECC 134. A disk interface 136 reads data 
from DRAM 132 and writes the data onto a CD-R 138. 
Part of the process of passing data between a CD-ROM/CD-R and a host 
includes ECC operations which are generally used to recover useful data 
from the CD-ROM/CD-R in the presence of errors. Although the errors can be 
widely varied, examples of such errors include scratches, fingerprints, 
and manufacturing imperfections of the physical media. 
ECC is generally based on mathematical principles and, as such, entails 
performing a large number of complex arithmetic computations at high 
speeds. As the rotational speed of CD-ROM/CD-R drives has increased, the 
demand placed upon interface controllers has increased as well, since 
interface controllers must be capable of processing data at much higher 
rates. The principal impediment to operating the interface controller at 
high data rates has been the difficulty of performing ECC operations at 
the increasingly high data rates. 
Data on a CD-ROM/CD-R is typically organized as sectors, each of which 
includes 2352 bytes, as described in the above-mentioned ISO/IEC 
10149:1995(E) standard. In general, three types of sectors exist, each 
with a different data organization. Of the three types of sectors, one 
type of sector is protected by a Reed-Solomon Product Code. FIG. 2 
indicates the physical layout of a sector that can be protected by a 
Reed-Solomon Product Code or, more generally, an ECC. A sector 202 
includes data 204 and parity bytes 206a-b, which will be described in more 
detail below. As shown, sector 202 includes 2076 bytes of data 204. Data 
204 occupy overall bytes "0" through "2063" from the beginning of the data 
field, while the 172 P-parity bytes 206a occupy bytes "2064" through 
"2235" from the beginning of the data field, and the 104 Q-parity bytes 
206b occupy bytes "2236" through "2339" of the data field. The location of 
data 204 and parity bytes 206 have, therefore, a relative byte offset from 
the beginning of the data field. Data 204 is protected by ECC, while 
parity bytes 206a-b are used for ECC. As will be appreciated by those 
skilled in the art, the sync bytes of sector 202 are not included in the 
ECC encoding, and are not protected by ECC. 
In a typical system, data from a CD-ROM/CD-R is read into a word-wide 
dynamic memory (DRAM) using a mapping between memory word addresses and 
relative byte offsets. Such a mapping is shown in FIG. 3. Memory addresses 
210 are mapped into relative byte offsets 212, where byte offsets 212 are 
divided in terms of even bytes 213 and odd bytes 214. 
A CD-ROM/CD-R ECC segments a sector into two separate but identical 
encodings which separately span even and odd bytes. That is, using the 
DRAM memory addresses as shown in FIG. 3, all the even bytes can be 
segregated together and encoded by a Reed-Solomon Product Code, and all 
the odd bytes can be segregated together and encoded by a Reed-Solomon 
Product Code, as indicated in FIG. 4. That is, even, or odd, data bytes 
220, which are protected by ECC, can be segregated together along with 
their associated P-parity bytes 222 and Q-parity bytes 224. 
As previously mentioned, a CD-ROM/CD-R specifies a Reed-Solomon Product 
Code. The specification of a Reed-Solomon Product Code implies that there 
are two dimensions, which are referred to as "P" and "Q." With reference 
to FIG. 5, the Reed-Solomon Product Code data organization of even or odd 
bytes, which are taken separately, of a sector will be described. 
Specifically, the data organization of a Reed-Solomon Product Code will be 
described in terms of the manner in which ECC encoding is performed. The 
construction of the Reed-Solomon Product code involves creating a matrix 
of data 228, which has 43 columns 229 and 24 rows 230. Elements in cells 
232 correspond to word, or memory, addresses for DRAM data organization as 
shown in FIG. 3. 
The data in each column 229 includes 24 bytes, and is encoded by a 
single-error correcting Reed-Solomon code, and two parity bytes for each 
column 229 are placed in rows 230h and 230i in column 229 over which the 
encoding has taken place. Each newly formed codeword is a separate P 
codeword. Therefore, there are 43 such codewords, corresponding to the 43 
columns 229. For purposes of explanation, each individual P codeword will 
referenced as P.sup.i, where i ranges from 0 to 42. 
The encoding of individual P codewords represents one dimension of the 
Reed-Solomon Product Code. The second dimension of the Reed-Solomon 
Product Code involves encoding data lying along the diagonals of matrix 
228. For the second dimension, which encodes Q codewords, the "data," 
which consists of 43 bytes, includes some of the parity bytes of the P 
codewords, as will be described in more detail with respect to FIG. 6. 
FIG. 6 illustrates the manner in which the Q codewords are typically 
constructed by presenting two specific Q codewords. FIG. 6 is a partial 
representation of matrix 228 of FIG. 5. That is, matrix 228' of FIG. 6 is 
essentially matrix 228 of FIG. 5, without Q-parity rows 230k and 230l. The 
first Q codeword 240 starts in row 0, column 0 of matrix 228' and proceeds 
down the diagonal until Q codeword 240 reaches column 25, row 24, at which 
point Q codeword 240 continues from row 0, column 26 until Q codeword 240 
terminates at row 16, column 42. It should be appreciated that parity 
bytes associated with P codewords in matrix 228', which are located in 
rows 24 and 25, are also included in Q codeword 240. The two parity bytes 
for Q codeword 240 are placed in Q-parity positions associated with matrix 
228'. That is, Q parity bytes for Q codeword 240 are placed in row 230k 
(location 1118) and row 2301 (location 1144), at column 229a, as shown in 
FIG. 5. 
Another Q codeword 242 starts in row 20. As before, Q codeword 242 moves 
down matrix 228'. Q codeword 242 moves from row 20, column 0 at a diagonal 
until row 25, column 5 is reached. Then, Q codeword 242 continues from row 
0, column 6, moving at a diagonal down to row 25, column 31. Q codeword 
242 then continues from row 0, column 32 along a diagonal until row 10, 
column 42 is reached. As was the case for Q codeword 240, P parity bytes 
are included in Q codeword 242. Specifically, P parity bytes located at 
row 24, column 4, as well as P-parity bytes at row 25, column 6, P-parity 
bytes at row 24, column 30 and P-parity bytes at row 25, column 31, are 
all included as a part of Q codeword 242. The two parity bytes for Q 
codeword 242 are placed in row 230k (location 1138) and row 2301 (location 
1164), of matrix 228, as shown in FIG. 5. 
In total, there are 26 Q codewords, corresponding to each of the 26 rows of 
matrix 228'. That is, the first element of each Q codeword, as for example 
Q codeword 240, starts in column 0 of each row. The 26 Q codewords which 
correspond to rows of a matrix is in contrast to the 43 P codewords which 
correspond to each of the columns of a matrix, as described above with 
respect to FIG. 5. For purposes of explanation, each individual Q codeword 
will referenced as Q.sup.j, where j ranges from 0 to 25. 
As previously mentioned, each dimension, i.e., P and Q, of the Reed-Solomon 
Product Code is encoded by a single-error correcting (SEC) Reed-Solomon 
code. In order to encode the dimensions, a CD-ROM/CD-R typically uses a 
Galois Field (i.e., GF(2.sup.8)) generated by the following primitive 
polynomial: 
EQU p(x)=x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1 
where the primitive element of GF(2.sup.8) is: .alpha.=(00000010). The same 
SEC Reed-Solomon code is used for both the P codewords and Q codewords. 
The SEC Reed-Solomon code is generated using the following generator 
polynomial: 
EQU g(x)=(x+.alpha..sup.1)(x+.alpha..sup.0) 
For a typical CD-ROM/CD-R interface controller, the steps for performing 
error corrections involve first computing the partial syndromes for each 
P.sup.i codeword and then performing SEC on each P.sup.i codeword, 
whenever possible. When the partial syndromes are computed, and SEC is 
performed, each p.sup.i codeword is processed one at a time, and the 
errored byte corrected in memory. Then, after all the P codewords are 
processed, the partial syndromes for each Q.sup.i codeword are computed, 
and SEC is performed whenever possible. As was the case for the P 
codewords, each Q.sup.i codeword is processed one at a time, and the 
errored byte is corrected in memory. The partial syndromes for the P 
codewords and Q codewords are calculated and SEC is performed whenever 
possible until either all the partial syndromes are zero, indicating no 
more detectable errors, or a repetition count associated with the 
computations expires. FIG. 7 illustrates the preceding steps, where the 
index i refers to the columns, and index j refers references each Q 
codeword. 
A received polynomial r(x) is the combination of an original codeword and 
any errors which might have been introduced within the original codeword. 
In other words, r(x)=c(x)+e(x), where c(x) is the originally generated 
codeword, and e(x) is the error polynomial which represents any error 
introduced within the original codeword. Since two factors make up the 
generator polynomial, due to the fact that a SEC Reed-Solomon code is 
being implemented, two partial syndromes, S.sub.0 and S.sub.1 can be 
calculated. The two partial syndromes are calculated by evaluating the 
received polynomial, r(x) , at each of the factors of the generator 
polynomial g(x), namely .alpha..sup.0 and .alpha..sup.1. As such, the 
following expressions for partial syndromes S.sub.0 and S.sub.1 can be 
obtained: 
EQU S.sub.0 =r(.alpha..sup.0)=c(.alpha..sup.0)+e(.alpha..sup.0) 
EQU S.sub.1 =r(.alpha..sup.1)=c(.alpha..sup.1)+e(.alpha..sup.1) 
By definition, the originally generated codeword c(x) evaluated at 
.alpha..sup.0 and .alpha..sup.1 are zero, i.e., c(.alpha..sup.0)=0 and 
c(.alpha..sup.1)=0, since .alpha..sup.0 and .alpha..sup.1 are factors of 
generator polynomial g(x). As such, partial syndromes S.sub.0 and S.sub.1 
can also be expressed as: 
EQU S.sub.0 =r(.alpha..sup.0)=e(.alpha..sup.0) 
EQU S.sub.1 =r(.alpha..sup.1)=e(.alpha..sup.1) 
In general, the received polynomial, r(x), is represented as follows: 
EQU r(x)=r.sub.n-1 x.sup.n-1 +r.sub.n-2 x.sup.n-2 +. . . +r.sub.1 x.sup.1 
+r.sub.0 x.sup.0 
where the r.sub.i are the data from a DRAM and are, therefore, the original 
data combined with the error data, and n is the length of the codeword. As 
such, partial syndromes S.sub.0 and S.sub.1 can further be expressed as 
##EQU1## 
An alternative method of evaluating the received polynomial r(x) is by the 
use of Horner's rule, which is a recursive multiply and add algorithm, as 
will be appreciated by those skilled in the art. In this regard, the 
partial syndrome equations can be rewritten in the following form: 
EQU S.sub.i =((. . . (r.sub.n-1 .alpha..sup.i +r.sub.n-2) .alpha..sup.i 
+r.sub.n-3) .alpha..sup.i +. . .+r.sub.1) .alpha..sup.i +r.sub.0 
The usual procedure for computing the partial syndromes is to use the 
circuit in FIG. 8, which directly implements Horner's rule. A partial 
syndrome calculation circuit 270 includes a separate circuit, as for 
example circuits 274, 276, for each partial syndrome that is to be 
calculated. The coefficients of received polynomial r(x) are sequentially 
transmitted to partial syndrome calculation circuit 270, where the 
coefficients of received polynomial r(x) are passed through modulo-2 
adders 278, 279, which are implemented by exclusive OR circuits. It should 
be appreciated that adders 278, 279 are generally identical. The output 
from adder 278 is multiplied by root .alpha..sup.0 280 of generator 
polynomial g(x), in order to obtain partial syndrome S.sub.0. Likewise, 
the output from adder 279 is multiplied by root .alpha..sup.1 217 to 
obtain partial syndrome S.sub.1. Once obtained, the partially computed 
partial syndromes S.sub.0 and S.sub.1 are clocked into flip-flops 282, 
283. 
It should be appreciated that substantially all arithmetic operations are 
over GF(2.sup.8) such that addition is performed modulo 2. Addition is, 
therefore, implemented by an exclusive or gate, which is denoted by the 
.sym. symbol. In addition, fixed Galois Field multiplication is 
implemented as well. The use of the symbol indicates Galois Field 
multiplication performed in GF(2.sup.8). 
Circuit 270 of FIG. 8 relies upon the proper ordering of the elements of 
the codewords. As such, circuit 270 only serves its intended purpose if 
the elements clocked into the circuit are in sequential order, from the 
first element to the last element. 
An error correction operation is performed once partial syndromes S.sub.0 
and S.sub.1 are calculated. In the event that either partial syndromes 
S.sub.0 or S.sub.1 are non-zero, then an error has occurred. If a single 
random error has occurred, then one of the r.sub.i contains the error, 
where i identifies the relative location within the codeword which is in 
error. When a single random error has occurred, then partial syndromes 
S.sub.0 and S.sub.1 can be expressed in terms of the value of the random 
error and the error location as follows: 
EQU S.sub.0 =v 
EQU S.sub.1 =v.alpha..sup.i =S.sub.0.alpha..sup.i 
where v is the error value and i is the error location. To isolate the 
error location i, the following expression can be used: 
EQU i=log.sub..alpha. (S.sub.1 /S.sub.0) 
Once i is determined, the original data can be recovered by adding the 
value of S.sub.0 to the data read from memory at location "i." This 
operation is performed modulo-2, as will be appreciated by those skilled 
in the art. 
The coefficients of received polynomial r(x) represent the elements of a 
codeword. When an error is present, the location of the error is 
determined by the procedure described above. The locations are represented 
by elements of GF(2.sup.8), as shown in FIG. 9. As shown, the 
.alpha..sup.j are labels for the possible error locations of the codeword. 
If there is an error in r.sub.n-3, for example, the location of the error 
is referenced as .alpha..sup.2, which is the result that would be obtained 
by calculating `i` as described above. 
An example of a P codeword, located in column 42 of data matrix 228 is 
shown in FIG. 10. In FIG. 10, a row 290 contains DRAM addresses of bytes 
which make up the P codeword. Due to the fact that the even bytes and the 
odd bytes are treated separately, it should be appreciated that FIG. 10 
can refer to either even bytes or odd bytes. 
A second row 292 refers to each coefficient of a received polynomial. In 
this case, any r.sub.k could contain an error, in which case the value 
obtained from the DRAM would be d.sub.k .sym.e.sub.k, where d.sub.k is the 
original encoded data and e.sub.k is the error pattern introduced. The two 
parity bytes of the codeword represented in row 290 are located in cells 
293, 294. A third row 296 contains labels, which are elements of 
GF(2.sup.8), that identify each location of the received polynomial r(x) 
as a solution for a corresponding error location equation. 
As previously mentioned, the operation of the partial syndrome calculation 
circuit of FIG. 8 requires that the data passed into the circuit is in the 
proper order, i.e., in the same order in which the original data is 
encoded. In this regard, the data from a DRAM must be read 
non-sequentially such that the data can correspond to the same order of 
bytes making up a codeword. This non-sequential access of data is not as 
efficient as a sequential access of data due to the fact that DRAMs have a 
mode of operation called Page Mode which allows data to be accessed much 
faster when the data is located in consecutive locations within the 
memory. Hence, the calculation of partial syndromes, as discussed above, 
causes inefficiency in CD-ROM/CD-R interface controllers since a 
non-sequential access of data requires more memory bandwidth for obtaining 
the data from the DRAM. 
In general, the inefficiency in CD-ROM/CD-R interface controllers can be 
attributed to two sources. Once source of inefficiency is due to the fact 
that each data byte generally must be read twice. That is, each data byte 
must be read once to calculate the P partial syndromes, and a second time 
to compute the Q partial syndromes. This is due to the fact that partial 
syndromes for the P codewords are calculated separately from partial 
syndromes of the Q codewords, although each data byte is simultaneously 
used to encode both a P codeword and a Q codeword. Another source of 
inefficiency is that the calculation of the partial syndromes are made by 
non-sequential accesses such that the faster Page Mode access method 
cannot be used. 
A typical approach to performing the ECC functions also requires that 
multiple passes be made through memory in order to perform error 
correction operations, as shown in FIG. 7. In this regard, each iteration 
pass through memory involves recalculating the partial syndromes, which 
uses up a considerable amount of memory bandwidth, as mentioned above. One 
consequence associated with repeated passes through memory is that less 
memory bandwidth is available for reading additional sectors of data from 
the CD-ROM/CD-R and for delivering the corrected data to a host, since the 
DRAM is the central repository. 
In general, conventional approaches to performing ECC operations involve 
two separate passes through memory for each iteration of the correction 
process to calculate the partial syndromes for each of the P codewords and 
each of the Q codewords. Multiple iterations are required, thereby leading 
to additional DRAM memory accesses. Each memory access is a non-sequential 
access which is much less efficient than using a Page Mode access method. 
As such, the maximum transfer rate of data from a CD-ROM/CD-R to a host is 
often limited due to the high DRAM memory bandwidth required by the ECC 
operations. 
For a CD-R, it is requirement for data to be written onto the disk in the 
same format as for CD-ROM. Hence, it is necessary to generate parity bytes 
for all of the associated P codewords and Q codewords. In a conventional 
approach to writing data onto a CD-R, data from a host computer is placed 
into the DRAM main memory, as described above with respect to FIG. 1b. 
Once data is placed into the main memory, the EDAC then accesses the data 
and computes the P parity bytes and Q parity bytes. As was the case for 
the typical approach taken with respect to a CD-ROM, the individual data 
making up the codewords for each dimension are accessed in non-sequential 
fashion, Le., one after the other, such that the appropriate parity bytes 
are computed during each access. The parity bytes are then written into 
memory. It should be appreciated that such a process implies making two 
non-sequential passes through memory. 
An example of a standard circuit for generating parity bytes is shown in 
FIG. 11. Circuit 302 relies upon the proper ordering of the data bytes 
since the parity bytes are computed in "byte-serial" fashion. Data is 
passed through an exclusive OR 304, which functions as modulo-two adder. 
The output from adder 304 is separately multiplied by .alpha.306 and 
clocked into flip-flop 312. The output from adder 304 is also multiplied 
by .alpha..sup.25 308, passed through an adder 311, and clocked into 
flipflop 310. 
In circuit 302, the input data, or DataIn 314, comes from DRAM. The bytes 
in DataIn 314 are clocked into circuit 302 which performs a byte-serial 
division of the data using the following generator polynomial g(x): 
EQU g(x)=(x+.alpha..sup.0)(x+.alpha..sup.1) 
After the last data byte is inputted to circuit 302, the two flip-flops 
310, 312 hold the remainder of the division, which are the parity bytes. 
The parity bytes can then be written out to the DRAM. The result of the 
byte-serial division operation is to create, or encode, a Reed-Solomon 
codeword in systematic form. That is, the byte-serial division allows the 
original data to be included in the computed codeword, with the parity 
bytes "tacked on" to the end of the data. 
The systematic form of a Reed-Solomon codeword is generally computed as 
follows: 
EQU c(x)=(d(x)*x.sup.2 modulo g(x))+d(x)*x.sup.2 
where c(x) is the Reed-Solomon codeword, d(x) is the data, and g(x) is the 
generator polynomial. As shown in the above expression, data d(x) is first 
pre-multiplied by x.sup.2 and divided by g(x). Then, the results of the 
pre-multiplication and division are added to d(x)*x.sup.2. 
The computation of P and Q codewords associated with writing data onto a 
CD-R requires two non-sequential passes through memory, as well as 
separate circuitry that must be used in addition to the syndrome 
computation circuits. 
The maximum transfer rate of data from a CD-ROM/CD-R to a host or from a 
host to a CD-R is often limited due to the high DRAM memory bandwidth 
required by the ECC operations. Therefore, as the general demand for 
high-speed CD-ROM and CD-R is always increasing, what is desired is a 
method and an apparatus for efficiently implementing ECC without requiring 
a high DRAM memory bandwidth. Specifically, what is desired is a method 
and an apparatus for efficiently calculating partial syndromes for use in 
a Reed-Solomon encoder and decoder. 
DISCLOSURE OF THE INVENTION 
A method for calculating partial syndromes for codewords that are used in 
error control coding enables partial syndromes to be computed using a 
single, sequential access to data bytes stored in memory. Partial 
syndromes, as well as intermediate values for the partial syndromes, are 
held in buffers where they can be readily accessed. Allowing a single, 
sequential access to data bytes stored in memory increases the efficiency 
of partial syndrome computations. 
A method for processing encoded data using error control coding in 
accordance with the present invention includes: a) obtaining Q codewords 
and P codewords from a storage location, wherein the Q codewords and the P 
codewords are all obtained in a single pass through the storage location, 
b) calculating P partial syndromes for said P codewords, c) calculating Q 
partial syndromes for the Q codewords, and d) storing the Q partial 
syndromes and the P partial syndromes in a buffer that is separate from 
the main memory. In some embodiments, storing the Q partial syndromes and 
the P partial syndromes in the buffer includes storing the Q partial 
syndromes in a first buffer, and storing the P partial syndromes in a 
second buffer. In such embodiments, a plurality of intermediate values for 
P partial syndromes can be stored in the first buffer, and a plurality of 
intermediate values for Q partial syndromes can be stored in the second 
buffer, where the values can be accessed during partial syndrome 
computations. 
An apparatus for processing data encoded using error control coding in 
accordance with the present invention includes a main memory being 
arranged to hold he encoded data, and circuitry arranged to access said 
main memory to retrieve the encoded data. The circuitry is also arranged 
to process the encoded data, which is formatted as codewords, and includes 
a partial syndrome calculation circuit that is arranged to compute partial 
syndromes for the codewords. The partial syndrome calculation circuit 
further includes a buffer arrangement arranged to store the partial 
syndromes after the partial syndromes are calculated using a single access 
to the main memory. In one embodiment, the buffer arrangement includes a 
first buffer arranged to store the partial syndromes computed for the P 
codewords and a second buffer arranged to store the partial syndromes 
computed for the Q codewords. 
These and other advantages of the present invention will become apparent 
upon reading the following detailed descriptions and studying the various 
figures of the drawings.

BEST MODES FOR CARRYING OUT THE INVENTION 
FIGS. 1a and 1b are block diagram representations of systems which use 
Reed-Solomon codes for error correction and were discussed previously. 
FIG. 2 is a representation of a sector of a CD-ROM or CD-R, FIG. 3 is a 
table which shows the mapping between DRAM words and sector bytes, FIG. 4 
is a representation of bytes in a sector which are protected by and used 
for error control coding, FIG. 5 is a representation of a data matrix from 
which columnar and diagonal codewords are generated, and FIG. 6 is a 
representation of a portion of the data matrix of FIG. 5 which shows the 
construction of Q codewords, all of which were also discussed previously. 
FIG. 7 is a process flow diagram which illustrates the steps associated 
with a prior art process of calculating partial syndromes, FIG. 8 is a 
circuit diagram of a prior art circuit which is used to recursively 
calculate partial syndromes for use with Reed-Solomon codes for error 
correction, FIG. 9 is a representation of the relationship between 
solutions to an error location polynomial and coefficients of a received 
polynomial, FIG. 10 is a representation of the possible error location 
values for a specific P codeword, FIG. 11 is a prior art circuit which is 
used to generate parity bytes, and were all also previously discussed. 
FIG. 12 is a tabular representation of the terminology and nomenclature 
which will be used herein and below. 
In order to more efficiently compute the partial syndromes and perform 
correction operations, the partial syndromes for each P codeword and each 
Q codeword can be computed using only a single sequential pass through 
memory. The partial syndromes for each of the P codewords are then stored 
in a separate buffer P.sub.-- BUF, while the partial syndromes for each of 
the Q codewords are stored in a separate buffer Q.sub.-- BUF. 
Substantially all correction operations can be performed using the partial 
syndromes in P.sub.-- BUF and Q.sub.-- BUF, without additional access to 
memory. Memory is only accessed again for the purpose of writing corrected 
values back into the memory. 
One circuit which is suitable for computing the partial syndromes for each 
of the P and Q codewords will be described with reference to FIGS. 13 and 
14. FIG. 13 is a block diagram which illustrates a circuit that is used to 
compute the partial syndromes in accordance with an embodiment of the 
present invention. A partial syndrome computation circuit 402 includes a 
P.sub.-- BUF 412 and a Q.sub.-- BUF 414. P.sub.-- BUF 412 is arranged to 
hold values for the P partial syndromes, while Q.sub.-- BUF 414 is 
arranged to hold values for the Q partial syndromes. 
P.sub.-- BUF 412 and Q.sub.-- BUF 414 are typically local memory buffers. 
In the described embodiment, P.sub.-- BUF 412 is 43 locations long, with 
each location being arranged to hold partial syndromes. That is, each 
location i within P.sub.-- BUF 412 is arranged to hold the two partial 
syndromes for codeword P.sup.i. Q.sub.-- BUF 414 is 26 locations long and 
is arranged such that each location j within Q.sub.-- BUF 414 is holds the 
partial syndromes for codeword Q.sup.j. 
In the described embodiment, two sets of buffers are used to store the 
partial syndromes. One set is used for computing the partial syndromes for 
the low-order bytes and the other set is used to computing the partial 
syndromes for the high-order bytes. As shown, circuit 402 is suitable for 
use in either computing the partial syndromes for the low-order bytes or 
the high-order bytes. It should be appreciated that if it is desired to 
calculate the partial syndromes for the lower byte stream simultaneously 
with calculating the partial syndromes for an upper byte stream, circuit 
402 can essentially be "duplicated," with some modifications, to enable 
the partial syndromes for the lower byte streams to be calculated at the 
same time as the partial syndromes for upper byte streams. 
A data line 420 is clocked into a multiplexer 424 that is arranged to 
distribute data, or the bytes which make up a codeword, throughout circuit 
402. In the described embodiment, the partial syndromes are calculated for 
a single error correction process. Therefore, as will be appreciated by 
those skilled in the art, two partial syndromes, S.sub.0 and S.sub.1, are 
typically calculated for each codeword. Syndrome S.sub.0 is calculated by 
adding all data bytes, using exclusive OR 434, that are associated with a 
given codeword. It should be appreciated that prior to the calculation of 
the partial syndromes, P.sub.-- BUF 412, as well as Q.sub.-- BUF 414, are 
initialized with zero values in substantially every location. As each data 
byte passes through multiplexer 424, the contents of P.sub.-- BUF 412 are 
accessed to locate the intermediate value which is associated with, or 
relevant to, a particular data byte, and added to the data byte. The 
mathematical expression for obtaining partial syndrome S.sub.0 for P 
codewords can be expressed as follows: 
EQU S.sub.0 =d.sub.n-1 .sym.d.sub.n-2 .sym.. . . .sym.d.sub.1 .sym.d.sub.0 
where d.sub.m represents the elements of a P codeword, and n represents the 
length of the codeword. In the described embodiment, the codeword has a 
length of 26 elements, including redundancy bytes for P codewords. 
Once an intermediate value is updated, the updated intermediate value is 
rewritten back into P.sub.-- BUF 412 at the same location from which the 
original intermediate value was obtained. It should be appreciated that 
once all relevant data bytes have been processed for a particular P 
codeword, the intermediate value corresponding to the P codeword, as 
stored in P.sub.-- BUF 412, is partial syndrome S.sub.0 for the P 
codeword. The overall timing associated with computing S.sub.0 for storage 
in P.sub.-- BUF 412 is shown in FIG. 19. 
To calculate the syndrome S.sub.1 for the P codewords, the data bytes are 
recursively processed using a single .alpha.-multiplier 428. 
.alpha.-multiplier 428 is coupled to P.sub.-- BUF 412 such that as an 
incoming data byte passes through multiplexer 424, the relevant contents 
of P.sub.-- BUF 412 are read out, passed through multiplier 428, added to 
the incoming data byte using an exclusive OR 436, and written back into 
P.sub.-- BUF 412. As intermediate values for P syndromes are stored in 
P.sub.-- BUF 412, a single .alpha.-multiplier 428 is sufficient for 
calculating S.sub.1 syndromes for P codewords. Once all the relevant data 
bytes for a P codeword are processed, the intermediate values stored in 
P.sub.-- BUF 412 that relate to calculating partial syndrome S.sub.1 are 
the actual partial syndrome S.sub.1. A timing diagram for computing 
S.sub.1 syndromes is shown in FIG. 21. 
Mathematically, the computation of partial syndrome S.sub.1 for the P 
codewords can be expressed as follows: 
EQU S.sub.1 =(d.sub.n-1 .alpha..sup.n-1).sym.(d.sub.n-2 .alpha..sup.n-2).sym.. 
. . .sym.(d.sub.1 (d.sub.0 .alpha..sup.0) 
where d.sub.m values are data bytes associated with a P codeword, and n 
represents the length of the P codeword, which, in the described 
embodiment, is 26. It should be appreciated that the mathematical 
expression for partial syndrome S.sub.1 for the P codewords is implemented 
by the use of Horner's rule which is embodied in circuit 402. 
Horner's rule is generally well-known to those skilled in the art. 
As previously mentioned Q.sub.-- BUF 414 is 26 locations long. In the 
described embodiment, as circuit 402 is used for a single error correcting 
code, each location in Q.sub.-- BUF 414 is arranged to store partial 
syndrome S.sub.0 and partial syndrome S.sub.1. Partial syndrome S.sub.0 
for a Q codeword can be calculated by adding, through the use of an 
exclusive OR 440, all data bytes that are relevant to the Q codeword. 
Specifically, as each data byte sequentially passes through multiplexer 
424, the contents of Q.sub.-- BUF 414 are accessed to locate the 
intermediate value which is relevant to a particular data byte. The data 
byte is then added to the relevant intermediate value. Then, the updated 
intermediate value is rewritten back into Q.sub.-- BUF 414 at the same 
location from which the original intermediate value was obtained. 
To compute partial syndrome S.sub.1 for a Q codeword, it should be 
appreciated that from the point-of-view of the elements that make up the 
codeword, the data bytes do not arrive sequentially. By way of example, 
with reference to the data matrix of FIG. 5, when data byte "0" arrives, 
data byte "0" is the first element of Q codeword number zero, i.e., 
Q.sup.0. However, when data byte "1" arrives, data byte "1" is the second 
element of Q.sup.25, and when data byte "2" arrives, data byte "2" is the 
third element of Q.sup.24. Therefore, a recursive calculation for partial 
syndrome S.sub.1 of the Q codewords, which is similar to the recursive 
calculation for syndromes S.sub.1 of P codewords is not used since there 
are no previous intermediate values. That is, when data byte "2" arrives, 
corresponding to the third element of Q.sup.24, there are no previous 
intermediate values corresponding to the first and second elements of 
Q.sup.24 since the data bytes corresponding to these elements are data 
bytes 1032 and 1076, respectively. Under this condition, recursion 
generally cannot be used. 
The computation of S.sub.1 syndromes for Q codewords can generally be 
expressed as follows: 
EQU S.sub.1 =(d.sub.44 .alpha..sup.44).sym.(d.sub.43 .alpha..sup.43).sym.. . . 
.sym.(d.sub.1 .alpha..sup.1)(d.sub.0 .alpha..sup.0) 
where d.sub.m are the data bytes associated with a Q codeword which 
contains 45 elements. To compute the partial syndrome S.sub.1 for a Q 
codeword, each element of the Q codeword is essentially multiplied by a 
power of .alpha.. It should be appreciated that the general format of 
expressions used in the calculation of partial syndrome S.sub.1 for Q 
codewords and partial syndrome S.sub.1 for P codewords are substantially 
the same, with the main difference being a function of the lengths of the 
codewords. 
The computation of partial syndrome S.sub.1 for Q codewords is accomplished 
using an alpha down counter 452 which provides an output that is applied 
to data bytes passed from multiplexer 424 using a multiplier 454. Alpha 
decrementing counter 452 in arranged to be loaded with an appropriate 
power of .alpha. and thence downcounted for use in computing partial 
syndrome S.sub.1 for the Q codewords. The data bytes then pass through 
adder 456 where the data bytes are added, using an exclusive OR 456, to 
any associated intermediate results obtained from Q.sub.-- BUF 414 in 
order to update the associated intermediate results. Once the intermediate 
results are updated, the updated intermediate results are written back 
into Q.sub.-- BUF 414 into the same locations from which the intermediate 
results were obtained. It should be appreciated that once the last data 
byte has been added to the intermediate results, the contents of Q.sub.-- 
BUF 414 are then considered to be partial syndrome S.sub.1 for the Q 
codewords. 
Once the partial syndromes are calculated, the partial syndromes can be 
clocked out of P.sub.-- BUF 412 and Q.sub.-- BUF 414, through multiplexers 
458 and 460, respectively, to registers 470 and 472. Specifically, partial 
syndrome So associated with the P codewords are clocked out of P.sub.-- 
BUF 412 on line 462, which is an input to multiplexer 458. Multiplexer 458 
provides inputs to register 470. Similarly, partial syndrome S.sub.0 
associated with the Q codewords are clocked out of Q.sub.-- BUF 414 on 
line 466 which is also an input to multiplexer 470. Partial syndrome 
S.sub.1 associated with the P codewords are clocked out of P.sub.-- BUF 
412 on line 464, which is an input to multiplexer 460. As shown, 
multiplexer 460 provides inputs to a register 472. Partial syndrome 
S.sub.1 associated with the Q codewords are clocked out of Q.sub.-- BUF 
414 on line 468, which is also an input to multiplexer 460. Therefore, the 
partial syndromes can be accessed through registers 470 and 472. 
FIG. 14 is a block diagram representing syndrome address logic in 
accordance with an embodiment of the present invention. A circuit 480 
includes a binary counter I.sub.-- CNTR 482 associated with columns of a 
data matrix, as for example the data matrix described above with respect 
to FIG. 5, and a binary counter K.sub.-- CNTR 484 associated with the rows 
of a data matrix. As each data byte arrives sequentially from a DRAM, an 
appropriate address to a P.sub.-- BUF and a Q.sub.-- BUF is generated. 
With reference to FIG. 13, P.sub.-- RADR is used to address the read port 
of P.sub.-- BUF 412 while P.sub.-- WADR is used to address the write port 
of P.sub.-- BUF 412. Similarly, Q.sub.-- RADR is used to address the read 
port of Q.sub.-- BUF 414, while Q.sub.-- WADR is used to address the write 
port of Q.sub.-- BUF 414. 
I.sub.-- CNTR 482 is a modulo 42 binary counter which increments as each 
byte arrives. K.sub.-- CNTR 484 is a binary counter which increments when 
I.sub.-- CNTR 482 has reached the count of 42, signaling the beginning of 
the next row in a data matrix. In general, I represents the contents of 
I.sub.-- CNTR 482 and K represent the contents of K.sub.-- CNTR 484. 
Q.sub.-- RADR can then generated as follows: 
EQU Q.sub.-- RADR=[26+K-(I modulo 26)]modulo 26 
FIG. 15 is a process flow diagram which outlines an enhanced EDAC process, 
i.e., an ECC process, in accordance with an embodiment of the present 
invention, as will be described in more detail below. The present 
invention allows the computation of the P and Q partial syndromes to occur 
substantially on-the-fly as data arrives sequentially. As such, there is 
dedicated circuitry for computing the partial syndromes, as described 
above with respect to FIG. 13, which relies upon storing intermediate 
results in the P and Q Buffers as each data byte is processed. 
As will be appreciated by those skilled in the art, the data organization 
for either the low-order or high-order data bytes in a data matrix is such 
that the entry in each cell is the DRAM word address of where a particular 
data byte is located. As each data byte arrives sequentially from the 
DRAM, a determination must be made as to which P codeword and which Q 
codeword the data byte "belongs" to in order to access the corresponding 
entry in the P.sub.-- BUF and the Q.sub.-- BUF. 
FIG. 16 is a data matrix which shows the identification of P codewords 
contained therein in accordance with an embodiment of the present 
invention. Within a data matrix 520, entries in each cell 524 correspond 
to the P.sub.-- BUF address which is accessed in the course of computing 
the P partial syndromes. In other words, as data bytes arrive from DRAM, 
an identification can be made of which P codeword the data byte is an 
element of. FIG. 17 is a data matrix which shows the identification of Q 
codewords contained therein in accordance with an embodiment of the 
present invention. Entries in each cell 530 of a data matrix 528 
correspond to the Q.sub.-- BUF address which is accessed when the Q 
partial syndromes are computed. In other words, as each 
sequentially-arriving data bytes arrive from DRAM, an identification is 
made of which Q codeword the data byte is an element of. Each 
sequentially-arriving data byte requires an access to specified addresses 
of P.sub.-- BUF and Q.sub.-- BUF. 
As previously mentioned, in one embodiment, a P.sub.-- BUF is 43 locations 
long. Each location is arranged to hold the two partial syndromes for each 
P.sup.i codeword. FIG. 18 is a diagrammatic representation of the contents 
of a P.sub.-- BUF in accordance with one embodiment of the present 
invention. A P.sub.-- BUF 536 has 43 address locations 538 each of which 
holds the partial syndromes for a P codeword. By way of example, a first 
address location 538a is arranged to hold S.sub.0 and S.sub.1 for codeword 
P.sup.0, while a forty-third address location 538f is arranged to hold 
S.sub.0 and S.sub.1 for codeword P.sup.42. 
In general, the computation of S.sub.0 is simply the modulo-2 addition of 
substantially all of the data bytes which make up the codeword, including 
the parity bytes associated with the codeword. Consequently, there is no 
particular ordering of the data bytes. The steps associated with the 
computation of S.sub.0 for a P codeword assumes that P.sub.-- BUF is 
initialized with zeroes. The partial syndromes for all P.sup.i and q.sup.j 
are computed and stored in P.sub.-- BUF and Q.sub.-- BUF. As each data 
byte arrives the contents of P.sub.-- BUF are accessed at a given 
location, as shown in FIG. 16, added to the arriving data byte, and then 
rewritten back into P.sub.-- BUF at the same location. That is, the 
previously stored intermediate results for S.sub.0 are obtained from a 
given location, added to the newly arrived data byte, and then written 
back into the same location for each newly arrived data byte. In order to 
perform such operation at full speed, the P.sub.-- BUF is a dual-ported 
memory, with the write port of the P.sub.-- BUF configured as a 
synchronous port. 
FIG. 19 shows the overall timing for obtaining intermediate results for 
S.sub.0 from a given location, adding the results to a new data byte, and 
then writing the modified results into the same location in accordance 
with an embodiment of the present invention. That is, FIG. 19 illustrates 
the overall timing associated with computing partial syndrome S.sub.0. As 
shown, the first 43 bytes, corresponding to the first element of each of 
the 43 P codewords, are written into a P.sub.-- BUF. After the first 43 
data bytes are obtained, the partial syndrome calculations are performed 
by first reading the previously calculated intermediate from the location 
in the P.sub.-- BUF, adding the intermediate results from the P.sub.-- BUF 
to the incoming data byte, and then writing back the result into the 
original location within P.sub.-- BUF. It should be appreciated that the 
specific location accessed within P.sub.-- BUF is determined by which P 
codeword the incoming data byte is an element of, as shown in FIG. 16. As 
shown in FIG. 19, the data is obtained from DRAM, the intermediate value 
is read from the P.sub.-- BUF, and the intermediate value is updated 
during approximately one clock cycle. The updated intermediate value is 
then stored into the associated location, or the location from which the 
original intermediate value was obtained in the P.sub.-- BUF during the 
next clock cycle, while the next intermediate value is obtained and 
processed as before. This process is repeated until all data values have 
be obtained from DRAM and processed. 
Mathematically, the computation for S.sub.1 can be expressed as follows: 
EQU S.sub.1 =(d.sub.n-1 .alpha..sup.n-1).sym.(d.sub.n-2 .alpha..sup.n-2).sym.. 
. . .sym.(d.sub.1 .alpha..sup.1)(d.sub.0 .alpha..sup.0) 
where d.sub.k are the data from the DRAM which arrives sequentially. FIG. 
20 is a diagram of a circuit which is suitable for computing S.sub.1 
recursively in accordance with an embodiment of the present invention. A 
circuit 544 is arranged such that coefficients of a received polynomial 
r(x) are passed through adder 546, which functions as modulo-2 adder using 
an exclusive OR circuit. The output from adder 546 is multiplied by 
.alpha.548 in order to obtain an intermediate value as part of the overall 
calculation of partial syndrome S.sub.1. Once obtained, the value is 
clocked into a register, or flip-flop 549. Using circuit 544, data bytes 
arriving sequentially are added to previously calculated intermediate 
results multiplied by .alpha.. It should be appreciated that the ordering 
of the bytes is important as is required for Horner's rule, which is 
embodied by circuit 544. 
In one embodiment, the method of calculating S.sub.1 involves substituting 
P.sub.-- BUF for flip-flop 549 in circuit 544. When flip-flop 549 is 
replaced with P.sub.-- BUF, as each data byte arrives the appropriate 
contents of P.sub.-- BUF, as shown in FIG. 16, are read, multiplied by 
.alpha., added to the incoming data byte, and then rewritten back into 
P.sub.-- BUF. 
FIG. 21 is a timing diagram associated with calculating partial syndrome 
S.sub.1 in conjunction with P.sub.-- BUF. As shown, the first 43 bytes 
from the DRAM are written into the P.sub.-- BUF. After the first 43 data 
bytes are obtained, partial syndrome S.sub.1 is calculated by reading the 
intermediate value from an appropriate location in the P.sub.-- BUF, 
performing arithmetic operations on the intermediate value obtained from 
the P.sub.-- BUF to the incoming data byte obtained from DRAM, and then 
rewriting the result back into P.sub.-- BUF. It should be appreciated that 
the specific location accessed within P.sub.-- BUF is determined by which 
P codeword the incoming data byte is an element of, as shown in FIG. 16. 
It should be appreciated that this generally operation takes one clock 
cycle and, hence, the S.sub.1 partial syndrome calculations and S.sub.0 
partial syndrome calculations can occur substantially simultaneously. 
As previously mentioned, a Q.sub.-- BUF is 26 locations long, with each 
location holding the two partial syndromes associated with each Q.sup.j. 
FIG. 22 is a representation of Q.sub.-- BUF in accordance with an 
embodiment of the present invention. A Q.sub.-- BUF 552 includes 26 
address locations 554. Each address location 554 contains S.sub.0 and 
S.sub.1 for a given Q.sup.j. For example, a first address location 554a 
contains S.sub.0 and S.sub.1 for Q.sup.0, while a twenty-sixth address 
location 554f contains S.sub.0 and S.sub.1 for Q.sup.25. 
In general, the computation of S.sub.0 for Q codewords is substantially 
identical to the computation of S.sub.0 for the P codewords. In other 
words, the computation of S.sub.0 for a particular Q codeword is the 
modulo-2 addition of all data bytes, including parity bytes, which make up 
the Q codeword. As such, the data bytes do not need to be in any 
particular order. 
The steps involved in the computation of S.sub.0 for the Q codewords 
assumes that Q.sub.-- BUF is initialized with zeroes. As each data bytes 
arrive sequentially, the appropriate contents of Q.sub.-- BUF are read 
from a given location, as defined by FIG. 17, added to the incoming data 
byte, and then rewritten into the same location in Q.sub.-- BUF. In order 
to perform this operation at full speed, the Q.sub.-- BUF, like the 
P.sub.-- BUF, is a dual-ported memory, with the write port configured as a 
synchronous port. 
Typically, the computation of S.sub.1 for Q codewords differs substantially 
from the computation of S.sub.1 for P codewords. Computing S.sub.1 for P 
codewords recursively was possible because the sequentially-arriving data 
bytes from DRAM were in the right order so far as the elements making up 
the P codewords. That is, each element making up a P codeword arrives 
sequentially, in the desired order, thereby enabling the recursive circuit 
shown in FIG. 20 to be used. That is possible because the first 
sequentially-arriving 43 bytes correspond to the first elements of each of 
the P codewords, the next sequentially-arriving 43 bytes correspond to the 
second elements of each of the P codewords, and so forth. In this way, the 
intermediate results stored in P.sub.-- BUF are correct in that they allow 
a recursive calculation of S.sub.1 such that the ordering of the elements 
of the codewords is preserved. 
In the computation of S.sub.1 for Q codewords, however, the data bytes do 
not arrive sequentially from the point of view of the elements that make 
up each of the Q codewords. For example, when data byte "1" arrives, it is 
the second element of Q.sup.25. That is, the first element of codeword 
Q.sup.25 had not previously arrived such that the recursive calculation 
method can be used. Consequently, the recursive circuit of FIG. 20 cannot 
be used in the computation of S.sub.1 for the Q codewords since the 
recursion requires the sequential ordering of the elements making up the 
codeword. Instead, the fundamental definition of S.sub.1 can be used as a 
means of finding a way to calculate S.sub.1 for the Q codewords, thereby 
allowing the computation of the partial syndromes to occur using a single, 
sequential pass through DRAM. 
S.sub.1 as previously mentioned, can be defined as follows: 
EQU S.sub.1 =(d.sub.n-1 .alpha..sup.n-1).sym.(d.sub.n-2 .alpha..sup.n-2).sym.. 
. . .sym.(d.sub.1 .alpha..sup.1)(d.sub.0 .alpha..sup.0) 
As such, by multiplying each element of a Q codeword by the appropriate 
power of .alpha., S.sub.1 can computed. Since each Q codeword contains 45 
elements, with reference to the columns of the data matrix shown in FIG. 
5, the first element of each Q codeword resides in column 0, the second 
element of each Q codeword resides in column 1, and so forth up to element 
43 in column 42. Elements 44 and 45 of the Q codewords differ, however, in 
that they are in rows 26 and 27, as shown in FIG. 17. 
To compute S.sub.1, the elements corresponding to column 0 of a data 
matrix, FIG. 5, are multiplied by .alpha..sup.44, elements in column 1 are 
multiplied by .alpha..sup.43, and so forth up to column 42, whose elements 
are multiplied by .alpha..sup.2. The Q parity bytes, in rows 26 and 27 of 
the data matrix, are multiplied by .alpha..sup.1 and .alpha..sup.0, 
respectively. FIG. 23 is a circuit which is suitable for computing S.sub.1 
for the Q codewords in accordance with an embodiment of the present 
invention. A circuit 560 includes a decrementing counter, i.e., alpha down 
counter 562, which counts down in powers of .alpha.. Data bytes passed 
into circuit 560 are multiplied by a power of .alpha., then added to an 
appropriate intermediate value of S.sub.1 obtained from Q.sub.-- BUF 564. 
With respect to FIG. 13 and FIG. 14, alpha down counter 452 is initially 
loaded with .alpha..sup.44, while I.sub.-- CNTR 482 is initialized with 0. 
As each data byte arrives, corresponding to the first row of matrix 228, 
FIG. 5, alpha down counter 452 is decremented, while I.sub.-- CNTR 482 is 
incremented. Then, when data byte "1" arrives, the second data byte, alpha 
down counter 452 contains the value .alpha..sup.43 while I.sub.-- CNTR 482 
is 1. When data byte "2", the third data arrives, alpha down counter 452 
contains the value .alpha..sup.42 and I.sub.-- CNTR 482 contains 2. When 
data byte "42" arrives, the last data byte of row 0, alpha down counter 
452, contains the value .alpha..sup.2, and I.sub.-- CNTR 482 contains the 
value 42. At this point, K.sub.-- CNTR 484 is incremented in preparation 
for data byte 43, the first byte of the second row, row 1. In addition, 
I.sub.-- CNTR 482, is reinitialized with zero, corresponding to the first 
column, while alpha down counter 452 is reinitialized with the value 
.alpha..sup.44, the value corresponding to column 0. 
FIG. 15 is a process flow diagram which outlines an enhanced EDAC process, 
i.e., an ECC process, in accordance with an embodiment of the present 
invention. By storing the partial syndromes in P.sub.-- BUF and Q.sub.-- 
BUF, in step 490, correction operations can be performed without accessing 
DRAM until the corrected data values are to be written into DRAM. 
Prior to attempting a single error correction, S.sub.0 and S.sub.1 are 
inspected to determine what actions can be taken, as summarized in FIG. 
24. As shown in FIG. 24, when S.sub.0 and S.sub.1 have zero values, no 
errors are present in an associated codeword. Therefore, no corrective 
action is necessary. Alternatively, when one of S.sub.0 and S.sub.1 has a 
zero value while the other has a non-zero value, in one embodiment, single 
error correction is not considered to be possible. However, when both 
S.sub.0 and S.sub.1 have non-zero values, then single error correction is 
considered to be possible. 
If there is a single error in a P codeword, a SEC operation, step 492, can 
be performed. The location of the error may be obtained from partial 
syndromes S.sub.0 (P.sup.i) and S.sub.1 (P.sup.i) as follows: 
EQU k=log.sub..alpha. (S.sub.1 (P.sup.i)/S.sub.0 (P.sup.i))=[log.sub..alpha. 
S.sub.1 (P.sup.i)-log.sub..alpha. S.sub.0 (P.sup.i)+255]modulo 255 
where S.sub.0 (P.sup.i) contains the error pattern, and k is the subscript 
of P.sub.k, the location of an error in codeword P.sup.i. 
A single error-correcting Reed-Solomon code is guaranteed to correct one 
random error in a codeword. If there are two or more errors in a codeword, 
either a miscorrection occurs or an uncorrectable event results. By 
definition, a miscorrection cannot be detected. However, an uncorrectable 
event can be detected by performing a range check on the computed value of 
location k. In general, for each P.sup.i, k is in the range of 
0.ltoreq.k.ltoreq.25. In the event that k lies outside of this range, the 
determination is that an uncorrectable event has taken place. 
Once k is determined, the corresponding data byte from DRAM is accessed, 
modified, and then re-written with the correct value. Given values for k 
and i, the corresponding address in memory can be computed as follows: 
EQU DRAM address=(43*k+i) modulo 1118 
When the errored byte, d, is obtained, the corrected data byte d' is 
obtained as follows: 
EQU d'=d.sym.S.sub.0 (P.sup.i) 
After d' is computed, d' is re-written into the same address location that 
d was obtained from. 
Each data byte is simultaneously encoded in a P codeword and a Q codeword. 
Therefore, if a single-error correction (SEC) is performed on a P 
codeword, then the partial syndromes of the intersecting Q codeword, 
PQ.sub.m must be modified as well, step 493, since the affect of the error 
in the P codeword is also contained in the partial syndrome of the 
intersecting Q codeword. 
To modify the PQ.sub.m partial syndromes, which are the m-th elements 
within Q codewords that intersect with a specific elements within P 
codewords, a determination is made regarding which Q.sup.j and which 
Q.sub.l are affected by P.sub.k. In order to determine l, the following 
relationship can be used: 
EQU l=i 
Q.sup.j, in turn, can be determined using the following relationship: 
EQU k'=25-k 
EQU j=[26+(k'-(1 modulo 26))]modulo 26 
where i is the superscript of P.sup.i, j is the superscript of Q.sup.j, k' 
is the subscript of P.sub.k, and 1 is the subscript of Q.sub.l. 
Once j is calculated, the partial syndromes for Q.sup.j can be obtained, 
and the update calculations proceed as follows: 
EQU S.sub.0 (Q.sup.j)'=S.sub.0 (P.sup.i).sym.S.sub.0 (Q.sup.j) 
EQU S.sub.1 (Q.sup.j)'=(S.sub.0 (P.sup.i).alpha..sup.(44-1)).sym.S.sub.1 
(Q.sup.j) 
where S.sub.0 (Q.sup.j)'and S.sub.1 (Q.sup.j)' are the updated partial 
syndromes, S.sub.0 (Q.sup.j) and S.sub.1 (Q.sup.j) are the original 
partial syndromes stored in Q.sub.-- BUF, S.sub.0 (P.sup.i) and S.sub.1 
(P.sup.i) are the P.sup.i partial syndromes, and 1 is the subscript of 
Q.sub.1. The effect of the update calculations, therefore, is to "back 
out" the contribution of the error from the partial syndromes for the 
intersecting Q codeword. It should be appreciated that the exponent of 
.alpha. is referenced to the end of Q.sup.j, while Q.sub.1 is referenced 
from the beginning of Q.sup.j. As shown in FIG. 15, steps 492 and 493, as 
described above, are repeated for each P.sup.i. After all P codewords have 
been processed, the Q codewords are next processed. 
If there is a single error in a Q codeword, step 495, the location of the 
error may be obtained from the partial syndromes S.sub.0 (Q.sup.j) and 
S.sub.1 (Q.sup.j) as follows: 
EQU 1=log.alpha.(S.sub.1 (Q.sup.j)/S.sub.0 (Q.sup.j))=[log.sub. .alpha.S.sub.1 
(Q.sup.j)-log.sub..alpha. S.sub.0 (Q.sup.j)+255]modulo 255 
where S.sub.0 (Q.sup.j) contains the error pattern, and 1 is the subscript 
of Q.sub.1. A range check is performed to ensure that 1 is in the range of 
2.ltoreq.1.ltoreq.44. In the event that 1 lies outside of the specified 
range, the indication is that an uncorrectable event has taken place. Once 
1 is determined, the corresponding data byte from DRAM is accessed, 
modified, and then re-written back into DRAM with the correct value. 
After 1 and have been determined, the corresponding address in memory, ie., 
DRAM address, is computed as follows: 
EQU DRAM address=(44*1+43*k) modulo 1118 
with: 
EQU k=(j+1) modulo 26 
where j is the superscript of Q.sup.j and 1 is the subscript of Q.sub.1. 
When the errored byte, d, is obtained from memory, the corrected value d' 
is given by: 
EQU d'=d.sym.S.sub.0 (Q.sup.j) 
After d' is calculated, d' is re-written into the same address in memory 
from which d was obtained. 
If a SEC is performed on a Q codeword, then the partial syndromes of the 
intersecting P codeword, QP.sub.n, are also modified in step 496, due to 
the fact that the affect of the error in the Q codeword is also contained 
in the partial syndrome of the intersecting P codeword. To modify the 
QP.sub.n partial syndromes, it is necessary to determine which P.sup.i and 
P.sub.k are affected by Q.sub.1. 
P.sup.i can be determined using the following relationship: 
EQU l'=44-1 
EQU i=l' 
where i is the superscript of P.sup.i and l' is the subscript of Q.sub.1. k 
can be determined as follows: 
EQU k=(j+1) modulo 26 
where 1 is the subscript of Q.sub.1 and i is the superscript of P.sup.i. 
Once i is calculated, and the partial syndromes for P.sup.i are obtained, 
the partial syndromes can be updated as follows: 
EQU S.sub.0 (P.sup.i)=S.sub.0 (Q.sup.j).sym.S.sub.0 (P.sup.i) 
EQU S.sub.1 (P.sup.i)'=S.sub.0 (Q.sup.j).alpha..sup.(25-k) .sym.S.sub.1 
(P.sup.i) 
where S.sub.0 (P.sup.i)' and S.sub.1 (P.sup.i)' are the updated partial 
syndromes, S.sub.0 (P.sup.i) and S.sub.1 (P.sup.i) are the original 
partial syndromes stored in P.sub.-- BUF, S.sub.0 (Q.sup.j) and S.sub.1 
(Q.sup.j) are the Q.sup.j partial syndromes, and k is the subscript of 
P.sub.k. In general, the effect of the updating calculations, therefore, 
is to "back out" the contribution of the error from the partial syndromes 
for the intersecting P codeword. The exponent of a is typically referenced 
to the end of P.sup.i, while P.sub.k is typically referenced from the 
beginning of P.sup.i. As shown in FIG. 15, steps 495 and 496 are repeated 
for each Q.sup.j. After all Q codewords have been processed, the 
correction operations are repeated in accordance with a setting for N. 
An enhanced mechanism for generating parity bytes can be accomplished 
through the use of one sequential pass through memory by using the 
existing partial syndrome computation circuitry, as described above with 
respect to FIGS. 13 and 14. As described above, a single error-correcting 
Reed-Solomon code can be used either to correct a single random error, or 
to correct two erasures. FIG. 25 is a representation of a codeword in 
which parity bytes have been erased in accordance with an embodiment of 
the present invention. 
Computing the partial syndromes for a codeword 570 in which parity byte 
positions 572, 574 have been obliterated can be accomplished using a 
single error-correcting Reed-Solomon code. Since the locations of errors 
are known, the correct parity bytes can be "filled in" through the use of 
erasure decoding. In essence, to generate parity bytes, partial syndromes 
are computed for the data for which parity bytes are to be generated in 
substantially the same manner as used for generating codewords for 
CD-ROMs. However, correction operations are now applied in order to 
generate the correct parity bytes. 
Such a method for correcting parity bytes can be accomplished using one 
sequential pass through memory, thus preserving memory bandwidth. In 
addition, by enabling substantially the same partial syndrome circuitry to 
be used for both correction operations as well as for generating parity 
bytes, the amount of circuitry associated with the two processes can be 
reduced. 
When there are exactly two errors in a codeword, the partial syndromes for 
the codewords can be represented as follows: 
EQU S.sub.0 =v1.sym.v2 
EQU S.sub.1 =(v1.alpha..sup.loc1).sym.(v2.alpha..sup.loc2) 
where v1 is the error pattern at a first error location, ie., loc1, and v2 
is the error pattern at a second error location, i.e., loc2. When both 
error locations are known, .alpha..sup.loc1 and .alpha..sup.loc2 are fixed 
numbers. When .alpha..sup.loc1 and .alpha..sup.loc2 are fixed numbers, v1 
and v2 can be determined by an elimination of variables. As such, v1 and 
v2 can be obtained as follows: 
EQU v1=(S.sub.1 .sym.(S.sub.0 .alpha..sup.loc2))/(.alpha..sup.loc1 
.sym..alpha..sup.loc2) 
EQU V2=(S.sub.1 .sym.(S.sub.0 .alpha..sup.loc1))/(.alpha..sup.loc1 
.sym..alpha..sup.loc2) 
In the case of "erased" parity byte locations, the following relationships 
are defined: 
EQU loc1=0 
EQU loc2=1 
In other words, the parity bytes are always located at the last two 
positions of the codeword, which corresponds to .alpha..sup.0 and 
.alpha..sup.1. As such, corresponding parity bytes PB0 and PB1 can be 
expressed as: 
EQU PB0=v1=(S.sub.1 .sym.(S.sub.0 .alpha..sup.1))/(.alpha..sup.0 
.sym..alpha..sup.1) 
EQU PB1=v2=(S.sub.1 .sym.(S.sub.0 .alpha..sup.0))/(.alpha..sup.0 
.sym..alpha..sup.1) 
In other words, the "error patterns" are precisely the parity bytes that 
are sought. Since .alpha..sup.0 .alpha..sup.1 =.alpha..sup.25 in 
GF(2.sup.8), the expressions for PB0 and PB1 can be rewritten as: 
EQU PB0=(S.sub.1 .sym.(S.sub.0 .alpha..sup.1))/.alpha..sup.25 
EQU PB1=(S.sub.1 .sym.(S.sub.0 .alpha..sup.0))/.alpha..sup.25 
In general, the parity bytes for each of the P and Q codewords are 
generated by computing the P and Q partial syndromes for the data field, 
FIG. 5, in the same manner as is done for an error correction operation 
described with respect to FIG. 15. The essential difference between the 
computations is that for computing parity bytes, in one embodiment, 
processing stops upon the arrival of word 1031 from the DRAM memory. 
Erasure decoding is then performed on each of the partial syndromes in 
P.sub.-- BUF. After erasure decoding takes place, each entry in P.sub.-- 
BUF contains the computed parity bytes for each of the P codewords. 
The Q partial syndromes are next updated with the newly computed P parity 
bytes since the Q codewords include the parity bytes of the P codewords. 
The processing of parity bytes is completed with the performance of 
erasure decoding on the partial syndromes in Q.sub.-- BUF, such that each 
of the partial syndromes is replaced with the newly computed parity bytes. 
Once both P.sub.-- BUF and Q.sub.-- BUF are updated, in one embodiment, 
the contents of P.sub.-- BUF and Q.sub.-- BUF are written into DRAM. It 
should be appreciated that erasure decoding is typically first performed 
on p.sup.i rather than on Q.sup.j due to the fact that Q.sup.j encodes the 
parity bytes of P.sup.i. 
When the partial syndromes for a data field are computed, substantially all 
the information necessary for computing the P parity bytes is available. 
However, after the partial syndromes are computed, sufficient information 
does not exist for computing the Q parity bytes. The lack of sufficient 
information for computing the Q parity bytes stems from the fact that Q 
codewords include the P parity bytes. At the conclusion of the partial 
syndrome computation for the data field, though, parity bytes for the P 
codewords have not yet been computed. Therefore, the partial syndromes for 
the Q codewords are still not completed. As such, it is first necessary to 
compute the P parity bytes before continuing with the computation of Q 
partial syndromes in order to include the newly computed P parity bytes in 
the computation of the Q partial syndromes. After the Q partial syndromes 
are computed, erasure decoding can then be performed on the Q partial 
syndromes to compute parity bytes for the Q codewords. 
FIG. 26 is a representation of the contents of a P.sub.-- BUF after the 
partial syndromes are computed, but prior to performing erasure decoding, 
in accordance with an embodiment of the present invention. P.sub.-- BUF 
580, as previously mentioned, includes address locations 582 which contain 
partial syndromes S.sub.1 and S.sub.0. After erasure decoding is performed 
at each address location 582, the contents of P.sub.-- BUF 580 are 
essentially transformed from partial syndromes into parity bytes, as shown 
in FIG. 27. Such a transformation occurs by performing erasure decoding on 
the contents associated with each address location 582 after the partial 
syndromes for the data field are computed. 
With reference to FIG. 28, the computation of the Q partial syndromes using 
the P parity bytes will be described in accordance with an embodiment of 
the present invention. The P parity bytes are used as input to the Q 
partial syndrome computation circuit 590 to finish the computations 
associated with determining the partial syndromes for the Q codewords. The 
Q partial syndrome computation circuit 590 includes P.sub.-- BUF 594 and 
Q.sub.-- BUF 596 which are part of P.sub.-- BUF feedback sub-circuit 595 
and Q.sub.-- BUF sub-circuit 597, respectively. P.sub.-- BUF feedback 
sub-circuit 596 is arranged to generate P parity bytes which are then 
provided to Q.sub.-- BUF sub-circuit 597, which is substantially the same 
as the Q partial syndrome computation circuit described above with respect 
to FIG. 23. Q.sub.-- BUF sub-circuit 597 then computes the Q partial 
syndromes. 
The Q partial syndrome computation circuit 590 basically uses the contents 
of P.sub.-- BUF 594, which contain P parity bytes, as data for a 
correction operation. In other words, for a correction operation, the P 
parity bytes are processed along with the data field. When the P parity 
bytes are processed, however, the P parity bytes are extracted from 
P.sub.-- BUF 594, rather than from DRAM memory, from which the data field 
is extracted. 
It should be appreciated that, according to the described embodiment, when 
correction processing reaches the P parity bytes in row 24 of a data 
matrix, e.g., row 230i data matrix 228 of FIG. 5, the contents of each 
low-order byte of P.sub.-- BUF, which contains parity bytes PB0, is routed 
through a multiplexer in an overall partial syndrome computation circuit, 
e.g., multiplexer 424 of FIG. 13. The contents of each low-order byte is 
routed through a multiplexer since the bytes are the "data" needed to 
compute the Q codeword partial syndromes. Similarly, when correction 
processing reaches the parity bytes in row 25 of a data matrix, e.g., row 
230j in data matrix 228 of FIG. 5, the multiplexer 424 of FIG. 13 selects 
the high-order byte of P.sub.-- BUF in order to route parity bytes PB 1 
through the Q partial syndrome computation circuitry. 
Referring back to FIG. 28, after the P parity bytes are routed through 
Q.sub.-- BUF subcircuit 597, Q.sub.-- BUF 596 contains the syndromes for 
both the data field and the P parity bytes. Then, erasure decoding is 
performed using the Q partial syndromes to generate the parity bytes for 
the Q codewords, as shown in FIGS. 29 and 30. FIG. 29 is a representation 
of Q.sub.-- BUF prior to the generation of the Q parity bytes in 
accordance with an embodiment of the present invention. Q.sub.-- BUF 602 
includes partial syndromes S.sub.1 and S.sub.0 at each address location 
604. After erasure decoding is performed at each address location 604, the 
contents of Q.sub.-- BUF 602 are essentially transformed from partial 
syndromes into parity bytes, as shown in FIG. 30. Such a transformation 
occurs by performing erasure decoding on the contents of each address 
location 604 after the Q partial syndromes for the data field are 
computed. 
After the P parity bytes and Q parity bytes are generated, the parity bytes 
can be written to DRAM. In one embodiment, writing parity bytes into DRAM 
can be accomplished by reading out the contents of P.sub.-- BUF and 
reading out the contents of Q.sub.-- BUF. Once the parity bytes are 
written into DRAM, the generation of the parity bytes is considered to be 
completed. 
Although only a few embodiments of the present invention have been 
described, it should be understood that the present invention may be 
embodied in many other specific forms without departing from the spirit or 
the scope of the present invention. By way of example, the number of 
redundancy bits, or parity bits, can be widely varied depending upon the 
number of errors which are to be corrected in a codeword. As a result, the 
length of codewords, both P codewords and Q codewords, can also be widely 
varied. Therefore, the described embodiments should be taken as 
illustrative and not restrictive, and the invention should be defined by 
the following claims and their full scope of equivalents.