Browse Prior Art Database

Shift Register Implementation of the SEC DED Codes

IP.com Disclosure Number: IPCOM000075626D
Original Publication Date: 1971-Oct-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 53K

Publishing Venue

IBM

Related People

Patel, AM: AUTHOR

Abstract

The modular SEC-DED odd-weight-column codes have a parity check matrix H, which is divided into r+1 partitions H(o),H(1),H(2),...H(3-1), I such that any partition H(i+1) is constructed from the partition H(i) by shifting the rows of H(i) cyclically one unit downwards, and I is the r x r identity matrix. Each partition H(i) contains b columns. (Image Omitted) This modular structure is very suitable for shift register implementation of the code, which results in an economical use of hardware and is an effective tradeoff between hardware and decoding time. Let B(o), B(1), B(2), ... B(r-1), and C be the byte vectors as partitions of the codeword corresponding to the r+1 partitions, respectively, of the modular parity check matrix. The bytes B(i) are b-digit information vectors and C is a vector of r check digits.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 3

Shift Register Implementation of the SEC DED Codes

The modular SEC-DED odd-weight-column codes have a parity check matrix H, which is divided into r+1 partitions H(o),H(1),H(2),...H(3-1), I such that any partition H(i+1) is constructed from the partition H(i) by shifting the rows of H(i) cyclically one unit downwards, and I is the r x r identity matrix. Each partition H(i) contains b columns.

(Image Omitted)

This modular structure is very suitable for shift register implementation of the code, which results in an economical use of hardware and is an effective tradeoff between hardware and decoding time. Let B(o), B(1), B(2), ... B(r-1), and C be the byte vectors as partitions of the codeword corresponding to the r+1 partitions, respectively, of the modular parity check matrix.

The bytes B(i) are b-digit information vectors and C is a vector of r check digits. The parity checking rules can be written as the following modulo-two-matrix-equation:
H(o)B(o) + H(1) B(1) + H(2) B(2) + ... + H(r-1)B(r-1) = C (1).

For shift register implementation, the parity check equations can be written in terms of the companion matrix of a polynomial. Let T be the companion matrix of the polynomial X/r/ + 1. Then T is given by:

(Image Omitted)

where i(r-1) is a (r-1)x(r-1) identity matrix. It can be shown that:

TH(i) = H(i+1) where H(i+1) and H(i) are partitions of the modular parity check matrix of r parity checking rules. It can also be shown that: H(i+1) = T(i)H(1) where T/i/ denotes the i/th/ power of matrix T. Accordingly, the parity checking equation (1) can be rewritten as follows: H(o)B(o) + TH(o)B(1) + ... T/i/H(o)B(i) +
... + T/r-1/ H(o)B(r-1) = C (2). Equation (2) can be implemented by a simple r-channel shift register.

The vector C of r check digits is computed from the information vectors B(o),B(1),...B(r-1) according to the parity checking equation (2). This is accomplished by a r-channel shift register (SR) with an end-around feedback 10, as shown in Fig. 1. Shifting operation corresponds to multiplying by the companion matrix T. The entering b-digit information vector B(i) is premultiplied by the matrix H(o) using a network of Exclusive OR gates 12. The resulting r- digit vector H(o)B(i) is entered into the shift register (SR). Initially, the SR contains all zeroes. The information bytes B(r-1), B(r-2),...B(3), B(2),B(1) are successively entered, in that order, as the contents of the SR is shifted. At the end of r shifts, SR contains the vector H(o)B(o) + TH(o)B(1) + ... T/r-1/H(o) B(r- 1). which is the vector C of r check digits.

In decoding, let B(-o), B(-1), B(-2), ... B(-r-1) and C denote the received vectors. The syndrome is given by the equation:

1

Page 2 of 3

S = H(o)B(-0)+ TH(o) B(-1)+ T/2/ H(o) B(-2) ...

T/r-1 H(o) B(-r-1) + C (3). The syndrome can be generated in the same manner...