Instruction for Bi-Residue coder/decoder

Introduction:

For Residue code, one can refer to the course webpages. A separate code with two residue checks is called bi-residue code. We study [N, |N|A1, |N|A2]. A1,A2 are called the check bases. We can choose A1=2c-1,A2=2d-1, for positive integers c and d.

Theorem: Consider a biresidue code with k-bit data, that is, N \in 2k-1, A1=2c-1,A2=2d-1 for c!=d. The code can correct any single error in the adder or any error in one of the checker if and only if k=LCM(c,d).

The theorem tells us in order to single-bit error correction, the bits of encoder/decoder and two check bases has the least common multiple relations. For example, if the input data bit width is 24, we can choose (c=8,d=6) or (c=12,d=8).  If we want the data bit width is 32, we have to choose (c=32, d=2 or 4 or ...). Obviously, this is not a good choose.

Syndrome and error correction:

The syndrome of a 3-turple (x,y,z) is given by S(x,y,z)=(s1,s2)=(|x-y|A1,|x-z|A2). It is assumed that the three components of the code are processed in separate units, called the adder, check_1, and check_2, respectively, and therefore at most one of the components of the result will be erroneous at any given time. We have the following rules:

• s1=0, s2=0: no error.
• s1!=0, s2!=0: error in the adder.
• s1!=0, s2=0: error in check_1.
• s1=0, s2!=0: error in check_2.

The following table is a detailed example of syndromes to detect and correct the error for the adder. Here, k=6, c=2, d=3. That is, A1=3, A2=7. Input data is in the range of (0-63).

 error bit-i 0-->1 error 1-->0 error 0 (1,1) (2,6) 1 (2,2) (1,5) 2 (1,4) (2,3) 3 (2,1) (1,6) 4 (1,2) (2,5) 5 (2,4) (1,3)

How the Bi-Residue error correction program works

step 1:  Input the data word (DEC), with the corresponding encoded bit width. Also input the bit width of the two check bases. If the LCM requirement between the three inputs are not meet, a pop-up window indicating errors will be shown.

step 2:  Click the "encode" button, the encoded bit stream are turple (x,y,z) where x is the data-bit, y and z are check-bits.  At the same time, the fault-free bit will be appear at the received word dialogs.

step 3:  The user can change at most one bit error in received word. If more than one errors are injected or the length of received words is longer than the original encoded one, a pop-up window indicating errors will be appear.

step 4:  Click the "decode" button, the decoded data will be appear at the decoded word part. At the same time, the error-detected indicator and error-corrected indicator will indicate whether the error is detected/corrected.

step 5: (optional) If the user clicks the "Error info", a pop-up window will be show up for detailed error information and related syndrome.

กก