BSEDMATH 18 Abstract Algebra
BINARY LINEAR CODES
Behind every reliable digital message is a
piece of mathematics.
Prepared by: Roslit O. Mayormita
What are Binary Linear Codes?
A Binary Linear Code is a method of detecting and correcting errors in data
transmission using concepts from linear algebra and abstract algebra.
When data is sent through a channel (internet, satellite, etc.), errors can occur. Binary
linear codes help identify and sometimes correct these errors.
Binary Linear Codes use:
Binary numbers (0 and 1)
Vector spaces
Matrices
Modulo 2 arithmetic
The codewords form a vector subspace of
Where:
Z sub 2 = {0,1} with operations done modulo 2.
EXAMPLE:
a b a + b (mod 2)
0 0 0
0 1 1 So
1 + 1 = 0.
1 0 1
1 1 0
Key Concepts, Terms, and Definitions
1.. Binary Code
1
A binary code is a set of binary sequences.
Example: C = {000, 101, 110, 011}
2.. Codeword
2
Each element of the code is called a codeword.
Example: If C = {000, 101, 110}, then 000, 101, 110 are codewords.
Key Concepts, Terms, and Definitions
3.. Binary Linear Code
3
A binary linear code is a code that is a subspace of .
Meaning:
Contains the zero vector
Closed under vector addition
Closed under scalar multiplication
Example:
C = {000, 011, 101, 110}
Check closure:
011 + 101 = 110
→
Still inside the set linear code
Key Concepts, Terms, and Definitions
4.. Parameters of a Code
4
A binary linear code is written as:
[n, k]
where n = length of codeword
k = number of information bits
Example: [n, k]=[3, 2]
→
n = 3 each codeword has 3 bits
→
k = 2 2 bits are the original message
Key Concepts, Terms, and Definitions
5.. Generator Matrix (G)
5 (G )
A generator matrix G used to generate all possible codewords of a binary linear code.
Given:
This means the code is a [4,2] binary linear code because:
→
n=4 length of each codeword
→
k=2 number of message bits
The codeword is obtained using: c = uG
where:
u = message vector
G = generator matrix
c = codeword
All operations are done modulo 2 (binary arithmetic).
Key Concepts, Terms, and Definitions
6.. Parity Check Matrix (H)
6
Used in binary linear codes to detect errors in a received codeword.
The rule is:
Where:
H = Parity Check Matrix
c = Codeword
c^ = Transpose of the codeword
0 = Zero vector
Key Concepts, Terms, and Definitions
7.. Hamming Distance
7
is the number of positions where two binary strings are different.
In symbols:
d (x, y) = number of different positions between x and y
Example: We will use ASCII binary representation.
→
T 0 1 0 1 0 1 0 0
→
R 0 1 0 1 0 0 1 0
Hamming Distance = 2
d=2
Key Concepts, Terms, and Definitions
8.. Minimum Distance
8
The smallest distance between any two codewords.
It determines error detection ability.
Rules:
Detectable errors: d - 1
Correctable errors: t = ⌊ d - 1 / 2 ⌋
EXAMPLE: ASCII
Letter Binary Letter Binary
C 1000011 C 1000011
A 1000001 A 1000001
T 1010100 R 1010010
CAT - 01000011 01000001 01010100
CAR - 01000011 01000001 01010010
ITS TIME TO HAVE FUN!
1.. Is C = {000, 011, 101, 110} is a binary linear code? Why?
1
2. Find the Hamming distance between
2.
1 0 1 0 1
0 0 1 1 1
3. Find the detectable errors of
3.
C = {000, 011, 101, 110)
ASSESSMENT
Problem 1
Consider the binary code C = {000, 011, 101, 110}
a. Determine the length n of the codewords.
b. How many codewords are in C?
c. Find the minimum Hamming distance of the code.
d. Determine the maximum number of detectable errors.
Problem 2
Given the generator matrix [1 0 1 1]
[0 1 1 0]
a. Identify the values of n and k.
b. Determine the number of possible message vectors.
c. List all possible message vectors.
THANK YOU