Elementary Study of Coding Theory:

Controlling noise in communication

An Internship Report

Completed during 16th June to 16th July, 2025

Submitted by

Ujjal Tanti
Dibru College

Supervised by

Dr. Pankaj K. Das

Department of Mathematical Sciences

Submitted to

Department of Mathematical Sciences

Tezpur University, Napaam
Tezpur-784028
Assam, India.
ABSTRACT

This report describes the work I did during my one-month internship on the topic: Con-
trolling noise in communication, under the guidance of Dr. Pankaj K. Das, De-
partment of Mathematical Sciences, Tezpur University. During this time, I learned how
mathematics is used to protect information when it is sent from one place to another.
This field is known as coding theory, and it helps in detecting and correcting mistakes in
data transmission.
In the internship, I studied many important topics such as error detection and
correction, Hamming codes, Mutually Orthogonal Latin Squares, Hadamard
codes, the Singleton bound, the Plotkin bound, and Gilbert-Varshamov Bound.
These topics helped me understand how messages are made more reliable using extra in-
formation, so even if there is a small error during transfer, the original message can still
be recovered. I also learned how redundancy is used to increase the reliability of data.
What made the learning more interesting were real-life examples such as how QR codes
and ISBN numbers are created using mathematical logic. These examples helped me
clearly understand how these theories are used in the world around us.
Another important part of my learning was the use of LaTeX, a software for writing
documents, especially mathematical ones. Before the internship, I had never used LaTeX.
Although it was difficult at first, I gradually became more proficient and now feel confident
in using LaTeX to create clean, structured, and professional documents.
This internship helped me in many ways. It not only improved my mathematical
knowledge but also changed the way I look at technology. I now understand that many
things we use every day, like barcodes and digital messages, depend on deep mathematical
ideas. This experience has made me more interested in applied mathematics and has given
me skills that I will use in the future, both in my studies and in professional work.

1
DECLARATION BY THE
STUDENT

I, Ujjal Tanti (Dibru College), do hereby declare that the subject matter in this intern-
ship report is the record of my reading work/survey work/research work, done by me
during the one month period, from 16th June 2025 to 16th July 2025, carried out
with full integrity, honesty and concentration under the immaculate supervision of Dr.
Pankaj K. Das, Department of Mathematical Sciences, and submitted to the Depart-
ment of Mathematical Sciences, Tezpur University.

Date: Ujjal Tanti

Place: Dibru College

2
ACKNOWLEDGEMENT

I would like to express my deepest gratitude to Dr. Pankaj K. Das, my internship

supervisor at the Department of Mathematical Sciences, Tezpur University, for his ex-
ceptional guidance, continuous support, and valuable insights throughout the duration of
my internship. His expertise and constructive feedback helped me understand complex
concepts in coding theory and shaped my overall learning experience. I truly appreci-
ate his patience and dedication in guiding me whenever I faced challenges during the
internship.
I would also like to thank the entire Department of Mathematical Sciences at Tezpur
University for this internship program. The resources and academic environment of the
department were incredibly helpful for my personal and professional growth.
Additionally, I am grateful to my colleagues and fellow interns for their collaboration
and for sharing knowledge that enhanced my learning. Their assistance made the work
environment more enriching and enjoyable.
This internship has been a transformative learning experience, and I am grateful to
everyone who contributed to making it a success.

3
Contents

Abstract 1

Declaration by the Student 2

Acknowledgement 3

1 Introduction and Preliminaries 6

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Some Examples and Definitions 9

2.1 Examples : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Symbols and Codewords . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Illustration of Example 2.1.2. . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Binary Symmetric Channel and Problems . . . . . . . . . . . . . . . . . 13
2.5 Real Life Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Hamming Distance and Error Detection and Correction 20

3.1 Hamming Distance and Nearest Neighbour Decoding . . . . . . . . . . . 20
3.2 t-Error Detecting and t-Error Correcting Codes . . . . . . . . . . . . . . 28
3.3 Minimum Distance and Hamming Balls . . . . . . . . . . . . . . . . . . . 31

4 Main Coding Theory 39

4.1 Bounds on size of a code . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Equivalent Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Codes from Mutually Orthogonal Latin Squares (MOLS) . . . . . . . . . 50
4.4 Puncturing a Code and Hadamard Codes . . . . . . . . . . . . . . . . . . 53

4
Conclusion 56

References 57
———————–

5
Chapter 1

Introduction and Preliminaries

The subject Coding Theory was initiated in around 1948 by Richard W. Hamming (1915-
1998). It becomes an essential part of the modern electronic world, with applicatons in
compact discs, satellites, space probes (like Mariner 9), and mobile phone networks.

1.1 Introduction
Coding theory is an important branch of mathematics and computer science that deals
with the transmission of data in a reliable way. In modern communication systems, data
is often sent over noisy channels where errors can occur due to interference, distortion,
or loss. Coding theory helps to design methods that can detect and correct these errors,
ensuring that the original data is received correctly.
During my internship, I explored the basics of coding theory and how it is applied
in real-world technologies. The main goal was to understand how error-correcting codes
work and why they are essential in everyday systems like digital communication, barcodes,
QR codes, and ISBN numbers. These systems use special mathematical structures that
allow them to detect and even fix mistakes that may happen while transferring data.
The study of coding theory involves mathematical concepts like binary operations,
vector spaces, matrices, and modular arithmetic. These tools are used to create and ana-
lyze codes such as Hamming codes, parity-check codes, and linear block codes. Learning
how these codes are constructed and used helped me gain a better understanding of both
mathematics and computer applications.

6
 This internship gave me the opportunity to not only study theoretical concepts but
also see their practical impact. It strengthened my foundation in applied mathematics
and introduced me to important skills like LaTeX for scientific documentation.

1.2 Preliminaries
Before diving into the detailed study of error-correcting codes, it is important to under-
stand some basic terms and definitions that form the foundation of coding theory:

ˆ Alphabet: A finite set of symbols used to form messages. In binary codes, the
alphabet is {0, 1}.

ˆ Codeword: A valid sequence of symbols from the alphabet that represents encoded
information.

ˆ Block Code: A set of fixed-length codewords used for encoding messages.

ˆ Hamming Distance: The number of positions at which two codewords differ. It

is used to measure how different two codewords are.

ˆ Error Detection and Correction: Techniques used to identify and fix errors in
received data using special patterns or redundancy.

ˆ Redundancy: Extra bits added to data to help detect or correct errors.

ˆ Linear Code: A code where the linear sum of any two codewords is also a code-
word, usually studied using vector spaces.

ˆ Probability: In coding theory, probability is used to model the chances of errors

during data transmission. For example, a binary symmetric channel assumes that
each bit has a fixed probability p of being flipped (from 0 to 1 or vice versa).
Understanding basic probability helps in analyzing how reliable a code is.

ˆ Modular Arithmetic in Zp : Many operations in coding theory are performed

over a finite field, especially Zp , where p is a prime number. In Zp , numbers are
added and multiplied modulo p. For example, in Z2 , we have 1 + 1 = 0. This
kind of arithmetic is essential when working with parity-check matrices, generator
matrices, and encoding/decoding schemes.

7
 Understanding these terms was essential for me to move ahead with topics like Ham-
ming codes, parity-check matrices, generator matrices, and decoding algorithms. These
concepts helped me analyze how data is encoded, transmitted, and decoded safely, even
in the presence of errors.

—————-

8
Chapter 2

Some Examples and Definitions

2.1 Examples :
Example 2.1.1. Alice wants to send a message to Bob. She can communicate with him
by sending him a word formed from symbols taken from some fixed set. But every time
she sends a word, there is a chance that some of its symbols will be corrupted, so the
word that Bob receives may not be the word that Alice sent. How can Alice and Bob
communicate reliably?
(“Alice and Bob can communicate reliably by using error-detecting and error-correcting
codes.”)
Where Alice is ‘Encoder’ and Bob is ‘Decoder’. The symbols are sent through a channel.
The channel could be a phone line, a fibre-optic cable, the air in a room (the medium
through which sound-waves travel), a compact-disc, and so on. The errors could come
from human error, imperfections in the equipment, aeroplanes flying overhead, scratches
on the disc, and so on. These unwanted phenomena are called noise.
Example 2.1.2. Alice wants to send the message ‘Yes’ or ‘No’ to Bob. The available
symbols are 0 and 1, and we will imagine that the channel is a noisy phone-line to which
Alice and Bob have connected their respective computers.

noise
↓
message −→ encoder −→ channel −→ decoder −→ decoded message

Figure 2.1: Block Diagram of a Communication System.

9
Scheme 1: The two decide, in advance, that Alice will send

ˆ ‘No’ −→ 00

ˆ ‘Yes’ −→ 11

If Bob receives 00 or 11 then he will assume this is the word that Alice sent, and
decode her message. If he receives 01 or 10 then Bob knows an error has occurred,
but he does not know which symbol is wrong. If he can get in touch with Alice to
ask her to resend the message, this may be acceptable.

Scheme 2: Suppose instead they decide that Alice will send

ˆ ‘No’ −→ 000

ˆ ‘Yes’ −→ 111

Bob decodes a received word based on its majority symbol. For example, if he
receives 000, 001, 010, or 100, he assumes Alice sent 000 and decodes it as ‘No’.
Similarly, if he receives 111, 110, 101, or 011, he assumes Alice sent 111 and decodes
it as ‘Yes’. This strategy allows for correct decoding provided at most one error
occurs.
If two error occur then, the majority symbol of the received word will flip, when
Bob decodes the received word, he gets the wrong message :

ˆ Suppose Alice sends 111 (‘Yes’). If two errors occur, the received word could
be 001, 010, or 100. In all these cases, the majority symbol is ‘0’, so Bob will
decode the received word as 000 (‘No’), which is the wrong message.

ˆ Suppose Alice sends 000 (‘No’). If two errors occur, the received word could
be 110, 101, or 011. In all these cases, the majority symbol is ‘1’, so Bob will
decode the received word as 111 (‘Yes’), which is the wrong message.

2.2 Symbols and Codewords

Definition 2.2.1.Let q ∈ N. A q-ary alphabet is a set of q different elements called sym-
bols. A word of length n over an alphabet A is a sequence (x1 , x2 , . . . , xn ) with xi ∈ A

10
for each i.

Equivalently, a word is an element of An = A × A × · · · × A. We will usually omit

the round brackets and commas when writing words. For example, in Example 2.1.2, the
alphabet is 0, 1 and the binary word (1, 1, 1) is written as 111, corresponding to ‘Yes’ in
Scheme 2.

Definition 2.2.2. Let A be an alphabet and n ∈ N. A code over A of length n over A is

a subset C ⊆ An containning at least two words. The elements of C are called codewords.
The size of C is |C|.

Problem 2.2.1: Why is it reasonable to require that a code always has at least two
codewords?
Solution : It is reasonable to require that a code always has at least two codewords
because, with only one codeword, there is no meaningful way to detect or correct errors
during transmission. If the code contains no codewords, it cannot represent any message,
and if it contains only one, then any errors cannot be distinguished from the correct
message, rendering the code useless for communication purposes.

Definition 2.2.3. The binary alphabet of binary digits, or bits, is {0, 1}. A binary code
is a code over {0, 1}.

The binary alphabet and binary codes are particularly important because modern
computers store and send data as sequences of bits.

2.3 Illustration of Example 2.1.2.

In Scheme 1, Alice and Bob use the binary code

C = {00, 11}

which has length 2 and size 2. The encoder is define by

11
 encoded as
‘No’ 00

encoded as
‘Yes’ 11
The decoder decodes 00 as ‘No’ and 11 as ‘Yes’. If 01 or 10 is received then rather
than take a blind guess, Bob requests retransmission.

In Scheme 2, Alice and Bob use the binary code

D = {000, 111}

which has length 3 and size 2. The encoder encodes ‘No’ as 000 and ‘Yes’ as 111. The
decoder decodes a received word according to its majority symbol, so if Bob receives
{000, 001, 010, 100} Bob assumes Alice sent 000 and decodes as ‘No’.
{111, 110, 101, 011} Bob assumes Alice sent 111 and decodes as ‘Yes’.
Suppose that whenever a bit 0 or 1 is sent down the channel used by Alice and Bob, there
is a probability p that it flips, so a 0 becomes a 1, and a 1 becomes a 0.

12
2.4 Binary Symmetric Channel and Problems
Definition 2.4.1. The binary channel in which each transmitted bit flips,so a 0 becomes
a 1 and a 1 becomes a 0, independently with probability p, is called the binary symmetric
channel with cross-over probability p.
The transition probabilities for the binary symmetric channel are shown in the digram
below.

1−p
0 0

p
p

1 1
1−p

Figure 2.2: Binary Symmetric Channel(BSC)

Problem 2.4.1: Why is it reasonable to assume that p < 1/2?

Solution : It is reasonable to assume that p < 1/2 because if p ≥ 1/2, the channel would
flip bits more than half the time, making the received message more likely to be incorrect
than correct. In such a case, the channel would effectively be worse than random noise,
and coding strategies would become ineffective or counterproductive. This assumption
ensures that transmitting the original message has a better chance of being received cor-
rectly than incorrectly, which is fundamental for reliable communication.

Remarks: The followin key points of Definition 2.2.2 should be noted:

(1) By Definition 2.2.2, all the codewords in a code have the same length.This is standar
modern codes and it helps make things simpler.
(2) Every code must have at least two codewords. A code with none or only one word
can’t be used for communication.

13
Example 2.4.2. Suppose ALICE wants to send BOB one of the messages ′ Stand −
down′ or ′ Launch nukes′ . They decide to use the binary code D = {000, 111} from
Example 2.3, with the encoder:

encoded as
‘Stand-down’ 000

encoded as
‘Launch nukes’ 111

Definition 2.4.3. Let C be a code of length n and size M . We define the (code) rate of
C to be (log2 M )/n.

Example 2.4.4. The binary codes {00, 11} and {000, 111} used by ALICE and BOB
in Example 2.1.2 have rates 1/2 and 1/3, respectively. A code of length n used for the
guessing game has size 16, so has rate (log1 6)/n = 4/n.

Problem 2.4.2: Alice thinks of a number between 0 and 15. Playing the role of Bob,
how many yes/no questions do you need to ask Alice to find out her number?
Solution : There are 16 possible numbers that Alice think, (0, 1, 2, . . . , 15).

Hence the size of the code M = 16

threfore (log1 6)/n = 4/n

Bob needs 4 questions to gather 4 bits of information, which is enough to determine

Alice’s number.

14
2.5 Real Life Examples
Now we discuss some examples which are important in real life :
Example 2.5.1. A Quick-Response code, or QR-code is a 2121 grid of small black
and white squares. The squares represent a binary sequence (black is 1 and white is 0)
encoding a short message. As shown below :

Format string
QR code

Each QR-code has a 15-bit format string, repeated twice in the grid. The format
string in this example is 111011111000100. (One place to find it is in 15 of the 17 bits
counterclockwise around the top-left square, as shown above.) The first 5 bits of the
format string specify the coding scheme used for the main message. The remaining
10 bits are used for error correction. After a fixed masking pattern is added, the format
string becomes a single codeword in the binary BCH [15,5,7]-code of length 15 and size 32.

The remaining data in this QR-code consists of 268 = 208 bits which correspond
to a single codeword in a Reed–Solomon code of length 26 over an alphabet of size 28 .
This codeword encodes a message of uppercase characters and some limited punctuation,
suitable for transmitting web addresses.

The encoder begins by converting each character in the message into a number be-
tween 0 and 44: for example, ‘C’ is sent to 12, ‘D’ to 13, and so on. Each pair
of numbers is then converted into an 11 bit binary word. (This is possible because
452 = 2025 =< 211 = 2048.) These words are then concatenated into a string of

15
198 = 152 bits which is encoded using the Reed–Solomon code.

This describes QR-codes with the lowest degree of error correction. The decoder will
always be able to correct up to three errors, in which a black square is read as a white
square, or vice versa.

Problem 2.5.1: Why do you think the format string is repeated twice? What is the
point of the three squares in the corners? (Including the white border, these squares
occupy 82 × 3 = 192 of the 212 = 441 little squares, so they must be important for some
reason!)
Solution : The format string is repeated twice to protect against data loss and ensure
correct interpretation.
The three corner squares are vital for detection, orientation, and alignment, which is why
they occupy a significant portion of the QR code.

Example 2.5.2.The Australian railway company ‘Victorian Railways’ used a telegraph

system and codebook. The entire codebook, as used in 1972, can be read online at
www.railpage.org.au/telecode/tc01.gif. Here is an extract from near the start.
Ayah Provide locomotive to work
Aybu Return locomotive at once
Azaf Breakdown train left at . . .
Azor Arrange to provide assistance locomotive
Azub A second locomotive will be attached to . . .
In telegraph transmission only upper case were used. So a typical message might be
something like ‘Breakdown train left at Sydney, provide locomotive to work’, encoded as
AZAF SYDNEY AYAH. The code has these properties.
(1) All codewords are of length 4 and are words over the alphabet A, B, C, . . . , X, Y,
Z. (Except for place names such as SYDNEY, which break our rule that all codewords
must have the same length.)
(2) The codewords are easily pronounceable. Most, but not all, have the pattern vowel–consonant–vowel–
Probably this reduced operator error when encoding messages.
(3) Most codewords differ from one another in at least two letters. So if I mean to send

16
‘Ayah’, but because of human error, or a problem with the line, ‘Ayam’ is received, then
it will be clear an error has occurred.

Problem 2.5.2: Most codewords are not English words, although a few are: ‘Coma’ is
an instruction about extra trucks, ‘Cosy’ is an instruction about loading trucks. Why
do you think English words were usually avoided?
Solution : English words were mostly avoided in the codebook to ensure clarity, preci-
sion, and safety in communication. Using unfamiliar but structured codewords reduced
the chances of misinterpretation, which was essential in a high-risk system like railway
operations.

Problem 2.5.3: Related instructions often start with the same letter: is this a good
feature of the coding scheme?
Solution: Yes, organizing related instructions to start with the same letter is a good
feature. It improves usability, speed, and memorability, making the system more efficient
for operators.

Example 2.5.4: The Mariner 9 probe, launched in 1971, took the first pictures of
Mars, ultimately transmitting 7239 pictures at a resolution of 700832 pixels. The images
were grey-scale, using 64 different shades of grey. The pictures were transmitted back to
Earth by sending one pixel at a time, so we can think of a message as a single number
between 0 and 63. The channel of radio waves can be modelled by the binary symmetric
channel in Definition 2.4.1. The naive approach of just encoding each pixel as a string of
6 bits would not have worked well. One survey article gives the cross-over probability as
0.05. So about 5% of all bits were flipped by the channel (with a 0 becoming a 1, and a
1 becoming a 0). With this scheme, the probability that any particular pixel would be
correctly transmitted is then 0.956 ≈ 0.74. So about 26% of the image would have been
wrong.

17
The matrix shows 32 of the 64 codewords in the binary Hadamard code used in
Mariner 9. A black square represents 0 and a white square represents 1. The other
32 codewords are obtained by flipping each bit in the 32 codewords shown. For
example, the first row shows the codeword 00 . . . 0, which flips to 11 . . . 1.
Please don’t confuse this diagram with a QR-code!

It was acceptable for each pixel to be encoded by up to 32 bits, so increasing the

amount of data to be stored and transmitted by a factor of 5. A code in which each bit
was repeated 5 times, along the lines of the codes C and D in Example 2.3, would have
reduced the probability that a pixel was incorrectly decoded to about 0.8%.

The code actually used was a binary Hadamard code of length 32 and size 64. (Half
of the codewords are shown in the diagram above.) We will study these codes in Part
B. This code is capable of correcting any 7 errors in a received word. So of the 32 bits
sent for each pixel, even if 7 of them are corrupted by the channel, the pixel will still be
correctly decoded. This reduces the probability of incorrect decoding a pixel to less than
0.014%. Most images could be expected to have fewer than 100 incorrect pixels.

When working with codes of long length and large size, it is no longer at all obvious
how to decode a received word. For example, suppose you receive the word (0, 0, 1, 1, 1,
0, . . . , 1, 0, 1, 1), represented by

18
 It is far from obvious which codeword in the Mariner 9 code it is nearest to. In fact
the received word differs from the bottom row in the matrix above in 7 positions, and
from all other rows in at least 11 positions, so would be decoded as (0, 1, 1, 0, 1, 0 . .
. , 1, 0, 0, 1). (And then this codeword would be converted back into the corresponding
shade of grey.)
There is a very elegant decoding algorithm for the Mariner 9 code, based on the Discrete
Fourier Transform. Critically, this algorithm was easy to implement on the relatively
primitive computers available to NASA in 1971. See Van Lint’s survey article for an
outline of how this was done. Finding fast and accurate decoders for large codes, such
as Hadamard codes and the Reed–Solomon codes used on compact discs, is a central
problem in coding theory and has motivated much work in the subject.

————-

19
Chapter 3

Hamming Distance and Error

Detection and Correction

3.1 Hamming Distance and Nearest Neighbour De-

coding
This section introduces the concept of Hamming distance and explains how it helps in de-
coding by finding the closest codeword to a received word. It also discusses how Hamming
distance is used to determine a code’s ability to detect and correct errors, and explores
different methods to calculate this capability.

Definition 3.1.1. Let A be an alphabet. Let u, v ∈ An be words of length n. The

Hamming distance between u and v, denoted d(u, v), is the number of positions in which
u and v are different.
In mathematical notation, d(u, v) = |i ∈ 1, 2, . . . , n : ui ̸= vi |.

Example 3.1.2. Let, d(0011, 1101) = 3 of length 4, Since the words 0011 and 1101
differ in their first three positions, and are the same in their final position. Working
with words over the alphabet A, B, C, . . . , X, Y, Z we have d(T ALE, T AKE) = 1 and
d(T ALE, T ILT ) = 2.

Problem 3.1.1: Check that d(1010, 1001) = 2. Find the number of binary words v of

20
length 4 such that d(1010, v) = r for each r ∈ 0, 1, 2, 3, 4. Do you recognize the sequence
you get?
Solution : Let’s calculate this for each value of r:
• For r = 0 :

d(1010, v) = 1 means v is identical to 1010

therefore, v = 1010

• For r = 1 :

d(1010, v) = 1 means v is differs from 1010 in exactly one position.

therefore, v = 0010, 1110, 1000, 1011.

• For r = 2 :

d(1010, v) = 1 means v is differs from 1010 in exactly two position.

therefore, v = 0110, 0000, 0011, 1100, 1111, 1001.

• For r = 3 :

d(1010, v) = 1 means v is differs from 1010 in exactly three position.

therefore, v = 1101, 0001, 0111, 0100,.

• For r = 4 :

d(1010, v) = 1 means v is differs from 1010 in exactly four position.

therefore, v = 0101.

The sequence of numbers obtained for r = 0, 1, 2, 3, 4 is 1, 4, 6, 4, 1.Yes, the sequence

1, 4, 6, 4, 1 is recognizable.

21
Theorem 3.1.3. Let A be a q − ary alphabet and let u, v, w be words over A of length
n.

(i) d(u, v) = 0 if and ony if u = v;

(ii) d(u, v) = d(v, u);

(iii) d(u, w) ≤ d(u, v) + d(v, w).

Proof(ii): The definition of Hamming distance is symmetric if :

d(u, v) = |i :̸= ui ̸= vi | = |i :̸= vi ̸= ui | = d(v, u)

Problem 3.1.2: Find all English words v such that d(BIT E, v) = d(LOV E, v) = 2.
Check that the triangle inequality holds when u, v, w are BITE, WALL and LOVE, re-
spectively.
Solutionl: We have,
d(BIT E, v) = d(LOV E, v) = 2
We are to find v such that the Hamming Distance from both BITE and LOVE is exactly 2.

• For v = WORD,

d(BITE,WORD) = d(LOVE,WORD) = 2.

• For v = BAVE,

d(BITE,BAVE) = d(LOVE,BAVE) = 2.

• For v = BORE,

d(BITE,BORE) = d(LOVE,BORE) = 2.

22
 Now, we have to check for the triangle inequality when u, v, w are BITE, WALL, and
LOVE respectively.
By Hamming triangle inequality we have,

d(u, w) ≤ d(u, v) + d(v, w)

So, LHS: d(BITE,LOVE) = 4

RHS: d(BITE,WALL) + d(WALL,LOVE) = 2 + 3 = 5

Hence, Triangle inequality holds: 4 < 5

Definition 3.1.4: Let n ∈ N and let A be a q − ary alphabet with q ≥ 2. The repetation
code of length n over A has as its code words all words of length n of the form (s, s, . . . , s),
where s ∈ A. The binary code of length n is the repetation code of length n over the
binary alphabet {0,1}.

Note: If u and v are distinct codewords in a repetition code of length n then d(u, v) = n.

In Scheme 2 in Example 2.1.2, Alice and Bob used the binary repetition code of
length 3, with codewords 000, 111, Bob decoded a received word by its majority symbol,
so for example, 101 is decoded as 111 (meaning ‘Yes’). Equivalently, Bob decoded a
received word by choosing the closest codeword in the Hamming distance.

Definition 3.1.5. (Nearest neighbour decoding). Let C be a code. Suppose that a

codeword is sent through the channel and we receive the word v.To decide v using nearest
neighbour decoding look at all the codewords of C and pick the one that is nearest, in
Hamming distance to v. If there is no unique nearest codeword to v, then we say that
nearest neighbour decoding fails.
Note : The word ‘fail’ has a technical meaning in Definition 3.1.5. It does not mean
that the decoded codeword is not the send codeword.

23
Example 3.1.6. An internal review of the code in Example 2.4.2 has uncovered several
deficiencies. The new proposal uses a ternary repetition code of length 6 over the alphabet
{0, 1, 2}. The new encoder is

encoded as
‘Stand-down’ 000000

encoded as
‘Stay on your toes’ 111111

encoded as
‘Launch nukes’ 222222

Suppose ALICE sends ‘Stand-down’. If BOB receives 001102, then

d(001102, 000000) = 3, d(001102, 111111) = 4, d(001102, 222222) = 5, so under nearest
neighbour decoding, 001102 is decoded as 000000, which in turn BOB will decode as
‘Stand-down’.
Lastly, suppose four errors occur and the received message is 020222. The nearest code-
word is 222222, so BOB decodes it as ‘Launch nukes’. In this case, decoding technically
succeeds, but the result is likely not what ALICE intended.
This example illustrates that a ternary repetition code of length 6 can reliably correct up
to 2 errors. If more than 2 errors occur, reliable decoding cannot be guaranteed.
Example 3.1.6 shows that nearest neighbour decoding is only one step in the decoding
process. The diagram below extends our model of decoding to a two-step process. We
suppose that the codeword u is sent,the word v is received, and that nearest neighbour
decoding gives the codeword w, which is then decoded into the message.

noise nearest
w undo
u sent channel neighbour decodedmessage
encoder
v received decoder

The decoded message is correct if and only if w = u. This is the case if and only if u
is the unique nearest codeword to v, i.e. d(u, v) < d(u′ , v) for all codewords u′ .
Nearest neighbour decoding should seem like the intuitively obvious way to decode.
However, it is still interesting to give it a probabilistic justification. We shall do this in
the case of binary codes, using the binary symmetric channel defined in Definition 2.4.1.

24
Lemma 3.1.7. Let C be a binary code of length n used to communicate on a binary
symmetric channel with cross-over probability p. Suppose that the codeword u ∈ C is
sent. If v is a word of length n, then the probability that v is received pd (u, v)(1−p)n−d(u,v) .

In symbols, we write P[v received | u sent] = pd(u, v)(1 − p)n−d(u,v) .

Example 3.1.8. If C is the binary repetition code of length 3, then according to Lemma
3.1.8,

P[001 received | 111 sent] = p2 (1 − p)

P[001 received | 111 sent] = p3 .

The above equation is agree with the calculations in Example 2.1.2.

Example 3.1.9: (Parity check codes). Let n ∈ N, and let C be the set of all binary
words of length n. Now, make a new code Cext by adding one extra bit to each word in
C, so that the total number of 1s in each word becomes even.
For example, if n = 4, then C has all 16 binary words of length 4. The new code Cext
will have words of length 5, and still 16 words total. The codewords in Cext look like:

00000, 00011, 00101, 00110, ..., 11101, 11110

Suppose a codeword u ∈ Cext is sent through a channel, and the received word is v.
If one bit is changed (so d(u, v) = 1), then v will have an odd number of 1s. This means
v∈
/ Cext , so we know an error has happened.

Problem 3.1.3: How would you use the length 5 code Cext to encode a number between
0 and 15? Try to specify an encoding algorithm that is easy to perform in practice!

Solution: We have,

ˆ The length of the binary code Cext is 5 .

ˆ We want to encode numbers from 0 to 15.

25
 Since 24 = 16, each number 0 to 15 can be represented in 4 bits. We need to expand
this to 5 bits.
Steps of Parity Encoding Methods:

(1) Convert the number into a 4-bit binary string.

• Example : 0101

(2) Count the number of 1’s in this 4-bit string.

(3) Add a parity bit to ensure the total number of 1’s is even:

• If 1’s count is even −→ parity bit = 0

• If 1’s count is odd −→ parity bit = 1

(4) Place the parity bit at the beginning to form a 5-bit codeword. then the code
becomes 00101 .

Decimal 4-bit Binary No. of 1’s Parity Bit 5-bit Codeword

1 0001 1 1 10001
2 0010 1 1 10010
3 0011 2 0 00011
4 0100 1 1 10100
5 0101 2 0 00101
.. .. .. .. ..
. . . . .
15 1111 4 0 01111

Table 3.1: Encoding numbers 1 to 15 using 5-bit parity code

Example 3.1.10 (ISBN-10 code). All recent books have an International Standard
Book Number (ISBN), given by the publisher. The system changed in 2007 due to
limited number combinations. We will use the older ISBN-10 system here, which is more
interesting mathematically.
In this system, each book gets a 10-digit code using the alphabet {0, 1, 2, . . . , 9, X}.
For example, The book mention in the Reference(Coding and Information Theory.
Richard W. Hamming, Prentice-Hall, 1980.) has ISBN: 0-131-39139-9
Explanation of parts:

ˆ 0 is the country code

ˆ 131 is the publisher code

26
 ˆ 39139 is the item number

ˆ 9 is the check digit

The hyphens are just for readability; they are not part of the code.
The check digit is chosen so that:

10
X
(11 − j)uj = 10u1 + 9u2 + · · · + 2u9 + u10 ≡ 0 (mod 11)
j=1

This ensures the code is valid.

Sometimes, the check digit may need to be 10. In that case, we use X instead of 10
(X is never used in the first 9 digits of the ISBN).
We say that a 10-digit sequence u1 u2 . . . u10 is an ISBN if it satisfies the check con-
dition above—regardless of whether it was actually assigned to a book.
Lemma 3.1.11. If one single error is made when writing an ISBN, the result will not
be a valid ISBN.
The ISBN system can also detect if two adjacent digits are swapped, a common
mistake. However, it does not detect all errors, like swapping two digits that are not
next to each other.
For example: Starting with 0000000000, if we swap two digits to get 1000000001,
it’s still a valid ISBN.

27
3.2 t-Error Detecting and t-Error Correcting Codes
Definition 3.2.1 : Let C be a code of lenght n over an alphabet A and let t ∈ N. Then
C is :-

ˆ t-error detecting if whenever u ∈ C is a codeword, and v is a word of length n over

A such that v ̸= u and d(u, v) ≤ t, then v ∈
/ C.

ˆ t-error correcting if whenever u ∈ C is a codeword, and v is decoded to u using

nearest neighbour decoding.

Equivalently, a code C is t-error detecting if whenever a codeword is sent, and be-

tween 1 and t error occur, the received word is not a codeword. So the receiver will
know something has gone wrong in the channel.

Remarks:

1. Nearest neighbour decoding fails if there’s more than one closest codeword to a
word. So, a code C is t-error correcting if and only if for every word v within
distance t of a codeword u ∈ C, we have:

d(u, v) < d(u′ , v) for all u′ ∈ C with u′ ̸= u

This gives a way to define t-error correcting without mentioning decoding directly.

2. It might seem strange to call a code ”t-error correcting” since the decoder (human
or machine) does the correcting. But it’s a useful term because the same code can
work with different decoders. A code that is t-error correcting can correct up to t
errors, assuming nearest neighbour decoding is used.

3. In both definitions, we use d(u, v) ≤ t, meaning v differs from u in at most t

positions. So if a code is t-error detecting, it’s also s-error detecting for any s < t.
Similarly, if a code is t-error correcting, it’s also s-error correcting for all s < t.

However, if we defined things using exactly t changes instead of at most t, then

some codes could be 2-error detecting but not 1-error detecting.

28
 This would be confusing in practice and make theorems longer and more compli-
cated.

Lemma 3.2.2. Let n ∈ N. Let C be the repetition code of length n over a q-ary alphabet
A, where q ≥ 2.

(i) C is (n − 1)-error detecting but not n-error detecting.

(ii) If n = 2m + 1, then C is m-error correcting but not (m + 1)-error correcting.

(iii) If n = 2m, then C is (m − 1)-error correcting but not m-error correcting.

(i) C is (n − 1)-error detecting but not n-error detecting.

Proof: In a repetition code, each codeword is of the form (x, x, . . . , x) repeated n

times for some x ∈ A.
If at most n − 1 symbols are altered, the resulting word cannot be a valid codeword,
since a valid codeword has all symbols equal. Hence, such errors can be detected.
However, if all n symbols are changed to the same wrong value y ̸= x, the received
word is (y, y, . . . , y), which is a valid codeword. Thus, the error goes undetected.
Therefore, C detects up to (n − 1) errors, but not n errors.

(ii) If n = 2m + 1, then C is m-error correcting but not (m + 1)-error correcting.

Proof: Suppose the transmitted codeword is (x, x, . . . , x).

If at most m errors occur, then at least m + 1 symbols remain correct. Since
m + 1 > m, the correct symbol x appears more frequently than any other. Majority
decoding will correctly recover x.
However, if m + 1 symbols are altered to some y ̸= x, then y appears m + 1 times
while x appears only m times. In this case, majority decoding will wrongly decode
the word as y.
Therefore, C is m-error correcting but not (m + 1)-error correcting.

(iii) If n = 2m, then C is (m − 1)-error correcting but not m-error correcting.

Proof: If at most m − 1 errors occur, then at least m + 1 correct symbols remain.

The correct symbol appears in the majority and can be identified.

29
 If exactly m errors occur, then m symbols are correct and m are in error. In this
case, there is a tie between two symbols, and the decoder cannot determine the
original symbol with certainty.
Hence, C can correct up to (m − 1) errors, but not m errors.

Lemma 3.2.3. Let n ∈ N and let Cext be the binary parity check code of length n + 1
defined in Example 3.1.9. Then Cext is 1-error detecting but not 2-error detecting. It is
not 1-error correcting.
Proof : (i) 1-error detecting: In Example 3.1.9, each codeword has an even number of
1s. If a single bit is flipped during transmission, the number of 1s in the received word
becomes odd. Hence, the received word cannot belong to Cext , and the error is detected.
Thus, Cext is 1-error detecting.
(ii) Not 2-error detecting: If two bits are flipped, the number of 1s remains even, so
the received word may still lie in Cext . This makes the error undetectable in such cases.
Therefore, Cext is not 2-error detecting.
(iii) Not 1-error correcting: Error correction requires identifying the original code-
word from a corrupted one. Since Cext only checks parity (even/odd number of 1s), it
does not give information about the position of the error. Thus, Cext is not 1-error cor-
recting.

Lemma 3.2.4. The ISBN code is 1-error detecting but not 2-error detecting. It is not
even 1-error correcting.
Proof : (i) 1-error detecting: The ISBN code uses a modulo 11 checksum condition to
validate the number. If a single digit is changed, the checksum no longer holds, so the
error is detected. Therefore, the ISBN code is 1-error detecting.
(ii) Not 2-error detecting: Some double-digit errors can cancel each other out in the
checksum calculation, making the incorrect ISBN still satisfy the checksum. Hence, not
all 2-digit errors are detected. So the ISBN code is not 2-error detecting.
(iii) Not 1-error correcting: Although it can detect a single error, the ISBN code does
not provide enough information to identify which digit is wrong or what the correct digit
should be. So it is not 1-error correcting.

30
3.3 Minimum Distance and Hamming Balls
Definition 3.3.1. Let C be a code. The minimum distance of C, denoted d(C), is
defined by d(C) = min{d(u, w) : u, w ∈ C, u ∈
/ w}.

Example 3.3.2. Let C be the binary code of length 3 with codewords

C = {001, 1010, 111}

Then d(u, w) = 2 for all distinct u and w in C, so d(C) = 2. If we adjoin 000 as

another codeword then the minimum distance goes down to 1 since d(000,001) = 1.

Example 3.3.3. Let C be the binary code of length 5 with codewords

C = {00000, 11100, 00111, 11011}

Now we compute the Hamming distance d(u, w) between all distinct pairs of code-
words:

d(00000, 11100) = 3
d(00000, 00111) = 3
d(00000, 11011) = 4
d(11100, 00111) = 4
d(11100, 11011) = 3
d(00111, 11011) = 2.

Therefore, the minimum distance of the code is d(C) = 2.

Lemma 3.3.4. Let n ∈ N.

(i) The minimum distance of any length n repetition code is n.

(ii) The minimum distance of length n + 1 binary parity check codes Cext is 2.

(iii) The minimum distance of the square code is 3.

31
 (i) The minimum distance of any length n repetition code is n.

Proof: A binary repetition code of length n consists of two codewords:

C = {000
| {z . . . 1}}.
. . . 0}, |111{z
n n

The minimum distance d of a code is the minimum Hamming distance between any
two distinct codewords:
d = min d(x, y).
x̸=y∈C

Here, the only possible pair is the two codewords, and they differ in all n positions.
Hence,
d = n.

(ii) The minimum distance of the length n + 1 binary parity check code Cext
is 2.

Proof: The binary parity check code of length n + 1 is defined as:

Cext = x ∈ Fn+1

2 wt(x) ≡ 0 (mod 2) ,

where wt(x) denotes the Hamming weight of x. Thus, each codeword has an even
number of 1’s.

The smallest nonzero weight in such a code is 2 (e.g., 110 . . . 0). Codewords of
weight 1 are not allowed.

Since the minimum distance of a linear code equals the minimum weight of a nonzero
codeword, we conclude:
d = 2.

(iii) The minimum distance of the square code is 3.

Proof: The square code is a binary code constructed by arranging bits into an r × r
array such that each row and each column has even parity (i.e., an even number of
1s).

To determine the minimum distance, we consider the fewest number of bit positions
that can be changed to produce another valid codeword.

32
 Flipping 1 or 2 bits will violate the even-parity condition in at least one row or
column. However, flipping 3 specific bits forming an L-shape or triangle pattern
(e.g., two in one row and one in another row sharing a column) can preserve even
parity in all rows and columns.

Therefore, the smallest number of bits that can be changed to get another valid
codeword is 3. Hence,
d = 3.

Notation 3.3.5. If C is a code of length n, size M and minimum distance d, then C is

said to be a (n, M, d) − code.
Corollary 3.3.6. A code of minimum distance d is (d-1)-error detecting and [d − 1/2]-
error correcting.

The table below shows the maximum number of errors a code of small minimum dis-
tance can detect and correct.

d(C) error detection / correction

1 no detection possible
2 1-error detecting
3 2-error detecting / 1-error correcting
4 3-error detecting / 1-error correcting
5 4-error detecting / 2-error correcting

Definition 3.3.7. Let A be a q-ary alphabet and let u be a word of length n.The
Hamming ball of radius t about u is

Bt (u) = {v ∈ An : d(u, v) ≤ t}.

Theorem 3.3.8. Let C be a code with minimum distance d, and let t ∈ N. Then:

(i) C is t-error detecting if and only if t ≤ d − 1;

(ii) C is t-error correcting if and only if 2t ≤ d − 1.

Proof of (i): t-error detecting ⇔ t ≤ d − 1

Suppose C is t-error detecting. That means:

33
 ˆ For any codeword u ∈ C,

ˆ If v ̸= u and d(u, v) ≤ t, then v ∈

/ C.

Suppose, for contradiction, that t ≥ d. Then by the definition of minimum distance,

there exist distinct codewords u, w ∈ C such that

d(u, w) = d ≤ t.

But this implies that w ∈ C and d(u, w) ≤ t, which violates the definition of t-error
detection.
Hence, t < d, or t ≤ d − 1.

Suppose t ≤ d − 1. Let u ∈ C and suppose the received word v satisfies d(u, v) ≤ t.

Then for any other codeword w ∈ C, w ̸= u, we have

d(u, w) ≥ d > t ≥ d(u, v).

So v ∈
/ C, meaning the error is detected. Thus, C is t-error detecting.

Proof of (ii): t-error correcting ⇔ 2t ≤ d − 1

Suppose C is t-error correcting. Assume for contradiction that 2t ≥ d. Then there

exist u, w ∈ C, u ̸= w, such that

d(u, w) = d ≤ 2t.

Now consider a word v such that

d(u, v) ≤ t and d(w, v) ≤ t.

By the triangle inequality:

d(u, w) ≤ d(u, v) + d(v, w) ≤ 2t.

34
So both u and w are within distance t of v, and nearest neighbour decoding would not be
able to uniquely decode v. This contradicts the assumption that C is t-error correcting.
Hence, 2t < d, or 2t ≤ d − 1.

Suppose 2t ≤ d − 1. Let u ∈ C be the sent codeword and let v be the received word
with d(u, v) ≤ t. For any other codeword w ∈ C, w ̸= u, we have:

d(u, w) ≥ d ≥ 2t + 1.

By the triangle inequality:

d(w, v) ≥ d(u, w) − d(u, v) ≥ (2t + 1) − t = t + 1 > t.

So all other codewords w are farther from v than u is. Hence, nearest neighbour decoding
correctly decodes v to u, and C is t-error correcting.
An equivalent definition is that Bt (u) consists of all words that can be obtained from
u by changing up to t of its positions. The diagram below shows the Hamming ball of
radius 1 about 000.

Hamming Ball of radius 1 about 000

35
Example 3.3.9. The Hamming balls about the binary word 0000 are

B0 (0000) = {0000}

B1 (0000) = {0000, 1000, 0100, 0010, 0001}

B2 (0000) = B1 (0000) ∪ {1100, 1010, 1001, 0110, 0101, 0011}

B3 (0000) = B2 (0000) ∪ {1110, 1101, 1011, 0111}

and B4 (0000) is the set of all binary words of length 4.

(ii) If u = 1111, then

B0 (1111) = {1111}

B1 (1111) = {1111, 0111, 1011, 1101, 1110}

B2 (1111) = B1 (1111) ∪ {0011, 0101, 0110, 1001, 1010, 1100}

Also, B3 (1111) consists of all binary words of length 4 except 0000, and B4 (1111) is the
set of all binary words of length 4.

Example 3.3.10. The Hamming balls about the binary word 00000 are

B0 (00000) = {00000}

B1 (00000) = {00000, 10000, 01000, 00100, 00010, 00001}

B2 (00000) = B1 (00000) ∪ {11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011}

B3 (00000) = B2 (00000) ∪ {11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111}

and B5 (00000) is the set of all binary words of length 5.

(ii) If u = 10101, then

B0 (10101) = {10101}

B1 (10101) = {10101, 00101, 11101, 10001, 10111, 10100}

B2 (10101) = B1 (10101) ∪ {00001, 01101, 11001, 00111, 00100, 10011, 10000, 11111, 11100, 10110}

Also, B3 (10101) consists of all binary words of length 5 except 01010, and B5 (10101) is
the set of all binary words of length 5.

36
(iii) If u = 01010, then

B0 (01010) = {01010}

B1 (01010) = {01010, 11010, 00010, 01110, 01000, 01011}

B2 (01010) = B1 (01010) ∪ {10010, 00110, 00000, 11110, 11000, 11011, 01100, 01111, 00011, 01001}

Also, B3 (01010) consists of all binary words of length 5 except 10101, and B5 (01010) is
the set of all binary words of length 5.

Lemma 3.3.11. Let C be a code. If C is t-error correcting then for all distinct code-
words u, u′ ∈ C, the Hamming Balls Bt (u)andBt (u′ ) are disjoint.

Summary of Chapter 3. In Chapter 3, we introduced the formal definition of t-error

detecting and correcting codes (Definition 3.2.1). The examples in §2.1, along with the
results in Lemmas 3.2.3 and 3.2.4, support the reasonableness of this definition.
We then explored alternative perspectives on t-error correcting codes, particularly
through the concept of minimum distance (Definition 4.1) and the use of Hamming balls
(Lemma 4.9). These ideas are brought together in the following theorem.
Theorem 3.3.12. Let C be a code. The following are equivalent:

(a) C is t-error correcting;

(b) Nearest neighbour decoding always gives the sent codeword (without failing), pro-
vided at most t errors occur;

(c) If u ∈ C and d(u, v) ≤ t then d(u, v) < d(u′ , v) for all u′ ∈ C such that u′ ̸= u;

(d) If u, u′ ∈ C are distinct codewords, then the Hamming balls Bt (u) and Bt (u′ ) are
disjoint;

(e) The minimum distance of C is at least 2t + 1.

Proof : We show that all five statements are logically equivalent.

(a) ⇒ (b):
If C is t-error correcting, then any received word v with at most t errors from a codeword
u will be uniquely decoded to u. Hence, nearest neighbour decoding always succeeds.

37
 (b) ⇒ (c):
If nearest neighbour decoding gives the correct codeword whenever at most t errors occur,
then for any such v, the correct codeword u must be strictly closer to v than any other
codeword u′ ̸= u. Therefore, d(u, v) < d(u′ , v).
(c) ⇒ (a):
If d(u, v) ≤ t implies d(u, v) < d(u′ , v) for all u′ ̸= u, then u is the unique closest codeword
to v. Thus, the code is t-error correcting.
Hence, (a), (b), and (c) are equivalent.

(a) ⇒ (d):
If C is t-error correcting, then any word within distance t from u cannot also be within
distance t from any u′ ̸= u, otherwise decoding would be ambiguous. So the Hamming
balls Bt (u) and Bt (u′ ) are disjoint.
(d) ⇒ (e):
Suppose Bt (u) ∩ Bt (u′ ) = ∅ for all distinct u, u′ ∈ C. Then d(u, u′ ) > 2t, otherwise some
word v could be within distance t of both, leading to a contradiction. Therefore, the
minimum distance d(C) ≥ 2t + 1.
(e) ⇒ (a):
Assume d(C) ≥ 2t + 1. Let u ∈ C be sent and v be received with d(u, v) ≤ t. For any
u′ ̸= u,
d(u′ , v) ≥ d(u′ , u) − d(u, v) ≥ (2t + 1) − t = t + 1 > t.

So u is the unique codeword within distance t, hence C is t-error correcting.

Thus, all conditions (a) to (e) are equivalent.

38
Chapter 4

Main Coding Theory

One of the basic problems in coding theory is to make the code having maximum code
rate in order to have maximum efficiency. To acheive this, the codes over a given alphabet
should have

(1) small length;

(2) large size;

(3) high minimum distance.

This is called Main Coding Theory Problem. We aim to find (n, M, d)-codes with small
n, large M , and large d, i.e, for given n, d, what will be the maximum value of M , we
will try to study.

4.1 Bounds on size of a code

In this section, we try to find the upper bound on the value of size M of a code.

Lemma 4.1.1. For a binary word u of length n, the number of words in the Hamming
ball Bt (u) of radius t is:
t  
X n
k=0
k

39
Hamming’s Packing Bound
 d−1 
Theorem 4.1.2. Let C be a binary (n, M, d)-code. If e = 2
then:

2n
M ≤ Pe n


k=0 k

According to Theorem 3.3.8(ii), a code that can correct one error must have a mini-
mum distance of at least 3. From this, Hamming’s bound tells us that a binary code of
2n
length n that corrects single-bit errors can have no more than 1+n
codewords.
For example, if n = 7, we get:

27 128
M≤ = = 24 = 16.
1+7 8

If n = 5, then:
25 32
M≤ = ≈ 5.3.
1+5 6
Since we cannot have a fraction of a codeword, this bound is tightened to M ≤ 5.

The table below presents other values of Hamming’s bound for 1-error correcting
binary codes:

length n 3 4 5 6 7 8 9 10
bound on size M 2 3 5 9 16 28 51 93

It is very important to understand that although Hamming’s bound gives a necessary

condition for the existence of a binary code with a given length, size, and minimum
distance, it is not in general sufficient.

Problem 4.1.1. According to Hamming’s Packing Bound, the largest possible size of a
binary code of length 4 and minimum distance 3 is 3. Show that in fact the largest size
of a binary code of length 4 and minimum distance 3 is 2.
Solution: We are given that the minimum distance of the binary code is 3 and the length
of each codeword is 4. Hamming’s Packing Bound provides an upper bound of 3 on the
maximum number of such codewords.

40
 A minimum distance of 3 means that the Hamming distance between any two code-
words must be at least 3, i.e., they must differ in at least 3 positions.
Let us try constructing a binary code of length 4 and minimum distance 3 with 3
codewords.
Choose the first codeword as 0000. For the second codeword, we need a word that
differs from 0000 in at least 3 positions. For example, 1110 differs in the first three
positions, so we select it as the second codeword.
Next, we attempt to find a third codeword that has a Hamming distance of at least
3 from both 0000 and 1110. Consider 0111:

d(0111, 0000) = 3 (acceptable)

d(0111, 1110) = 2 (not acceptable)

Other options like 0011, 1100, 1010, 1001, etc., also fail to satisfy the condition with
both codewords. Therefore, no third codeword can be added without violating the mini-
mum distance condition.
Thus, although Hamming’s bound allows for up to 3 codewords, in reality, only 2
codewords can satisfy the required minimum distance of 3.
This shows that Hamming’s bound is a necessary condition but not sufficient in
general.

Gilbert–Varshamov Bound

We know that the Hamming Packing Bound (Theorem 4.1.4), written using the A2 (n, d)
notation, is:
2n
A2 (n, d) ≤ Pe n


k=0 k

where e = ⌊(d − 1)/2⌋. In the proof, we showed that if C is a binary (n, M, d)-code, then
the Hamming balls of radius e around the codewords in C do not overlap.
A similar idea using Hamming balls of radius d − 1 gives a lower bound on A2 (n, d).
The idea is to build a code with minimum distance d in a simple way: keep adding new
codewords until the Hamming balls of radius d − 1 around them cover all of {0, 1}n . This

41
means that every word is at most distance d − 1 from some codeword.

Theorem 4.1.3 (Gilbert–Varshamov Bound). If n, d ∈ N then,

2n
A2 (n, d) ≥ Pd−1 n


k=0 k

Singleton Bound

Theorem 4.1.4 . If C be a q-ary code of length n and minimum distance d then

|C| ≤ q n−d+1 . Hence Aq (n, d) ≤ q n−d+1
Remarks: We make the following remarks on Theorem 4..4.

(1) If n = 4 and d = 3 then the Singleton bound gives Aq (4, 3) ≤ q 4−3+1 .The codes
constructed by MOLs achieve the bound.So there is a pair of MOLs of order q if
and only if Aq (4, 3) = q 2 .

(2) The Reed–Solomon codes are known to achieve the Singleton bound. They show
that Aq (n, d) = q n−d+1 whenever q is a prime power and q ≥ n.

(3) The special case of the Singleton bound when d = n is

Aq (n, n) ≤ q.

Definition 4.1.5. Let q ≥ 2 and let n ∈ N, d ∈ N be such that n ≥ d. We denote

by Aq (n, d) the largest size of a code of length n and minimum distance d over a q-ary
alphabet.

Theorem 4.1.6 (Plotkin Bound). Let n, d ∈ N such that 2d > n. Then the maximum
number of codewords in a binary code of length n and minimum distance d, denoted by
A2 (n, d), satisfies:
2d
A2 (n, d) ≤ .
2d − n
This gives an upper bound on how large a binary code can be when the minimum
distance is relatively large compared to the length.

42
Example 4.1.7. Let n = 8 and d = 5. Since 2d = 10 > 8 = n, the condition of the
Plotkin bound is satisfied. Applying the bound:

2·5 10
A2 (8, 5) ≤ = = 5.
2·5−8 2

Therefore, any binary code of length 8 and minimum distance 5 can have at most 5
codewords.
However, we know that:
A2 (8, 5) = 4.

So although the Plotkin bound gives an upper limit of 5, the actual maximum number
of codewords is 4. This shows that the Plotkin bound is close to the best possible result
in this case.
In some cases, the Plotkin bound is sharp, meaning the inequality becomes an equality
and the bound exactly matches the true maximum size of the code.

Problem 4.1.2: Use the Plotkin bound to prove that A2 (9, 6) = 4.

Solution: We use the Plotkin bound, which states that if 2d > n, then

2d
A2 (n, d) ≤ .
2d − n

In this case, we are given n = 9 and d = 6. Since 2d = 12 > 9 = n, the condition holds,
so we can apply the bound:

2·6 12
A2 (9, 6) ≤ = = 4.
2·6−9 3

Thus,
A2 (9, 6) ≤ 4.

Next, we construct a binary code of length 9, minimum distance 6, and 4 codewords:

43
 C1 = 000000000

C2 = 111111000

C3 = 000111111

C4 = 111000111.

We now compute all pairwise Hamming distances:

d(C1 , C2 ) = 6, d(C1 , C3 ) = 6, d(C1 , C4 ) = 6,

d(C2 , C3 ) = 6, d(C2 , C4 ) = 6, d(C3 , C4 ) = 6.

Since all distances are at least 6, this is a valid code with 4 codewords. Therefore,

A2 (9, 6) ≥ 4.

Combining both results, we conclude:

A2 (9, 6) = 4

Corollary 4.1.8. If d ∈ N then,

A2 (2d, d) ≤ 4d

If there is a Hadamard matrix of order 2d then

A2 (2d, d) = 4d.

It is quite esy to show that if there is Hadamard matrix of order n then either n = 1, or
n = 2 or n is divisible by 4.
There is also a related ‘asymptotic’ Plotkin bound, which states that A2 (n, d) ≤ 2n−2d+1n
for all n and d.

44
 Table: Values of A2 (n, d)

d A2 (2, d) A2 (3, d) A2 (4, d) A2 (5, d) A2 (6, d) A2 (7, d) A2 (8, d)

1 4 8 16 32 64 128 256
2 2 4 8 16 32 64 128
3 2 2 4 8 16 20
4 2 2 4 8 16
5 2 2 2 4
6 2 2 2
7 2 2
8 2

The values of A2 (n, d)) are often powers of 2 because many good codes are linear, and all
linear binary codes have size a power of 2. But A2 (n, d) is not always a power of 2. For
example,A2 (8, 3) = 20; equivalently (by Theorem 3.3.8) the largest 1-error correcting of
length 8 has 20 codewords.
Lemma 4.1.9. Let q ≥ 2 and let n ∈ N Then:

(i) Aq (n, 1) = q n

(ii) Aq (n, n) = q

Proof:
(i) Here minimum distance 1 implies that no two codewords in the code can be iden-
tical. That is, any two distinct codewords must differ in at least one position. Therefore,
we are allowed to use all possible q-ary strings of length n as codewords, as all of them
are distinct and differ in at least one coordinate. The total number of such strings is q n .
Hence, we have
Aq (n, 1) = q n .

(ii) Here minimum distance n implies that any two codewords must differ in all n
positions. That is, for any two codewords x = (x1 , x2 , . . . , xn ) and y = (y1 , y2 , . . . , yn ),
we must have xi ̸= yi for all i = 1, 2, . . . , n.
This condition places a strong restriction on the number of codewords we can have.
If we view the code as a set of rows in a table with n columns, then in each column, no

45
symbol can be repeated. Since the alphabet has only q symbols, we can have at most q
distinct entries in any column. Therefore, the number of such codewords is at most q.
To show that this bound is tight, we construct q codewords such that each pair
differs in all positions. One such construction is the set of all cyclic shifts of the vector
(0, 1, 2, . . . , q − 1). These codewords differ in all coordinates and hence have minimum
distance n. Thus, we have
Aq (n, n) = q.

4.2 Equivalent Codes

Definition 4.2.1 Let C and C ′ be codes over a q-ary alphabet A. We say that C and C ′
are equivalent if one can be obtained from the other by repeatedly applying the following
two operations to all the codewords:

(a) relabelling the symbols appearing in a fixed position;

(b) shuffling the positions wihin each codeword.

Problem 4.2.1. Are the codes C = {0000, 1100, 1111} and C ′ = {0000, 1100, 0011}
equivalent?
Solution: We know two codes over a q-ary alphabet are said to be equivalent if one can
be obtained from the other by applying a sequence of the following operations:

(a) Relabelling the symbols in a fixed position (i.e., applying a permutation of the
alphabet in one coordinate).

(b) Shuffling (permuting) the positions within each codeword.

Here, Both codes are binary, of length n = 4, and size M = 3.

Let us compute their minimum distance.

ˆ For C = {0000, 1100, 1111}:

d(0000, 1100) = 2,

d(0000, 1111) = 4,

d(1100, 1111) = 2.

So, the minimum distance of C is d(C) = 2.

46
 ˆ For C ′ = {0000, 1100, 0011}:

d(0000, 1100) = 2,

d(0000, 0011) = 2,

d(1100, 0011) = 4.

So, the minimum distance of C ′ is also d(C ′ ) = 2.

Applying relabelling in C ′ such that position

Let us try to transform the codeword 1111 (in C) into 0011 (in C ′ ) using the allowed
operations.
We attempt a relabelling of symbols:

ˆ Suppose we try flipping 1 → 0 in positions 1 and 2.

ˆ Then, 1111 becomes 0011.

However, apply this same relabelling to the rest of the codewords in C:

ˆ 0000 remains 0000,

ˆ 1100 becomes 0000,

So, we now have duplicate codewords: {0000, 0000, 0011}.

The relabelling causes a loss of uniqueness in the code. Also, no permutation of
positions alone can transform C into C ′ . Hence:

The codes C and C ′ are not equivalent.

Lemma 4.2.2. If u and w are codewords in a code C, and u′ and w′ are the corresponding
codewords in an equivalent code C ′ obtained by relabelling and/or shuffling positions then
d(u, w) = d(u, w′ ).
Proof:
Case 1: Shuffling of Positions
Let π be a permutation of coordinate positions. Then for any word x = (x1 , x2 , . . . , xn ),
define:
x′ = π(x) = (xπ(1) , xπ(2) , . . . , xπ(n) )

47
 Now consider two codewords u, w ∈ C, and their permuted versions u′ = π(u), w′ =
π(w).
The Hamming distance between u and w is:

d(u, w) = #{i | ui ̸= wi }

After permutation, the set of positions where u′ and w′ differ is:

{j | uπ(j) ̸= wπ(j) }

This is simply a renaming of the index set — so the number of differing positions
stays the same.So,

⇒ d(u′ , w′ ) = d(u, w)

Case 2: Relabelling symbols in a fixed position

Now suppose we fix position i, and apply a permutation σ of the alphabet A to all
codewords in that coordinate:

x′i = σ(xi ), for all x ∈ C

This operation does not change whether ui = wi , because:

σ(ui ) = σ(wi ) ⇐⇒ ui = wi

So the number of positions where u and w differ is the same as for u′ and w′ .Thus

⇒ d(u′ , w′ ) = d(u, w)

Since both types of allowed transformations — shuffling positions and relabelling in

fixed coordinates — preserve the number of differing positions, the Hamming distance
between codewords is preserved under code equivalence.

d(u, w) = d(u′ , w′ )

48
Problem 4.2.2: Show that given four binary codes are equivalent

ˆ C = {0000, 1100, 1010, 0110}

ˆ C ′ = {1010, 0110, 0011, 1111}

ˆ D = {0000, 1100, 0011, 1111}

ˆ E = {1000, 0100, 0010, 0001}.

Proof : The minimum distance of the given four codes is 2.

First we show that C and C ′ are equivalent :
Applying shuffling positions in C. Now swap position 1 and 3 , 2 and 4 such that (3,4,1,2)
:

ˆ 0000 −→ 0000

ˆ 1100 −→ 0011

ˆ 1010 −→ 0110

ˆ 0110 −→ 1010.

Therefore, C becomes : C = {0000, 0011, 0110, 1010}

Now, Applying relabelling in C ′ such that position 1 and 3 flip bits :

ˆ 1010 −→ 0000

ˆ 0110 −→ 1100

ˆ 0011 −→ 1001

ˆ 1111 −→ 0101

So, C ′ becomes C ′ = {0000, 1100, 1001, 0101}

Again suffling position of new code of C ′ , swap position 1 and 3, 2 and 4.

ˆ 0000 −→ 0000

ˆ 1100 −→ 0011

ˆ 1001 −→ 0110

49
 ˆ 0101 −→ 1010.

Therefore, C ′ = {0000, 0011, 0110, 1010}

Hence C and C ′ are equivalent.

If we observe the other codewords. we fine that there are no codewords other than C
and C ′ that are equivalent.
For C and D this can be shown quite easily: there are codewords in D that are distance
4 apart, for example d(0000, 1111) = 4, but all codewords in C are distance 2 apart.

Lemma 4.2.4. A2 (5, 3) = 4

(Hamming Weight: The number of non-zero entry in any code(u) is called Ham-
ming Weight(wt) of the code and it’s denoted by wt(u) = r where r is the number of 1s.
For Example: u = 110110 ⇒ wt(u) = 4 )

Lemma 4.2.5. Let u and w be binary codewords of length n. Suppose that wt = r

and wt(w) = s. If r + s ≥ n then d(u, w) ≤ 2n − (r + s).

4.3 Codes from Mutually Orthogonal Latin Squares

(MOLS)
Definition 4.3.1.Let q ∈ N and let A be a q-ary alphabet.A Latin square with entries
from A is a q × q array in which every wow and column contains each symbol in A exactly
once. Then we say q is the order of the square.
Note: Since there are q symbols and each row and column has length q, it is equivalent
to require either

(i) Each row and column contains every symbol in A; or

(ii) No symbol appers twice in any row or column of A.

Example 4.3.2. A Latin square of order 4 over the alphabet {1, 2, 3, 4}, constructed

50
using the addition table for the integers modulo 4, is shown below.

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
2 3 4 1 3 4 1 2 4 1 2 3 2 3 4 1
3 4 1 2 2 1 4 3 3 4 1 2 4 1 2 3
4 1 2 3 4 3 2 1 2 3 4 1 3 4 1 2

Square 1 Square 2 Square 3 Square 4

Definition 4.3.3. Let X and Y be Latin squares over an alphabet A. We say that X
and Y are orthogonal if for each a, b ∈ A there exist unique i, j ∈ A such that Xi j = a
and Yi j = b.
Equivalently, X and Y are orthogonal if for all a, b ∈ A there is a unique position in
which X contains a and Y contains b. We shall abbreviate ’XandY a pair of mutually
orthogonal Latin Squares’, as ’X and Y are MOLs’.

Example 4.3.4. Let X and Y are the two MOLs over the alphabet {1, 2, 3, 4} are shown
below.
1 2 3 4 1 2 3 4
2 1 4 3 3 4 1 2
3 4 1 2 4 3 2 1
4 3 2 1 2 1 4 3

Square X Square Y

To show that these squares are orthogonal we form a new square whoseentries are
pairs of entries from the two squares,

11 22 33 44
23 14 41 32
34 43 12 21
42 31 24 13

Then check that each of the 16 pairs 11, 12, . . . , 44 appeares exactly once.

Problem 4.3.1: Show that is no pair of MOLs of order 2.

Solution: For order 2, the symbols are usually 0,1.
All possible Latin Squares of order 2 are :

51
 0 1 1 0
1 0 0 1

Square A Square B
Now create pairs of A and B (Ai j, Bi j),

01 10
10 01

A*B

We observed that, 01 and 10 occurs twice.

So, not all pairs are distinct therefore they are not orthogonal.

Lemma 4.3.5. Let q ≥ 3 be prime and let A = {0, 1, . . . , q − 1}. For i, j ∈ A let,

Xi j = (i + j) (mod q)
Yi j = (2i + j) (mod q)

Then X and Y are Mutually Orthogonal Latin squares.

Theorem 4.3.6. Let A be the alphabet {0,1,. . . ,q-1}. There is a pair of MOLs over A
of order q ⇐⇒ there exists a (4, q 2 , 3)-code over A.

Example 4.3.7. Let X and Y be the MOLs in Example 4.3.4. The corresponding code
has a codeword (i, j, Xi j, Yi j) for every i, j such that 0 ≤ i, j ≤ q − 1. So the codewords
are

0000 0111 0222 1012 1103 1230 1321

2023 2132 2210 2310 3031 3213 3302

Conversely given this list of codewords we can reconstruct X and Y .

52
4.4 Puncturing a Code and Hadamard Codes
Definition 4.4.1. . Let C be a code of length n ≥ 2 and minimum distance ≥ 2. Let
C ∗ be the code whose codewords are obtained by removing the final position from each
codeword in C. We say that C ∗ is obtained by puncturing C in its final position.

Note : Since C has minimum distance ≥ 2, it is impossible for two codewords in C to

become equal when their final position is removed.So C ∗ has the same size as C.

Example 4.4.2. Let C be the binary code whose codewords are all binary words of
length 4 with an even number of 1s. Let C ∗ be the code obtained by puncturing C in its
final position. Then

C = {0000, 1100, 1010, 0110, 1001, 0101, 0011, 1111}

C ∗ = {000, 110, 101, 011, 100, 010, 001, 111}

Thus C has minimum distance 2 and C ∗ has minimum distance 1.

Lemma 4.4.3. Let C be a code of length n and min. distance d. The punctured code C ∗
has length n − 1 and distance ≥ d − 1.

Hadamard codes are binary codes with a large minimum distance, which means they
can detect and correct many errors. Like the codes made from MOLs, Hadamard codes
have the largest possible size for a given length and minimum distance.
The Hadamard (32, 64, 16) code used in the 1971 Mariner 9 mission to Mars was dis-
cussed in Example 2.5.4. Since its minimum distance is 16, Theorem 3.3.8(ii) shows that
it can correct up to 7 errors, as mentioned in that example.

Hadamard codes are constructed using certain matrices with entries +1 and −1.

Definition 4.4.4.Let n ∈ N. A Hadamard matrix of order n is an n × n matrix H such

that each entry of H is either +1 or −1 and HH tr = nI.Here I is the n × n identity
matrix and H tr is the transpose matrix os H.

53
  
1 1
Example 4.4.5. If H =   then H is a Hadamard matrix of order 2.
1 −1
Two Hadamard matrices of order 4 are shown below; in these matrices we write + for
1 and − for −1.
   
+ + + + + + + +
   
− −   + − + − 
   
 + +
 ,  
 + − + −  − − 
   
 + +
   
+ − − + + − − +

Except for the 1 × 1 matrices (+1) and (−1), all Hadamard matrices have even order.
This result follows from the following lemma.
Lemma 4.4.6. Suppose H is a Hadamard matrix of order n where n ≥ 2. If i, k ∈
{1, 2, . . . , n} and i ̸= k, then row i and row k of H are equal in exactly n/2 positions.

Example 4.4.7. Hadamard Matrix of Order 8

 
+ + + + + + + +
 
+ + + + − − − −
 
 
 
+ + − − + + − −
 
 
 
+ + − − − − + +
 
 
 
+ − + − + − + −
 
 
 
+ − + − − + − +
 
 
 
+ − − + + − − +
 
 
 
+ − − + − + + −

Theorem 4.4.8. Suppose that H is a Hadamard matrix of order n ≥ 2. Let B be the

2n × n matrix defined by
 
H
B= 
−H

The rows of B are the codewords in a (n, 2n, n2 )-code over the alphabet {+,-}.
We say that any code given by the construction in Theorem 4.5.5 is a Hadamard code.
These codes can be converted into binary codes over the usual alphabet of bits 0,1 by
replacing each + with 0 and each with 1.

54
Summary of Chapter 4. In Chapter 4, we studied bounds like Hamming, Singleton,
Plotkin, and Gilbert–Varshamov on Aq (n, d), with equality for some optimal codes like
Reed–Solomon, MOLs codes, and Hadamard codes. The true value of A2 (n, d) remains
unknown in many cases and is a major open problem.

The Plotkin bound is stronger than the Hamming Packing Bound for d ≥ 320. For
most d there is a wide gap between the Gilbert–Varshamov lower bound and the mini-
mum of the Hamming and Plotkin upper bounds, and all we know is that A2 (1000, d) is
somewhere in between. Determining the true value of A2 (n, d) for large n and d is one of
the main open problems in coding theory.

1,000
Singleton bound
800 Hamming bound
Plotkin bound
bound on rate

Gilbert–Varshamov bound
600

400

200

0
0 200 400 600 800 1,000
minimum distance d

Comparison of Bounds for binary codes of length 1000

55
Conclusion

This internship on the topic: Controlling noise in communication has been a trans-
formative academic experience that bridged the gap between abstract mathematical the-
ory and real-world applications. Through the study of concepts like Hamming distance,
error detection and correction codes, Latin squares, Hadamard and Reed–Solomon codes,
and various mathematical bounds, I have gained a much deeper appreciation for the role
mathematics plays in ensuring the reliability of digital communication.
Beyond learning the theoretical framework, I explored practical systems such as QR
codes, ISBN verification, and space communication protocols, all of which use these
mathematical tools in impactful ways. These examples helped solidify my understanding
and sparked my curiosity about how mathematical thinking underpins modern technology.
Another highlight of this internship was learning to use LaTeX. Initially unfamiliar and
somewhat challenging, it soon became an essential skill that allowed me to produce well-
structured and professional scientific documents. I now feel more confident in my ability
to write technical reports, which will be beneficial in both academic and professional
settings.
Importantly, this internship has also changed the way I view mathematics itself—from
a purely theoretical subject to one with profound practical applications. It has inspired
me to pursue further studies in applied mathematics, especially in areas like information
theory, cryptography, and communication systems. I believe the problem-solving skills
and technical insights gained during this internship will guide me well in my future
academic journey.
In conclusion, this experience has not only enhanced my knowledge base but has also
contributed significantly to my personal and intellectual growth. I am grateful to Tezpur
University and Dr. Pankaj K. Das for providing this valuable opportunity.

56
References

(1) Richard W. Hamming, Coding and Information Theory. Prentice-Hall, 1980.

(2) M. Wildon, Error correcting codes-MT361/MT461/MT5461,

https://ma.rhul.ac.uk/ uvah099/Maths/Codes12/MT3612012Slides.pdf.

57