[Design View / Design Solution]
Improve Integrated SRAM Reliability With Hamming Error-Correction Code
Several techniques can be used to efficiently implement a Hamming coder for single-bit error correction and double-bit error detection.
The computational complexity of parity bit computation can be reduced by using the Blackfin general-purpose LFSR instructions. For example, using the BXOR instruction, the parity bits of the Hamming coder can be efficiently computed as discussed below.
Given the 32-bit data and the 32-bit mask, the BXOR instruction computes the XOR of all bits defined by the mask in the 32-bit data. For example, if the 32-bit data is stored in an accumulator register A = 0xABCDEFAB, and 32-bit mask value is stored in a register R = 0x33333333, then BXOR(A, R) outputs the XOR of all 2-LSB bits in nibbles of register A. That’s because the mask is defined as 1s in 2-LSB bits of all eight nibbles.
COMPUTATION OF COLUMN PARITY BITS Because the Blackfin processor is 32 bits, the column parity bits can be efficiently computed in very few steps:
• Pack the bytes into 32-bit words. (It’s free because we can load 4 bytes or 32 bits at a time.)
• XOR all 64 32-bit words (i.e., 256 bytes) and say register R contains the result.
• Then shrink the result from 32-bit to 8-bit column parity as S = R>>16, R = R ^ S, S = R>>8, R = R ^ S, R = R & 0xff. Now, R contains the column wise XORed bits of 256 bytes.
• Then, compute the individual parity bits using the register R content.
• Using the masks and BXOR instruction, compute the individual parity bits and the masks used for computing the parity bits yP0, yP1, yP2, yP3, yP4, yP5, which are 0x55, 0xaa, 0x33, 0xcc, 0x0f, 0xf0.
• Compute the parity dP6 using the mask 0xff.
All of the above steps consume less than 100 cycles on the Blackfin processor.
COMPUTATION OF ROW PARITY BITS The 32-bit-word method used to compute column parity bits can’t be applied to row-parity-bit computation. Each data byte independently contributes toward the parity information, so we must handle each byte separately. For this, the parity of each byte is computed using the mask value 0xff and the BXOR instruction (see “Sample Code Using BXOR Instruction”).
The computed 256 parity bits of 256 bytes are organized into eight 32-bit words. Now, to compute the column parity on eight 32-bit words using the masks, first compute the 10 parity bits (xP0 to xP9). The values of the 10 masks are 0x55555555, 0xaaaaaaaa, 0x33333333, 0xcccccccc, 0x0f0f0f0f, 0xf0f0f0f0, 0x00ff00ff, 0xff00ff00, 0x0000ffff, and 0xffff0000. The reset of six parity bits is computed by shrinking the 256-bit parity data to a byte parity data using the mask 0xffffffff.
Once we have 8-bit parity, compute the last six row parity bits (xP10 to xP15) in the same way that the six column parity bits (yP0 to yP5) were computed using the mask values 0x55, 0xaa, 0x33, 0xcc, 0x0f, and 0xf0. All of the steps present in the xP0 to xP15 row-parity-bit computation consume about 850 cycles on a Blackfin processor.
Finally, the parity of parity bit dP7 is computed by XORing all parity bits yP0 to yP5 and xP0 to xP15. If all 22 parity bits are present in a 32-bit register starting from LSB side, compute the parity bit dP7 with the BXOR instruction using the mask value 0x3fffff.
With the techniques described above, the parity-bit computation of the Hamming coder (2072, 2048) can be implemented with less than 0.5 cycles per bit.
By using the techniques suggested in this article, one can efficiently implement a Hamming (2072, 2048) coder on a Blackfin processor for single-bit error-correction applications at less than 0.5 cycles per bit. The memory used in this implementation is approximately 640 bytes.
REFERENCES:
Analog Devices Inc., “ADSPBF53x/ 56x Blackfin Processor Programming Reference,” Revision 1.0, June 2005.
Neal Mielke, Todd Marquart, Ning Wu, Jeff Kessenich, Hanmant Belgal, Eric Schares, Falgun Trivedi, Evan Goodness, and Leland R. Nevill, “Bit Error Rate in NAND Flash Memories,” IEEE CFP08, 46th AIRPS, Phoenix, Ariz., 2008.
Reprints
