[D₁ D₂ D₃ P₁ P₂ P₃]

At the receiver we must multiply the received codewords with the H^T in order to achieve the error syndromes. By definition H = [PI_m], therefore H^T is:

However the problem is, we are not transmitting our pattern as in above, rather in the following order:

therefore according to the changes in the bit pattern’s position we must apply to the [G] and [H^T] as follow:

and

therefore according to the new order of bit transmission we suggest the following circuit to receive the 3 data bits and to produce the codeword [P₁ P₂ D₁ P₃ D₂ D₃].

Now we transmit our codewords on the channel, however the channel may apply some errors on the codewords. We model this effect by using the circuit labelled A. If all switches are on the 0 then we have no errors. Since each bit is EORed by 0 which permits the bit to receive with no error. However if we would like to apply an error to a specific bit all we have to do is to switch the appropriate bit to 1 which causes an arithmetic EOR addition of 1 which makes the output NOTed that models an error on that bit.

Now we must set up a circuitry to produce the syndromes for error checking. Before that we show how these syndromes look like:

where [R] is the received codeword :

where [P’₁ P’₂ D’₁ P’₃ D’₂ D’₃] is the received code word. Now by the application of definitions of our parities, we have:

To design a circuit which generates these syndromes, we suggest the usage of an integrated circuit of GAL22V10 which contains six two input EORs and one three input EOR. It’s pin configuration is shown in the circuit diagram B.

By using this IC the necessary syndromes are obtained according to the combination stated, shown in the circuit diagrams C and D.

Now if we assume that all the received codeword is correct therefore D_i = D_i‘ and P_i = P_i‘ and the followings are resulted:

since D_i (+) D_i according to the law of EOR is zero.

If the following errors occur we will have:

Now if we employ a 3 to 8 decoder, any of the combination of these syndromes is assigned to one out put. This has been shown in the circuit diagram C.

We have so far considered single error conditions only. By the usage of these syndromes and the received codewords and EORs gates we may achieve forward error correction as specified in the following design. Here if we assume that one of the arrival bits is error, this will make the appropriate output bit of the 3 to 8 high therefore if we drive the appropriate outputs with the actual bits as shown in the following figure, we will have either one of the possible states. The actual bit might be correct therefore the appropriate bit from the 3 to 8 is low therefore by EORing these two bits we may have the actual bit at the output. If the actual bit is error then that bit will be high which makes the EORing of these two bits reversing of the actual bit which makes it correct again. This effect has been illustrated in the circuit diagram E.

We have so far assumed to have only one error, however it is possible to have more, up to six errors. We are not able to detect and correct more than 2 errors according to the Hamming distance. In order to achieve more error bit detection and correction we must increase the number of parity bits. But the parity bits must be fixed.

We are expecting to have up to two errors and according to the 2t + 1 and t +1 law we are able to correct one bit error or to detect two bit errors. We have designed our system so that it corrects one bit error, now we enter a discussion to enhance the designed system. There are 3 data bits and 3 parity bits, which are generated from the data bits. Therefore our codeword can have only 8 different patterns.

The following table shows these 8 different patterns, along with the possibilities of having error in any of our 6 bits. Note that P_i^E, D_i^E, state the error bit received.

We write different possibilities for the first syndrome (S₁) according to the 8 different values of the data bits as follow:

Because of the similarities between the way that syndromes are generated from the arrival bits, we can derive a similar table for S₂ and S₃ as well.

The only reference point by which we are ensured that we have received all the bits correct is the state S₁ = S₂ = S₃ = 0. It can be shown that up to two errors won’t effect this criteria, however more than two errors may affect this criteria. That is:

For zero error the correct reception suits this condition fine, however there is no way to have one or two errors which result S₁ = S₂ = S₃ = 0.

Now we focus our attention to two-bit-error and according to the structure of the syndromes we see the effects as follow:

or in the terms of syndromes we conclude that :

Therefore, if we assume that we have two errors, we are not able to identify which set of two or three errors are responsible.

We shall note that the law of Hamming distance states that with the Hamming distance of 3 we are able to correct one error bit OR detect two error bits, that is, simultaneous operations are not possible. In the following we show, that we end with similar syndrome structure for both operations witch is not distinguishable.

Now we want to enhance our system in order to handle two errors detection. Again we assume that we have either no error or one error or two errors. We use several methods to check this out:

We have so far designed a system that detects and correct one error bit therefore if we reproduce the syndromes from the corrected bits (from the output of the EORs) and we feed them again through another 3 to 8 decoder.

If we have two error bits therefore one of the first outputs of the first 3 to 8 decoder’s output except for the first and the last ones, sets high, this not only does not reduces our errors but also according to the last table, it will increase our errors. For example if we have P^E₁, P₂, D^E₁, P₃, D₂, P₃, this will produce a syndromes of S₁, S₂, S₃ = 0 0 1. This will automatically generate the output from the first 3 to 8 decoder for P^E₃. Therefore we will have three errors that will affect our reference condition of S₁, S₂, S₃ = 0 0 0. This occurs while we have two errors and according to our pre-setting one error correction circuitry we make the third error to the code word and that makes a total of three errors for the next 3 to 8 decoder.

We introduce all the bit orders of three error bits that generate S₁, S₂, S₃ = 0 0 0 as follow:

D^E₁, D^E₂, D^E₃, P₁, P₂, P₃ D₁, D^E₂, D₃, P₁, P^E₂, P^E₃

D^E₁, D₂, D₃, P^E₁, P₂, P^E₃ D₁, D₂, D^E₃, P^E₁, P^E₂, P₃

and by a careful observation we see that all the 7 conditions will generate the state of S₁, S₂, S₃ = 0 0 0 at the second syndrome system.

Therefore again our reference condition is under the question while if we have either one error bit or two error bits we will achieve the first decoder’s output at the second decoder which is ambiguous.

The second approach is using the dual bits stated in the last table.

Now consider if we have received the bits whether with no error or one or two. If it has no zero, there is no problem we have the first bit of the decoder high. However if we have one or two error bits we employ the dual bits, so that when we have a high on one of the first decoder’s output we change the appropriate dual bit as well and the final bits are fed through the second decoder. The results are stated in the following table:

We observe that due to the dualities between the one error state and two errors state we achieve the same results therefore, we are not able to distinguish between one error state and two errors state! However certain states are detectable, for example all the states that produce the syndromes of: S₁, S₂, S₃ = 1 1 1, which are: D^E₂, P^E₁ and D^E₁, P^E₂ and D^E₃, P^E₃.

Therefore we must change our policy so that any case of two error bits can be detectable, since as observed except for the three above special two error bits, others can not be distinguished.

This situation occurs because of the effect of touching spheres in Hamming distance space structure. We propose the following method to solve this problem:

We add another parity bit to the sending codeword structure as stated as follow:

P₁ = D₁ (+) D₃

P₂ = D₂ (+) D₃

P₃ = D₁ (+) D₂

P₄ = D₁ (+) D₂ (+) D₃

therefore the codeword structure is changed as following:

C = [D₁ D₂ D₃ P₁ P₂ P₃ P₄]

and the G matrix will have an extra column as follow :

and the H^T matrix will become:

therefore there will be an extra one syndrome as stated below :

S₁ = P’₁ (+) D’₁ (+) D’₃

S₂ = P’₂ (+) D’₂ (+) D’₃

S₃ = D’₁ (+) P’₃ (+) D’₂

S₄ = D’₁ (+) D’₂ (+) D’₃ (+) P’₄

now we analyse the state of having one error:

now we analyse the state of having two errors:

therefore we can distinguish between one bit error and two bit error states. Now we write them in terms of the syndromes:

as you can see there is no over lap between the one error bit patterns and two error bit patterns, therefore, we are now able to operate both.

We can perform the operation by using a single 4 to 16 decoder, therefore, the first output is dedicated to the error free reception signal and the 2^nd, 3^rd, 5^th, 8^th, 9^th, 12^th, and 4^th outputs are related to the one error reception signals and the 15^th pin is dedicated to more than 3 bits error reception and the rest bits are for two bits error detection.

Another way to determine the one error bit case is by a careful look at the syndromes. We find out, that, in the one error bit condition we have 3 bits equal in level and one bit in another level. Either there are three one and a zero or three zero and a one, therefore by using a very simple circuit we are able to distinguish between them.

The construction of a decoder is not that sophisticated. For example, if the inverted signals of the three inputs are accessible, then by using 8 three-input-ANDs we are able to build a 3 to 8 decoder according to the following table:

and by using two 3 to 8 decoder we are able to build a 4 to 16 decoder.