VIETNAM NATIONAL UNIVERSITY

HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY

FACULTY OF APPLIED SCIENCE

REPORT
LINEAR ALGEBRA – MT1007

TOPIC: HAMMING CODE

Lecturer: Nguyễn Tiến Dũng

Class: CC02
Group: 10

Ho Chi Minh City, November 2024

 Ho Chi Minh City University of Technology
Faculty of Applied Science

Member List
STT Thành viên nhóm MSSV Công việc
1 Trần Hoàng Nam 2452800 MATLAB Code + Content
2 Huỳnh Hoàng Khải 2452508 LATEX Code + Content
3 Trương Võ Thành Nghĩa 2412279 MATLAB Code + Content
4 Lê Trần Bảo Nguyên 2452850 Presentation + Content
5 Nguyễn Thành Lộc 1951166 Content

Report Linear Algebra - MT1007 Trang 1/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

Contents
1 PROBLEM STATEMENT 3

2 METHOD OVERVIEW 4
2.1 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Types of Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Hamming Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Other Types of Hamming Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 DATA PREPROCESSING 5
3.1 Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 METHOD IMPLICATION 8
4.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.4 Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5 MATLAB CODE 10
5.1 Hamming (7,4) Error Correction Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Hamming (7,4) Code with Specific Single Error Correction . . . . . . . . . . . . . . . . . . 12

6 DISCUSSION 14
6.1 Advantages of Hamming Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.2 Disadvantages of Hamming Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.3 Later Iterations of Hamming Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

7 REFERENCES 14

Report Linear Algebra - MT1007 Trang 2/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

1 PROBLEM STATEMENT

In digital communications, maintaining data integrity and accuracy over

noisy channels is crucial. Data is vulnerable to noise-induced changes,
leading to potential errors and information loss. Hence, reliable error
detection and correction methods are essential for preserving message
accuracy.

During the 1940s, Richard Wesley Hamming became increasingly

frustrated whenever he had to restart his applications from the beginning
due to the poor quality and unreliability of the punched card readers.
Over the next few years, he dedicated himself to developing a series of
highly efficient algorithms to solve the error correction problem. In 1950,
he published a method that is now known as the Hamming Code. Some
current applications still use his code.

The objective of the Hamming Code is to address the challenge posed

by noisy communication channels by creating an encoding scheme that
can both detect and rectify errors. By focusing on the Hamming Code, a
method for error correction, we aim to refine and extend its capabilities to
enhance its performance in contemporary digital communication systems.

The broader context of this problem encompasses the increasing reliance

on digital communication for a multitude of applications, from simple
text messaging to complex data transfer in distributed networks. As we
become more dependent on digital data exchange, the importance of
error-free transmission becomes paramount, aligning with our goal to
ensure that our data encoding methods keep pace with the growing
demands for reliability and efficiency in digital communications.

Report Linear Algebra - MT1007 Trang 3/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

2 METHOD OVERVIEW
2.1 Error Detection
When data is transmitted from one device to another, the system does not guarantee whether the data
received by the device is the same as the data transmitted by another device. An error occurs when the
message received at the recipient’s end is not the same as the message transmitted.

2.2 Types of Errors

There are two types of errors:

• Single-Bit Error

• Burst Error

Since the Hamming Code cannot handle multiple errors or errors that affect multiple bits, we will focus
only on single-bit errors.
As illustrated in the example, a single-bit error occurs when a single bit in a data block is corrupted
(e.g., a bit changes from 0 to 1).

Single-Bit Error Example

Single-bit errors mainly occur in Parallel Data Transmission. For instance, if eight wires are used to
send the eight bits of a byte, and one of the wires becomes noisy, a single bit in the byte is corrupted.

2.3 Hamming Code

The Hamming Code is a binary error-correcting code that adds redundant parity bits to data to
detect and correct errors. These parity bits are strategically inserted at specific positions, enabling the
identification and correction of a single-bit error in the data block. The code uses binary operations to
create a system where the receiver can decode the information and restore the original data despite noise.

Efficiency of Hamming Code

Hamming Code is particularly efficient for environments with low error rates where single-bit error
correction is sufficient. It optimizes memory usage by incorporating the minimum number of parity bits
necessary to:

Report Linear Algebra - MT1007 Trang 4/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

• Detect single-bit errors.

• Correct single-bit errors within a block of data.

How Hamming Code Works

By strategically calculating the placement of parity bits using combinatorial mathematics and Boolean
algebra, Hamming Code ensures:

• Precise identification of the erroneous bit.

• Minimal redundancy for memory optimization.

This makes Hamming Code an ideal choice for low-error environments where reliable data transmission
is critical.

2.4 Other Types of Hamming Code

Total Number Bits Used as

Name Parity Bits
of Bits (n) Data (k)
Hamming (3,1) 2 3 1
Hamming (7,4) 3 7 4
Hamming (15,11) 4 15 11
Hamming (31,26) 5 31 26
Hamming (63,57) 6 63 57
Hamming (2m-1,
m n = 2m − 1 k = 2m − 1 − m
2m-1-m)

3 DATA PREPROCESSING
3.1 Calculation
Encoding and decoding with the Hamming Code are accomplished using matrix multiplication modulo
2, where the only constants are 0 and 1. The addition and multiplication rules follow basic modulo 2
arithmetic.

Report Linear Algebra - MT1007 Trang 5/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

3.2 Encoding
To encode, we first construct a generator matrix.

• Consider 4 information bits: d1 , d2 , d3 , d4 .

• Define 3 parity bits:

p1 = d1 + d2 + d4 , p2 = d1 + d3 + d4 , p3 = d2 + d3 + d4

• A Hamming (7,4) code places parity bits at positions 2n (n ≥ 0), which are positions 1, 2, and 4 in
the codeword.

Constructing the Generator Matrix

Each bit can be represented as a vector:

       
1 0 0 0
       
0 1 0 0
0 ,
d1 =  
0 ,
d2 =   d3 = 
1 ,
 d4 =  
0
       
0 0 0 1

The parity bits are represented as:

     
1 1 0
     
1 0 1
p1 = 
0 ,
 p2 = 
1 ,
 p3 =  
1
     
1 1 1

The generator matrix G is constructed by arranging the parity bits and data bits in the order
[p1 , p2 , d1 , p3 , d2 , d3 , d4 ]. However, the order of parity bits and data is varies so we manage them in the

Report Linear Algebra - MT1007 Trang 6/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

order [d1 , d2 , d3 , d4 , p1 , p2 , p3 ] This gives:

 
1 0 0 0 1 1 0
 
0 1 0 0 1 0 1
G=
0

 0 1 0 0 1 1
0 0 0 1 1 1 1

3.3 Decoding

Constructing the Parity Check Matrix H

As we know, the parity bits are positioned at 2n (n ≥ 0), corresponding to positions 1, 2, and 4 in
the codeword. To verify data bits, each row of H corresponds to a parity equation, and each column
represents a bit position in the codeword.

Filling the Parity Check Matrix H

First Parity Bit (Position 1): - Parity p1 checks all bits with a least significant bit of 1. - The parity
equation is:
p1 = d1 + d2 + d4

- p1 checks positions 1, 3, 5, and 7, so the first row of H is:

1010101

Second Parity Bit (Position 2): - Parity p2 checks bits where the second least significant bit of the
column is 1. - The parity equation is:
p2 = d1 + d3 + d4

- p2 checks positions 2, 3, 6, and 7, so the second row of H is:

0110011

Third Parity Bit (Position 4): - Parity p3 checks bits where the third least significant bit of the
column is 1. - The parity equation is:
p3 = d2 + d3 + d4

- p3 checks positions 4, 5, 6, and 7, so the third row of H is:

0001111

The Parity Check Matrix H

Combining these rows, the parity check matrix H is:
 
1 0 1 0 1 0 1
 
H = 0
 1 1 0 0 1 1

0 0 0 1 1 1 1

Report Linear Algebra - MT1007 Trang 7/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

4 METHOD IMPLICATION
4.1 Objective
Find and fix 1-bit errors after the transferring of data
 
1 0 1 1
 
x=
0 1 0 1

1 1 1 0

4.2 Encoding
 
1 0 1 1
 
x=
0 1 0 1

1 1 1 0

and the generator matrix:  

1 0 0 0 1 1 0
 
0 1 0 0 1 0 1
G=
0

 0 1 0 0 1 1
0 0 0 1 1 1 1

The codeword y is calculated as:

 
  1 0 0 0 1 1 0  
1 0 1 1   1 0 1 1 0 1 0
  0 1 0 0 1 0 1  
y =x×G=
0 1 0  × 0
1   = 0 1 0 1 0 1 0
0 1 0 0 1 1  
1 1 1 0 1 1 1 0 0 0 0
 
0 0 0 1 1 1 1

Error During Transmission

Suppose single bit errors occurs during transmission at 3rd position of each row. The received codeword
becomes:  
1 0 0 1 0 1 0
′
 
y =
0 1 1 1 0 1 0

1 1 0 0 0 0 0

4.3 Decoding
To decode y ′ , we use the parity-check matrix:
 
1 0 1 0 1 0 1
 
H=
0 1 1 0 0 1 1

0 0 0 1 1 1 1

Report Linear Algebra - MT1007 Trang 8/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

The syndrome is calculated as:

 
1 0 1
 
0 1 1
     
1 0 1 0 1 0 1 0 1 0 1 1 0
 

H × y ′T
     
=
0 1 1 0 0 1 1 
 × 1 1 =
0 1
  1 0

 
0 0 0 1 1 1 1 0 0 0 1 1 0
 
1 1 0


0 0 0

Since the syndrome is not zero, y ′ is not a valid codeword. The syndrome [0 1 1] corresponds to the binary
representation of 3 in decimal, indicating an error at position 3.

4.4 Error Correction

Fixing the error at position 3, the corrected codeword is:
 
1 0 0 1 0 1 0
′
 
y = 0
 1 1 1 0 1 0

1 1 0 0 0 0 0

By taking the data bit positions, we recover:

 
1 0 1 1
 
0 1 0 1
 
1 1 1 0
.

4.5 Conclusion
- The Hamming code effectively detects and corrects single-bit errors using a small number of parity bits.
- It is particularly advantageous for handling large amounts of data but assumes that only a single-bit
error occurs.

Report Linear Algebra - MT1007 Trang 9/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

5 MATLAB CODE
5.1 Hamming (7,4) Error Correction Code

1 clc ;
2 clear ;
3 % Create the parity - check matrix H and the generator matrix G
4 H = [1 0 1 0 1 0 1;
5 0 1 1 0 0 1 1;
6 0 0 0 1 1 1 1];
7 G = [1 0 0 0 1 1 0;
8 0 1 0 0 1 0 1;
9 0 0 1 0 0 1 1;
10 0 0 0 1 1 1 1];
11 % Input data ( each row is a 4 - bit data word )
12 data = [1 0 1 1; 0 1 0 1; 1 1 1 0];
13

14 % Encode the data

15 encoded_data = mod ( data * G , 2) ;
16 disp ( ’ Encoded data : ’) ;
17 disp ( encoded_data ) ;
18

19 % Simulate errors at the 3 rd position of each row

20 e n c o d e d _ d a t a _ w i t h _ e r r o r = encoded_data ;
21 e n c o d e d _ d a t a _ w i t h _ e r r o r (: , 3) = mod ( e n c o d e d _ d a t a _ w i t h _ e r r o r (: , 3) + 1 , 2) ;
22 disp ( ’ Data with errors ( after simulating errors ) : ’) ;
23 disp ( e n c o d e d _ d a t a _ w i t h _ e r r o r ) ;
24

25 % Calculate the syndrome to detect errors

26 syndrome = mod ( e n c o d e d _ d a t a _ w i t h _ e r r o r * H ’ , 2) ;
27 disp ( ’ Syndrome for error detection : ’) ;
28 disp ( syndrome ) ;
29

30 % Create a mapping table of syndromes to error positions

31 erro r_patt erns = eye (7) ; % Create 7 unit error vectors
32 syndromes = mod ( error _patte rns * H ’ , 2) ; % Calculate the corresponding syndrome
33

34 % Correct errors based on the syndrome

35 for i = 1: size ( encoded_data_with_error , 1)
36 if any ( syndrome (i , :) ) % If there is an error
37 % Find the error position by comparing the syndrome with the mapping table
38 for j = 1: size ( syndromes , 1)
39 if isequal ( syndrome (i , :) , syndromes (j , :) )
40 fprintf ( ’ Error occurred at position % d in row % d \ n ’ , j , i ) ;
41 % Correct the error by flipping the bit at the error position
42 e n c o d e d _ d a t a _ w i t h _ e r r o r (i , j ) = mod ( e n c o d e d _ d a t a _ w i t h _ e r r o r (i , j ) + 1 , 2)
;
43 break ;
44 end
45 end
46 end
47 end
48

Report Linear Algebra - MT1007 Trang 10/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

49 disp ( ’ Data after error correction ( if any ) : ’) ;

50 disp ( e n c o d e d _ d a t a _ w i t h _ e r r o r ) ;
51

52 % Extract the original data from the Hamming (7 ,4) code after error correction
53 decoded_data = e n c o d e d _ d a t a _ w i t h _ e r r o r (: , [1 , 2 , 3 , 4]) ;
54 disp ( ’ Original data after decoding ( after error correction ) : ’) ;
55 disp ( decoded_data ) ;

Report Linear Algebra - MT1007 Trang 11/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

5.2 Hamming (7,4) Code with Specific Single Error Correction

1 clc ;
2 clear ;
3 % Create the parity - check matrix H and the generator matrix G
4 H = [1 0 1 0 1 0 1;
5 0 1 1 0 0 1 1;
6 0 0 0 1 1 1 1];
7 G = [1 0 0 0 1 1 0;
8 0 1 0 0 1 0 1;
9 0 0 1 0 0 1 1;
10 0 0 0 1 1 1 1];
11

12 % Input data ( each row is a 4 - bit data word )

13 data = [1 0 1 1; 0 1 0 1; 1 1 1 0];
14

15 % Encode the data

16 encoded_data = mod ( data * G , 2) ;
17 disp ( ’ Encoded data : ’) ;
18 disp ( encoded_data ) ;
19

20 % Simulate an error in a specific row and position

21 row_ with_e rror = 2; % Specify the row where the error occurs
22 p o s i t i o n _ w i t h _ e r r o r = 5; % Specify the position where the error occurs
23 e n c o d e d _ d a t a _ w i t h _ e r r o r = encoded_data ; % Copy the encoded data
24 e n c o d e d _ d a t a _ w i t h _ e r r o r ( row_with_error , p o s i t i o n _ w i t h _ e r r o r ) = ...
25 mod ( e n c o d e d _ d a t a _ w i t h _ e r r o r ( row_with_error , p o s i t i o n _ w i t h _ e r r o r ) + 1 , 2) ; % Flip the
bit
26

27 disp ( ’ Data with a single error ( specific row and position ) : ’) ;

28 disp ( e n c o d e d _ d a t a _ w i t h _ e r r o r ) ;
29

30 % Calculate the syndrome to detect errors

31 syndrome = mod ( e n c o d e d _ d a t a _ w i t h _ e r r o r * H ’ , 2) ;
32 disp ( ’ Syndrome for error detection : ’) ;
33 disp ( syndrome ) ;
34

35 % Create a mapping table of syndromes to error positions

36 erro r_patt erns = eye (7) ; % Create 7 unit error vectors
37 syndromes = mod ( error _patte rns * H ’ , 2) ; % Calculate the corresponding syndrome
38

39 % Correct errors based on the syndrome

40 for i = 1: size ( encoded_data_with_error , 1)
41 if any ( syndrome (i , :) ) % If there is an error
42 % Find the error position by comparing the syndrome with the mapping table
43 for j = 1: size ( syndromes , 1)
44 if isequal ( syndrome (i , :) , syndromes (j , :) )
45 fprintf ( ’ Error occurred at position % d in row % d \ n ’ , j , i ) ;
46 % Correct the error by flipping the bit at the error position
47 e n c o d e d _ d a t a _ w i t h _ e r r o r (i , j ) = mod ( e n c o d e d _ d a t a _ w i t h _ e r r o r (i , j ) + 1 , 2)
;
48 break ;
49 end
50 end

Report Linear Algebra - MT1007 Trang 12/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

51 end
52 end
53

54 disp ( ’ Data after error correction ( if any ) : ’) ;

55 disp ( e n c o d e d _ d a t a _ w i t h _ e r r o r ) ;
56

57 % Extract the original data from the Hamming (7 ,4) code after error correction
58 decoded_data = e n c o d e d _ d a t a _ w i t h _ e r r o r (: , [1 , 2 , 3 , 4]) ;
59 disp ( ’ Original data after decoding ( after error correction ) : ’) ;
60 disp ( decoded_data ) ;

Report Linear Algebra - MT1007 Trang 13/14

School year: 2024 - 2025
 Ho Chi Minh City University of Technology
Faculty of Applied Science

6 DISCUSSION
6.1 Advantages of Hamming Code
• Effectively used to detect and correct errors.

• Single-bit error correction is effective on data stream networks.

• Memory efficient for handling a large amount of data bits.

6.2 Disadvantages of Hamming Code

• Higher bandwidth usage.

• Adding extra parity bits for error correction reduces the bit rate of the transmitter.

• Unstable when more than two errors occur.

6.3 Later Iterations of Hamming Code

Extended Hamming Code (e.g., Hamming 8,4)

• Extends the Hamming code by adding an additional parity bit.

• Can detect up to two-bit errors but still corrects only one bit.

Iterative Decoding

• Applies advanced decoding techniques to the Hamming code.

• Improves error detection and correction by performing multiple decoding passes.

Hybrid Approaches

• Combines Hamming code with other error correction methods such as interleaving or Low-Density
Parity-Check (LDPC) codes.

• Offers enhanced performance in noisy environments.

7 REFERENCES
1. But what are Hamming codes? The origin of error correction (3blue1brown).

2. Hamming code (Wikipedia).

3. L. Garcia and C. Penland, MATLAB Projects for Scientists and Engineers, Prentice Hall, Upper
Saddle River, NJ, 1996.

4. Error Detection in Computer Networks (GeekforGeeks).

Report Linear Algebra - MT1007 Trang 14/14

School year: 2024 - 2025