NHE2483 Digital Systems Integration

Error Coding
• The process of adding additional bits to the data
(codeword), before transmitting/storing so that if the
received/retrieved codeword has been corrupted (errors),
the corruption can be identified and corrected.

Transmitter Bit errors (noise) Receiver

Digital Digital
Source Encoder Decoder Received
Channel Identify
Data data
errors
Wire, & Correct
Optical fibre
etc

Dr. P.J. Mather

NHE2483 Digital Systems Integration

Digital Error Coding Systems

Multi-bit and Single Parity

Hamming coding system

Error (parallel coding generally 7/4 code.
coding 4 data bit + 3 error/Parity bits.
systems Codeword is 7 bits

Linear Sequential System

(serial coding generally 4 data bit 3 error
parity bits.

Multiple error bit correction schemes

Not covered in this module –
Reed-Soloman etc
2
Dr. P.J. Mather
NHE2483 Digital Systems Integration

Multi-bit Codes
2 bit Coding Data Codeword transmitted
0 00
1 11
• Errors can be detected - received code 01 or 10 indicates an
error has occurred.
• Odd number of 1’s
• but there is no way to correct the error.
• If 01 received the original signal could have been
00 or 11.
• Double the memory requirements compared to the basic
data.
• Transmission rate is 1/2 = 50% - (1 data bit in 2 transmitted
bits)
3
Dr. P.J. Mather
NHE2483 Digital Systems Integration

Multi-bit Codes
3-Bit Coding Data Codeword transmitted
0 000
1 111
• Errors can be detected and also corrected.
• Received 100 is closer to 000 (1 bit error) than to 111
• Three times as much memory is required, thus makes the
coding costly.
• The data transmission rate is only a 1/3 (1 data bit in 3
transmitted bits)
• A coding system where the list of codewords and all possible 1
bit error codes use all the possible codes 23 available, is termed
PERFECT. Data Valid 1 bit error code 1 bit error code 1 bit error code
Codewords 1st bit in error 2nd bit in error 3rd bit in error
0 000 100 010 001
1 111 011 101 110
4
Dr. P.J. Mather
NHE2483 Digital Systems Integration

Single Parity – Odd or Even Codes

• The method of adding an extra bit (1 or 0) to make the
codeword contain either an ODD or EVEN number of 1’s.

• This enables errors, during transmission, to be detected – if a

codeword has the opposite parity than expected.
• Errors cannot be corrected.
• 000 is transmitted, 010 is received,
The original code could have been 110 or 000 or 011
• 111 is transmitted, 010 is received,
The original code could have been 011 or 101 or 110

• Same for all 8 (23 where 3 is the number of bits) received

codeword. 5
Dr. P.J. Mather
NHE2483 Digital Systems Integration

Single Parity – Odd or Even Codes (cont.)

• Only requires 1 extra bit.
• Max extra memory requirements 3/2 = 50%, this decreases as
the number of data bits increase (single parity bit).
• 4 Data bits + even/odd parity 1 bit = 5 bit codeword.
• Memory requirements increase to 5/4 (25% increase)and
transmission rate is 4/5 compared to sending the raw
data.
Data Codeword
Parity

• 7 Data bits + even/odd parity 1 bit = 8 bit codeword.

• Memory requirements increase by 8/7 and transmission
rate is 7/8 compared to sending the raw data.

6
Dr. P.J. Mather
NHE2483 Digital Systems Integration

Hamming Coding System Data

Data Code-word
Code-word
00 0000 00 0000 00 00 0 0 0
• 7-bit code-words (4 data bits, 3 error bits) 0 0 0 1 0000 00 11 0 1 1
0001
• All the code-words differ in at least 3 00 0011 00 0000 11 00 1 1 1
places, so the code can correct 1-bit 00 1100 00 0011 00 00 1 0 1
errors. 11 0000 00 1100 00 00 1 1 0
11 1100 00 1111 00 00 0 1 1
• 16 valid code-words (2 ) 4
11 0011 00 1100 11 00 0 0 1
• Each valid code-word has 7 11 0000 11 1100 00 11 1 0 1
associated 1 bit error codes. 00 1111 00 0011 11 00 0 1 0
• Thus 16*8 = 128 code-words 00 1100 11 0011 00 11 1 1 0
required. 00 0011 11 0000 11 11 1 0 0
• 7 bits means 27= 128 code-words 11 1111 00 1111 11 00 1 0 0
available 11 1100 11 1111 00 11 0 0 0
• Therefore, the Hamming code is a 11 0011 11 1100 11 11 0 1 0
perfect code. 00 1111 11 0011 11 11 0 0 1
4.7 7
Dr. P. J. Mather 11 1111 11 1111 11 11 1 1 1
NHE2483 Digital Systems Integration
Developing Hamming Codes (1)
• A valid coding system can be used to correct single bit
errors if every codeword differs from all the other
codewords in at least three places:

• To compute the 7-bit code-words (c1c2 c3 c4 c5 c6 c7)

from the 4-bit input data (d1d2d3d4)

d1 d2 d3 d4 (d1  d2  d3) (d1  d3  d4) (d2  d3  d4)

c1 c 2 c 3 c4 c5 = p 1 c6 = p2 c7 = p3

8
Dr. P. J. Mather
NHE2483 Digital Systems Integration
Developing Hamming Codes (2)

c1 c2 c3 c4 c5 c6 c7 (c5 c6 c7 = three x EVEN Parity)

The following three constraints hold:

c1  c2  c3  c5 = 0
c1  c3  c4  c6 = 0
c2  c3  c4  c7 = 0
This leads to a very simple algorithm for decoding.
“parity-checks” can be used to determine whether
the codeword has been corrupted

P1 = c1  c2  c3  c5
P2 = c1  c3  c4  c6
Dr. P. J. Mather
P3 = c2  c3  c4  c7 9
NHE2483 Digital Systems Integration
Identifying Errors in Hamming Codes

1. If P1 = P2 = P3 = 0,
– c1 c2 c3 c4 c5 c6 c7 was a correct code-word and the
original data was c1 c2 c3 c4

2. If one of the P(1-3) = 1, but the other two equal to 0:

look for the data bit c which is only used in the P
which is 1 but not in the others and invert to obtain a
correct codeword.
• Note – If only one P(1-3) = 1 then only a parity bit
(c5 c6 c7 ) has been corrupted and not the data.
P1 = c1  c2  c3  c5
P2 = c1  c3  c4  c6
Dr. P. J. Mather P3 = c2  c3  c4  c7 10
NHE2483 Digital Systems Integration
Identifying Errors in Hamming Codes

3. If only one of the P(1-3) = 0, and the other two are

equal to 1: look for the c-bit that occurs in the two
“wrong” parity-bits, but not in the other, and invert it.
e.g: P1 = P2 = 1, P3 = 0.
The only c which P1 and P2 have in common but
that does not occur in P3 is c1. Therefore, invert c1 to
get the correct code-word.

4. If P1 = P2 = P3 = 1, then invert c3, as c3 is common to

all P(1-3)
P1 = c1  c2  c3  c5
P2 = c1  c3  c4  c6
Dr. P. J. Mather P3 = c2  c3  c4  c7 11
NHE2483 Digital Systems Integration
Correcting Errors in Received Codewords
P1 P2 P3 Bit in Correction Codes
Error (XOR) P1 = c1  c2  c3  c5
ca11 c2
a c3
a c44
a P2 = c1  c3  c4  c6
P3 = c2  c3  c4  c7
0 0 0 - 0 0 0 0
0 0 1 c7 0 0 0 0 a1
d1
0 1 0 c6 0 0 0 0 c1
0 1 1 c4 0 0 0 1 a2 d2
1
1 0
0 0
0 cc5 0
0 0
0 0
0 0
0
c2
5
1 0 1 a3
1 0 1 c2 0 1 0 0 d3
1 1 0 c3
1 1 0 c1 1 0 0 0 a4 d4
1 1 1
1 1 1 c3 0 0 1 0 c4
• Hardware implementation is straight forward, requiring
basic logic gates (XOR) and D-type flip-flops.
Dr. P. J. Mather 12
NHE2483 Digital Systems Integration
Examples – Correcting single bit Errors in received codewords
Example 1: If 1000101 (c1 to c7) is received, then the parity bits are
  p1 = c1  c2  c3  c5 = 1  0  0  1 = 0
p2 = c1  c3  c4  c6 = 1  0  0  0 = 1
p3 = c2  c3  c4  c7 = 0  0  0  1 = 1
• c common for p2 & p3, but does not occur in p1 is c4.
• The original transmitted code is determined by inverting c4.
• Hence the original codeword was 1001101 where the data is 1001

Example 2: If 1011101 (c1 to c7) is received, then the parity bits are
  p1 = c1  c2  c3  c5 = 1  0  1  1 = 1
p2 = c1  c3  c4  c6 = 1  1  1  0 = 1
p3 = c2  c3  c4  c7 = 0  1  1  1 = 1
• c common for p1,p2 & p3, is c3.
• The original transmitted code is determined by inverting c3.
• Hence the original codeword was 1001101 where the data is 1001
13
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Valid Hamming codes

Hamming Codeword Data Error bits Memory Correct 1

code bits bits requirement bit in
(multiple of
data bits
7/4 7 4 3 1.75 7
15/11 15 11 4 1.36 15
31/26 31 26 5 1.19 31

14
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Linear Sequential Systems – Serial

Circuit block
symbol
Z = x + D2x + D3x D Q

D-Type
FF
Dx D 2x D 3x clk
x
B
o/p B
A o/p
A
Encoder Z

Dx D 2x D 3x
x

Decoder
Z
15
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Encoder
Apply an impulse x= 1 for one clock pulse (followed by ‘0’s)
monitor the output. Dx Dx Dx2 3
x
X Dx Dx 2
Dx 3
Z
1 0 0 0 1 Z
0 1 0 0 0
0 0 1 0 1 1st bit in 1st bit out
0 0 0 1 1
0 0 0 0
0000000 = 0000000
0
0000001 = 0001101
0 0 0 0 0 0000010 = 0011010
0 0 0 0 0
0000100 = 0110100
0001000 = 1101000

Note If x is all ‘0’s then the output is all ‘0’s 16 Valid Codes
(4 bits of data)
16
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Determining all 16 Valid Codes (4 data bits) 0000001 = 0001101

0000010 = 0011010
0000000 = 0000000
0000100 = 0110100
0000001 = 0001101
0001000 = 1101000
0000010 = 0011010
0000011 0010111
= Data to be TX = 0000011
0000100 = 0110100 individual 0001101
0000101 = impulse responses 0011010 XOR
0000110 = code-word is 0010111
0001000 = 1101000
0001001 =
Data to be TX = 0001111
0001010 =
0001011 = 0001101
individual 0011010 XOR
0001100 =
impulse responses 0110100
0001101 =
0001110 = 1101000
0001111 1001011
= code-word is 1001011
17
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Decoding
x
Construct noise Look-Up
Dx Dx 2
Dx
3

table using the impulse

response table
Z
Noise Look-Up Table
Z=x+Dx+Dx 2 3

Impulse response 0000001 = 0011101

x Dx D 2x D 3x Z 0000010 = 0111010
1 0 0 0 1 0000100 = 1110100
0 1 0 0 0 0001000 = 1101000
1 0 1 0 0 0010000 = 1010000
1 1 0 1 0
0100000 = 0100000
1 1 1 0 0
0 1 1 1
1000000 = 1000000
0
0 0 1 1 0 Note: 0000000 = 0000000
18
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Decoding Operation – Valid Uncorrupted Codeword Received

No noise
0010111 0010111
0011 x’
Transmission Receiver
TX RX 0011

0010111 impulse response from Look-up table

0011101
0111010
1110100 XOR
1010000
0000011 
If the final error bits are 000 then the data has not been
corrupted. Hence the data bits are the same as the original.
Dr. P. J. Mather
NHE2483 Digital Systems Integration

Decoding Operation – 1 Bit error Codeword Received

0010111 0010101 x’
0011 Transmission Receiver
TX RX 0011
noise
0010101 impulse response from Look-up table
0000001 = 0011101


0000010 = 0111010
0011101 0111001 0000100 = 1110100
0000000 XOR
0111010 0001000 = 1101000
0010000 = 1010000
1110100 0000011 0100000 = 0100000
1010000
0111001
X 1000000 = 1000000

If the final error bits are not equal to 000 then the data has
been corrupted. Hence to determine the correct (original) data
the final output needs to be XOR’ed with the code in the LUT
with the same error code.
20
Dr. P. J. Mather
NHE2483 Digital Systems Integration

LSS System Diagram – Including Error Correction

ENCODER DECODER

Input txlss(1:3) rxlss(3:1) sipo(6:0)

Transmission
data
  1 2 3 Line 3 2 1 6 5 4 3 2 1 0

sin

Error code assessor/

check corrector

6 5 4 3 2 1 0 3 2 1 0
control(6:0)
Induced
Error Bit

res dout(3:0)
Output Data
4.21
Dr. P. J. Mather