Single-error-correction of messages with binary Hamming Code in Quartus VHDL
- Objective
- What's included
- Theoretical Approach
- Implementation
- Component Simulation
- Improvements
- Tools
- Testing
- Creators
This is the first assignment of the Advanced Computer Architecture (ACA) course lectured by professor António Borges.
The objective of the project involves the implementation of the Hamming code for 1-bit error correction with the triplet [15, 11, 3], where:
- n (number of bits of the encoded message) = 15
- k (number of information bits) = 11
- d (Hamming distance) = 3.
And in order to closely simulate and describe the hardware, the structural modeling style was adopted.
The module:
- encoder is implemented with a sequential digital circuit, from the schematics given by the professor
- decoder is implemented with a combinatorial digital circuit
Decoder/
+-- and_2.vhd
+-- decoder.vhd
+-- decoder.vwf
+-- xnor_2.vhd
+-- xor_2.vhd
Encoder/
+-- Flip_flop_bundle.vhd
+-- and_2.vhd
+-- and_4.vhd
+-- control_unit.vhd
+-- control_unit.vwf
+-- counter_4bit.vhd
+-- counter_4bits.vhd
+-- encoder.vhd
+-- encoder.vwf
+-- flipFlopDSimul.vhd
+-- mux2_1.vhd
+-- mux4_1.vhd
+-- nand_2.vhd
+-- not_1.vhd
+-- or_2.vhd
+-- rom.vhd
+-- rom.vwf
+-- xnor_2.vhd
+-- xor_2.vhd
The values for the n and k variables are calculated based on the number of redundant bits r = 4 addressed by the problem:
- length of the encoded message:
- length of the message:
The encoding process of a message is described by the formula:
where:
- x is the encoded message
- m is the message to be encoded
- G is the k x n generator matrix
To get the generator matrix, the following formula was used:
where:
is the k x k identity matrix
- matrix A is composed of all permutations, of the redundant bits, with 2 or more bits equal to '1' (each column represents one permutation). The permutation order must be the same across both the encoder and decoder:
- the transpose of matrix A can now be obtained:
Concatenating both matrices results in the generator matrix used to produce the encoded message:
The multiplication of the message by the last four columns of the G matrix resolves the 4 redundant bits. This operation is the same as using the four parity equations obtained from the A matrix:
The decoding process is described by the formula:
where:
-
y is the received message, possibly with transmission errors, and
is the transpose of y. This message is 15 bits long because it contains the four redundant bits.
-
matrix H is obtained by:
Matrix H is therefore:
The result of multiplying the H matrix by allows for the detection of transmission errors:
-
if all four parity bits are '0', then the message has no errors
-
if one or more parity bits are '1', then the message has one or more errors
Simulation of the main components of the project:
The decoder can be further improved by reducing the number of XOR operations required to calculate the parity bits.
The software Quartus Prime Lite Edition v18.1 was used to develop this project.
For testing purposes it's required the creation of new simulation files. This is because the version of Quartus used stores the absolute path of the components, used by the top level entity, in the .vwf files.
Diogo Guedes
Miguel Carvalho
- to be filled