# Hamming Code - amirrezatav/Verilog_VHDL Wiki

Hamming code is a set of error-correction codes that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver. It is technique developed by R.W. Hamming for error correction.

## Redundant bits

Redundant bits are extra binary bits that are generated and added to the information-carrying bits of data transfer to ensure that no bits were lost during the data transfer.

## Parity bits

A parity bit is a bit appended to a data of binary bits to ensure that the total number of 1’s in the data is even or odd. Parity bits are used for error detection. There are two types of parity bits:

### 1. Even parity bit:

In the case of even parity, for a given set of bits, the number of 1’s are counted. If that count is odd, the parity bit value is set to 1, making the total count of occurrences of 1’s an even number. If the total number of 1’s in a given set of bits is already even, the parity bit’s value is 0.

### 2. Odd Parity bit :

In the case of odd parity, for a given set of bits, the number of 1’s are counted. If that count is even, the parity bit value is set to 1, making the total count of occurrences of 1’s an odd number. If the total number of 1’s in a given set of bits is already odd, the parity bit’s value is 0.

## Encoding a message by Hamming Code

The procedure used by the sender to encode the message encompasses the following steps

- Step 1 : Calculation of the number of redundant bits.
- Step 2 : Positioning the redundant bits.
- Step 3 : Calculating the values of each redundant bit.

### Step 1 : Calculation of the number of redundant bits

The number of redundant bits can be calculated using the following formula:

```
2^r ≥ m + r + 1
where, r = redundant bit, m = data bit
```

**Suppose the number of data bits is 7, then the number of redundant bits can be calculated using:**
**= 2^4 ≥ 7 + 4 + 1** Thus, the number of redundant bits= 4

### Step 2 : Positioning the redundant bits

The r redundant bits placed at bit positions of powers of 2. 1, 2, 4, 8, 16 etc. They are referred in the rest of this text as r1 (at position 1), r2 (at position 2), r3 (at position 4), r4 (at position 8) and so on.

### Step 3 − Calculating the values of each redundant bit.

The redundant bits are parity bits. A parity bit is an extra bit that makes the number of 1s either even or odd. The two types of parity are −

- Even Parity − Here the total number of bits in the message is made even.
- Odd Parity − Here the total number of bits in the message is made odd.

Each redundant bit, ri, is calculated as the parity, generally even parity, based upon its bit position. It covers all bit positions whose binary representation includes a 1 in the ith position except the position of ri. Thus −

- r1 is the parity bit for all data bits in positions whose binary representation includes a 1 in the least significant position excluding 1 (3, 5, 7, 9, 11 and so on)
- r2 is the parity bit for all data bits in positions whose binary representation includes a 1 in the position 2 from right except 2 (3, 6, 7, 10, 11 and so on)
- r4 is the parity bit for all data bits in positions whose binary representation includes a 1 in the position 3 from right except 4 (5-7, 12-15, 20-23 and so on)
- r8 is the parity bit for all data bits in positions whose binary representation includes a 1 in the position 4 from right except 8 (9-16 and so on)

## example

Suppose the data to be transmitted is 1011001, the bits will be placed as follows:

- R1 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the least significant position. R1: bits 3, 5, 7, 9, 11

To find the redundant bit R1, we check for **even parity**. Since the total number of 1’s in all the bit positions corresponding to R1 is an even number the value of R1 (parity bit’s value) = 0

- R2 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the second position from the least significant bit. R2: bits 3,6,7,10,11

To find the redundant bit R2, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R2 is odd the value of R2(parity bit’s value)=1

- R4 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the third position from the least significant bit. R4: bits 5, 6, 7

To find the redundant bit R4, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R4 is odd the value of R4(parity bit’s value) = 1

- R8 bit is calculated using parity check at all the bits positions whose binary representation includes a 1 in the fourth position from the least significant bit. R8: bit 9,10,11

To find the redundant bit R8, we check for even parity. Since the total number of 1’s in all the bit positions corresponding to R8 is an even number the value of R8(parity bit’s value)=0.

- Thus, the data transferred is:

```
module HmamingEncoder(
output reg[10:0] dout,
input wire[6:0] din
);
always @(din) begin
dout = MakeOddPatiryBit(din);
$display ("din : %b , dout : %b , redundant bit = %b" , din , dout , {dout[7],dout[3],dout[1],dout[0]});
end
function [10:0]MakeOddPatiryBit(input [6:0] data);
reg R8;
reg R4;
reg R2;
reg R1;
reg[10:0] tmp;
begin
tmp = {data[6:4] , R8 , data[3:1] ,R4 , data[0] , R2 , R1 };
R1 = tmp[10] ^ tmp[8] ^ tmp[6] ^ tmp[4] ^ tmp[2] ;
R2 = tmp[10] ^ tmp[9] ^ tmp[6] ^ tmp[5] ^ tmp[2] ;
R4 = tmp[6] ^ tmp[5] ^ tmp[4];
R8 = tmp[10] ^ tmp[9] ^ tmp[8];
MakeOddPatiryBit = {data[6:4] , R8 , data[3:1] ,R4 , data[0] , R2 , R1 };
end
endfunction
endmodule
```

## Decoding a message in Hamming Code

Once the receiver gets an incoming message, it performs recalculations to detect errors and correct them. The steps for recalculation are −

- Step 1 : Calculation of the number of redundant bits.
- Step 2 : Positioning the redundant bits.
- Step 3 : Parity checking.
- Step 4 : Error detection and correction

### Step 1 − Calculation of the number of redundant bits

Using the same formula as in encoding, the number of redundant bits are ascertained.
`2r ≥ m + r + 1`

where m is the number of data bits and r is the number of redundant bits.

### Step 2 − Positioning the redundant bits

The r redundant bits placed at bit positions of powers of 2, i.e. 1, 2, 4, 8, 16 etc.

### Step 3 − Parity checking

Parity bits are calculated based upon the data bits and the redundant bits using the same rule as during generation of c1,c2 ,c3 ,c4 etc. Thus

- c1 = parity(1, 3, 5, 7, 9, 11 and so on)
- c2 = parity(2, 3, 6, 7, 10, 11 and so on)
- c3 = parity(4-7, 12-15, 20-23 and so on)
- c4 = parity(9-15 and so on)

### Step 4 − Error detection and correction

The decimal equivalent of the parity bits binary values is calculated. If it is 0, there is no error. Otherwise, the decimal value gives the bit position which has error. For example, if c1c2c3c4 = 1001, it implies that the data bit at position 9, decimal equivalent of 1001, has error. The bit is flipped to get the correct message.

```
module HammingDecoder(
input wire [10:0] din
);
always @(din) begin
$display("Received value: %b , Data : %b ,checksum: %b ,Status: %s",
din,{din[10:8],din[6:4],din[2]},{din[7],din[3],din[1],din[0]} , (ChackParity(din) == 1)? ("OK") :("Error"));
end
function ChackParity(input [10:0] data);
reg R8;
reg R4;
reg R2;
reg R1;
begin
R1 = data[10] ^ data[8] ^ data[6] ^ data[4] ^ data[2] ;
R2 = data[10] ^ data[9] ^ data[6] ^ data[5] ^ data[2] ;
R4 = data[6] ^ data[5] ^ data[4];
R8 = data[10] ^ data[9] ^ data[8];
if({data[7],data[3],data[1],data[0]} == {R8,R4,R2,R1})
ChackParity = 1'b1;
else
ChackParity = 1'b0;
end
endfunction
endmodule
```