Abstract:
System and method for improved formation of a Q-parity checkbyte matrix used for error control for a sequence of message bytes and error control bytes, using an algorithm, rather than a lookup table, to determine the order of the words used for the sequence. Entries of a Reed-Solomon parity check rectangular array are set up sequentially and diagonally, including the syndrome bytes and checkbytes to be used for error detection, so that all matrix entries can be written to, or read from, a computer memory in a stream of bytes whose order is determined by the algorithm without reference to a lookup table.

Description:
FIELD OF THE INVENTION 
     This invention relates to indexing of parity checkbytes and the associated message bytes for digital message error control operations. 
     BACKGROUND OF THE INVENTION 
     One method of error control for digital signals uses P-parity and Q-parity checkbytes to provide a means of identifying the presence of, and location of one or more errors in a digital message. The error correction code (ECC) used in this approach is a product code over the Galois field GF( 2   8 ), where each byte is a symbol and a word consists of two bytes (MSB and LSB, or “upper” and “lower”). Consecutive words in a block are numbered n=0, 1, . . . , 1169, and the numbering begins immediately following the end of the sync pattern or other preamble. The entire block, excluding the sync pattern, is protected against (some) errors by the ECC. Column code words and row code words are referred to as P(parity)-words and Q(parity)-words, respectively. 
     In a conventional approach, the elements s i,j  for a P-parity matrix and/or the Q-parity matrix are written to and read from a lookup table one at a time. These operations are repetitive but are treated as if they are individually defined. What is needed is an approach that takes advantage of the repetitive nature of the operations to obtain a sequence of read or write operations that can be performed in less time and with less logic hardware. Preferably, the approach should be flexible enough to permit its application to any size parity matrices and with any reasonable primitive polynomial equation that may be chosen. 
     SUMMARY OF THE INVENTION 
     These needs are met by the invention, which sets up an sequence of identical read (or write) operations in which the argument or index increases or decreases in a definable manner. An approach is implemented that writes to, or reads from, an entire Q-parity data sequence (1170 entries) in an ordered manner. A Q-parity data sequence includes all the data entries in a P-parity sequence but uses a diagonal format so that the entries appear in a non-intuitive and mixed-up order. The approach accounts for this and for the looping back of the data elements representing the Q-parity sequence. The entries can be written in a burst mode format that reduces the time required to process all the entries. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIGS. 1A,  1 B and  2  illustrate the desired action for reading to, or writing from, a sequence of entries for a P-parity word and a Q-parity word. 
     FIGS. 3 and 4 are flow charts illustrating use of the invention to perform a Q-parity error control processing operation, such as read or write. 
    
    
     DESCRIPTION OF THE INVENTION 
     FIG. 1A illustrates a data element array, expressed as a parity matrix (s i,j ) (0≦i≦25; 0≦j≦42) of 26 rows and 43 columns, used in parity-based error control for digital signals. Each entry s(r) (r=0, 1, 2, . . . , 1031) in the rows of the array or matrix, numbered 0, 1, . . . , 23 (1032 entries), is part of the sequence of digital signal bytes that make up a block of the “bare” message, without error control bytes appended. Each entry in the rows numbered 24 and 25 (86 entries, numbered 1032, 1033, . . . , 1117) is part of a P-parity checkbyte appended to the “bare” message for ECC (error correction) action. As indicated in FIG. 1A, the P-parity indices Mp and Np have the ranges 0≦Mp≦25 and 0≦Np≦42 and are assigned in a straightforward manner using sequences defined along horizontal rows (Np) or vertical columns (Mp). Two Q-parity checkbytes with entries s(r), shown in FIG. 1B are included as part of the error control procedure: Q 0 , with entries numbered r=1118, 1119, . . . , 1143, and Q 1 , with entries numbered r=1144, 1145, . . . , 1169. 
     FIG. 1A also indicates the assignment of Q-parity indices, which are determined using sequences of entries that are defined along each of 26 diagonals, with each complete diagonal having 43 entries. Each diagonal includes 43 entries, beginning at a different position on the left side of the array for each new pass. For example, the addresses of the 43 entries in the first diagonal Q( 0 ) of the array shown in FIG. 1A are, in order: 0000, 0044, 0088, 0132, 0176, 0220, 0264, 0308, 0352, 0396, 0440, 0484, 0528, 0572, 0616, 0660, 0704, 0748, 0792, 0836, 0880, 0924, 0968, 1012, 1056, 1100, 0026, 0070, 0114, 0158, 0202, 0246, 0290, 0334, 0378, 0422, 0466, 0510, 0554, 0598, 0642, 0686, 0730, after application of a (modulo 1118) operation. 
     An entry s(n 1 ,n 2 ), of a diagonal sequence in FIG. 1A is determined by 
     
       
           s ( n   1 , n   2 )= s ( k ),  (1) 
       
     
     
       
           k=k ( n   1 , n   2 )=(43 ·n   1 +44 ·n   2 )(mod 1118),  (2) 
       
     
     where the sum of the two subscripted indices is computed modulo  1118  to compensate for passage of each diagonal sequence through the array more than once. 
     FIG. 1B shows the addresses ( 1118 ,  1119 , . . . ,  1169 ) of the next 52 entries, which serve as memory cells for two ECC Q-parity segments, each 26 words in length. 
     FIG. 2 illustrates a rearrangement of the original 26×43 table to show more clearly how Q-parity indices, n 1  and n 2 , can be employed for Q-parity computations. Each Q-parity sequence is now one of the 26 (horizontal) rows of 45 entries in the array shown in FIG. 2, including the P-parity checkbyte components corresponding to the data element addresses  1032 ,  1033 , . . . ,  1117 . The data element addresses  1118 , . . . ,  1143  and  1144 , . . . ,  1169  will hold the components for the Q-parity checkbytes Q 0  and Q 1 . 
     The ECC Q-parity check involves powers α n  (n=0, 1, . . . , 7) of an eight-bit primitive α, that satisfies a selected primitive polynomial relation 
     
       
           p (α)=0.  (3) 
       
     
     For example, the primitive polynomial relation may be selected to be 
     
       
           p (α)=α 8 +α 4 +α 3 +α 2 +1=0,  (4) 
       
     
     in which event the “0” element, the “1” element and several powers of α become 
      0={0,0,0,0,0,0,0,0}, 
     
       
         α 0 ={0,0,0,0,0,0,0,1}(=“1”), 
       
     
     
       
         α={0,0,0,0,0,0,1,0}, 
       
     
     
       
         α 2 ={0,0,0,0,0,1,0,0}, 
       
     
     
       
         α 3 ={0,0,0,0,1,0,0,0}, 
       
     
     
       
         α 4 ={0,0,0,1,0,0,0,0}, 
       
     
     
       
         α 5 ={0,0,1,0,0,0,0,0}, 
       
     
     
       
         α 6 ={0,1,0,0,0,0,0,0}, 
       
     
     
       
         α 7 ={1,0,0,0,0,0,0,0}, 
       
     
     
       
         α 8 ={0,0,0,0,1,1,1,0}=α 4 +α 3 +α 2 +1, 
       
     
     
       
         α 9 ={0,0,1,1,1,0,1,0}=α·α 8 =α 5 +α 4 +α 3 +α, 
       
     
     
       
         α 25 ={0,0,0,0,0,0,1,1}, 
       
     
     
       
         α 230 ={1,1,1,1,0,1,0,0}, 
       
     
     
       
         α 231 ={1,1,1,1,0,1,0,1}, 
       
     
     
       
         α 230 ={1,1,1,1,0,1,1,1}, 
       
     
     
       
         α 255 =α 0 ={0,0,0,0,0,0,0,1}=“1”,  (5) 
       
     
     where the particular powers α h  (h=1, 230, 231, 232) will be needed in the following development. The remaining powers α h  (10≦h≦254) are generated using the particular primitive polynomial relation (4). Changing the choice of primitive polynomial will cause a corresponding change in definition of most of the powers of α. 
     The particular checkbytes Q 0  and Q 1  are formed as follows. Two syndrome variables s 0  and s 1  are defined generally by                s0        [   n1   ]       =       ∑     n2   =   0       M   -   1            1   ·     s        (       (         (     M   +   1     )     ·   n2     +     M   ·   n1       )          (     mod                   M   ·   N       )       )                   (   6   )                 s1        [   n1   ]       =       ∑     n2   =   0       M   -   1              α     M   -   1   -   n2       ·     s        (       (         (     M   +   1     )     ·   n2     +     M   ·   n1       )          (       mod                 M     -   N     )       )                   (   7   )                                
     for n 1 =0, 1, . . . , N−1, where the choices M=43 and N=26 correspond to a particular choice for Q-parity error correction. Two check bytes, Q 0  and Q 1 , are added for every code word to detect up to two errors per code word and to allow correction of up to one error per code word. 
     The check bytes Q 0  and Q 1  satisfy the error check relations 
     
       
           Q   1 [ n   1 ]+ Q   0 [ n   1 ]+ s   0 [ n   1 ]=0,  (8) 
       
     
     
       
           Q   1 [ n   1 ]+α Q   0 [ n   1 ]+α 2   s   1 [ n   1 ]=0.  (9) 
       
     
     One verifies from the relations (5), (8) and (9) that 
     
       
           Q   1 [ n   1 ]= Q   0 [ n   1 ]+ s   0 [ n   1 ],  (10) 
       
     
     
       
         (1+α)· Q   0 [ n   1 ]= s   0 [ n   1 ]+α 2   ·s   1 [ n   1 ]  (11) 
       
     
     
       
           Q   0 [ n   1 ]=(1+α) −1   {s   0 [ n   1 ]+α 2   ·s   1 [ n   1 ]}=α −25   {s   0 [ n   1 ]+α −25+2   ·s   1 [ n   1 ]} 
       
     
     
       
         =α 255−25   ·s   0 [ n   1 ]+α 255−23   ·s   1 [ n   1 ]=α 230   ·s   0 [ n   1 ]+α 232   ·s   1 [ n   1 ],  (12) 
       
     
     
       
           Q   1 [ n   1 ]=α 231   ·s   0 [ n   1 ]+α 232   ·s   1 [ n   1 ].  (13) 
       
     
     Each data element received by an ECC-Q-parity processor is a 16-bit array or word, consisting of a “high end” byte and a “low end” byte that are associated with each other. The procedure shown in FIGS. 3 or  4  will also work if each data element is an 8-bit array or byte. As a word (two bytes) of data arrives, the word is received simultaneously by a syndrome- 0  processor unit and by a syndrome- 1  processor unit. These processor units produce a contribution to the Q-parity syndromes s 0  and s 1  defined in relations (6) and (7), for later computation of the Q-parity checkbytes Q 0  and Q 1 . The contributions of this received word to the syndromes s 0  and s 1  are added to the partial sums for s 0  and s 1  already in memory, and the new partial sums are returned to memory. This continues until each data element in the 26×43 array has been received and its contributions to the sums s 0  and s 1  have been computed and added to the partial sums for s 0  and s 1 . Preferably, each row of entries in the 26×43 array in FIG. 2 is read as a unit so that the contributions from each row to the checkbytes Q 0  and Q 1  are computed as a unit. 
     The invention provides an abbreviated procedure for loading and processing ECC checkbyte entries for error control. The abbreviated procedure may be expressed as follows. 
     eccq_index_s: starting index 
     1.1 reset eccq_index_s to 0 
     1.2 when 0≦n 1 ≦24, n 2 =42: 
     eccq_index_s=eccq_index_s+43 
     eccq_index: address index 
     2.1 n 2 =1: 
     eccq_index=eccq_index_s+44: 
     2.2 2≦n 2 ≦42 and eccq_index+44≦1118: 
     eccq_index=eccq_index+44 
     2.3 2≦n 2 ≦42 and eccq_index+44≧1118: 
     eccq_index=eccq_index+44−1118 
     3 When n 1 =0, use s 00  and s 10  to store the syndrome 
     4 When n 1 =n (≧1), use s 0 n and s 1 n to store the syndrome 
     5 Use burst mode to write checkbyte back to memory 
     6 Set n 2 =43 and n 1 =0, 1, . . . , 25; write Q 0  to memory 
     7 Set n 2 =44 and n 1 =0, 1, . . . , 25; write Q 1  to memory 
     FIG. 3 is a flow chart illustrating one embodiment of the invention. It is assumed here that the “bare” data entries s(k) (k=0, 1, 2, . . . , 1031) are to be processed by being written to, or read from, the first 1032 entries of the 26×43 array as shown in FIG. 1, that first and second P-parity syndrome sequences correspond to the next two rows of 43 entries s(k) (k=1032, 1033, . . . , 1074 and k=1075, 1076, . . . , 1117), that the 44th column (FIG. 2) corresponds to the checkbyte Q 0  with entries s(k) (k=1118, 1119, . . . , 1143), and that the 45th column (FIG. 2) corresponds to the checkbyte Q 1  with entries s(k) (k=1144, 1145, . . . , 1169). The entire sequence of words s(k) (k=0, 1, 2, . . . , 1169), each consisting of an “upper” byte s(k) U  and a “lower” byte s(k) L , is to be read from the  1118  addresses of the 26×43 array shown in FIG. 1A, processed to determine the checkbyte entries for Q 0  and Q 1 , and these checkbyte entries are to be written to 52 addresses in a 2×26 array, as shown in FIG.  1 B. 
     In step  31  of FIG. 3, a first counting index n 1  is initialized (n 1 =0). In step  33 , two sequences, s 0 [n 1 ] and s 1 [n 1 ], of 16-bit arrays are initialized for a second counting index n 2  (s 0 [n 1 ]=0 and s 1 [n 1 ]=0) and a selected 8-bit variable α is provided. In step  35 , the second counting index n 2  is initialized (n 2 =0). In step  37 , a composite counting index k=k(n 1 ,n 2 ), defined in ( 2 ), is optionally computed. 
     In steps  41 - 43 , a sequence of data entries s(k) is read in and processed. In step  41 , the system reads a data element or word s(k), a 16-bit variable including a low end byte and a high end byte. In step  43 , the system calculates s 0 [n 1 ]=1·s 0 [n 1 ]+s(k) and s 1 [n 1 ]=α·s 1 [n 1 ]+s(k) for high end and low end bytes, where the 8-bit arrays designated as 1 and α are set forth in the relation (5). 
     In step  45 , the index n 2  is incremented (n 2 →n 2 +1). In step  47  the system determines whether n 2 ≧43? If the answer to the question in step  47  is “no,” the system returns to step  37  and repeats the procedure in steps  37 ,  41 ,  43 ,  45  and  47  at least once, using the now-incremented value for the second index n 2 . 
     If the answer to the question in step  47  is “yes,” the system re-initializes the second index (n 2 =0) and increments the first index n 1  in step  49  (n 1 →n 1 +1). In step  51  the system determines whether n 1 ≧26? If the answer to the question in step  51  is “no,” the system returns to step  33 , using the now-incremented first index n 1 , re-initializes the quantities s 0 [n 1 ], s 1 [n 1 ] and n 2  (all=0) for the new value of n 1 , and repeats the procedure in steps  33 ,  35 ,  37 ,  41 ,  43 ,  45 ,  47 ,  49  and  51  at least once, using the now-incremented value for the first index n 1 . 
     If the answer to the question in step  51  is “yes,” the system initializes a third counting index n 3  (n 3 =0) and loads or otherwise provides selected powers α h  of the α variable (e.g., α 230 , α 231 , α 232 ), at step  53 . The system provides s 0 [n 3 ] and s 1 [n 3 ] at step  55 . At step  57 , the system computes Q 0 [n 3 ]=α 230 ·s 0 [n 3 ]+α 232 ·s 1 [n 3 ] and stores Q 0 [n 3 ] in address  1118 +n 3 . At step  59 , the system computes Q 1 [n 3 ]=α 231 ·s 0 [n 3 ]+α 232 ·s 1 [n 3 ], and stores Q 1 [n 3 ] in address  1144 +n 3 . The index n 3  is incremented at step  61  (n 3 →n 3 +1). At step  63 , the system determines whether n 3 ≧26? If the answer to the question in step  63  is “no,” the system returns to step  55  at least once and repeats the steps  55 ,  57 ,  59 ,  61  and  63  at least once. If the answer to the question in step  63  is “yes,” the procedure optionally stops, at step  65 . The steps  55 ,  57 ,  59 ,  61  and  63  can be performed together in at most two clock cycles. The two sequences {Q 0 [n 3 ]} and {Q 1 [n 3 ]} serve as Q-parity checkbyte components for the data element sequence. 
     Although this method is arranged to scan a 26×43 (or 26×45) rectangular array of numbers in a diagonally oriented manner, the method can be extended to diagonally scan an M×N rectangular array of numbers (M≦N−1) in a similar manner. In FIG. 3, the choices N=26, M=43 and R=M·N=1118 are made. 
     FIG. 4 illustrates this extension of the method, with steps  71 ,  73 ,  75 ,  77 ,  81 ,  83 ,  85 ,  87 ,  89 ,  91 ,  93 ,  95 ,  97 ,  99 ,  101 ,  103  and  105  being analogous to the corresponding respective steps  31 ,  33 ,  35 ,  37 ,  41 ,  43 ,  45 ,  47 ,  49 ,  51 ,  53 ,  55 ,  57 ,  59 ,  61 ,  63  and  65 . In step  77 , the counting index k defined in the relation (2) is replaced by the index 
     
       
           k ′( n   1 , n   2 )=( M·n   1 +( M+ 1)· n   2 )(mod  M·N );  (14) 
       
     
     in step  8 , the question becomes “Is n2≧M?”; in step  91 , the question becomes “Is n1≧N?”; and in step  103 , the question becomes “Is n3≧N?” In steps  97  and  99 , the addresses for storage become M·N+n 3  and M·(N+1)+n 3 , respectively. In most other respects, the flow chart shown in FIG. 3 remains the same. Further, the initial address number,  0000 , may be replaced by any other reasonable address number, with suitable changes in other addresses being made to account for the changed initial address.