Intro to binary codes C1, C2, C3#
Hill, Raymond. (1986). A First Course in Coding Theory. Oxford University Press: Oxford Applied Mathematics and Computing Science Series.
Programming Environment#
Show code cell source
import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
plt.style.use('ggplot');
plt.rcParams.update({'text.usetex' : True});
%matplotlib inline
from collections import defaultdict
from itertools import combinations,product
import itertools
from typing import Set
from IPython.display import display, Math
from datetime import datetime as d
import locale as l
import platform as p
import sys as s
pad = 20
print(f"{'Executed'.upper():<{pad}}: {d.now()}")
print()
print(f"{'Platform' :<{pad}}: "
f"{p.mac_ver()[0]} | "
f"{p.system()} | "
f"{p.release()} | "
f"{p.machine()}")
print(f"{'' :<{pad}}: {l.getpreferredencoding()}")
print()
print(f"{'Python' :<{pad}}: {s.version}")
print(f"{'' :<{pad}}: {s.version_info}")
print(f"{'' :<{pad}}: {p.python_implementation()}")
print()
print(f"{'Matplotlib' :<{pad}}: {mpl.__version__}")
print(f"{'NumPy' :<{pad}}: {np .__version__}")
EXECUTED : 2025-01-17 17:27:51.386243
Platform : 15.2 | Darwin | 24.2.0 | arm64
: UTF-8
Python : 3.11.11 | packaged by conda-forge | (main, Dec 5 2024, 14:21:42) [Clang 18.1.8 ]
: sys.version_info(major=3, minor=11, micro=11, releaselevel='final', serial=0)
: CPython
Matplotlib : 3.9.3
NumPy : 2.0.2
Show code cell source
def rc (q : int,
n : int) -> Set[str]:
"""Repetition Code
Generate a q-ary repetition block code of length n.
"""
S=set()
for i in range(q):
S.add(str(i)*n)
return S
def fqn (q : int,
n : int,
g : int = 0) -> Set[str]:
"""Construct a linear space of dimension n over a finite field of order q.
Parameters
==========
g : If the space is very large, opt for the first g elements of a generator object.
"""
if bool(g):
f=itertools.product(range(q),repeat=n)
return set(''.join(str(i) for i in next(f)) for _ in range(g))
else:
return {''.join(str(bit) for bit in word) for word in itertools.product(range(q),repeat=n)}
def qarycode_to_nbitstring (code={'3121','2101'},k=4):
"""Convert a q-ary code """
for n in code:
print(' '.join(format(int(i),f'0{k}b') for i in n))
def hd (a : str = '1001',
b : str = '0101') -> int:
"""HAMMING DISTANCE
Parameters
==========
x : str
y : str
Return
======
int
"""
assert len(a) == len(b), 'x and y must have the same length'
return sum(x!=y for x,y in zip(a,b))
def nbfmd (c : Set[str],
pr : bool = False) -> np.float16:
"""NAIVE BRUTE FORCE MINIMUM DISTANCE d(C)
Computes the pairwise Hamming distance for all codewords and returns the minimum value.
This is a naive (i.e., non vectorized) implementation using nested for loops.
Parameters
==========
c : code
pr : Print intermediate steps.
Returns
=======
d(C)
"""
# convert a set of string vectors to a 2D NumPy array of integers
c=np.array([list(codeword) for codeword in c],dtype=np.float16)
# intialize empty hamming distance matrix
hamming = np.empty([c.shape[0]]*2,dtype=np.float16)
for i,x in enumerate(c):
for j,y in enumerate(c):
hamming[i,j]=(x!=y).sum()
# the diagonal represents the Hamming distance of a codeword with itself, which is always 0.
np.fill_diagonal(hamming,np.inf)
if pr == True:
print(hamming)
return hamming.min().astype(np.int8)
def one_error_detecting (q : int,
code : Set[str],
p : bool = False) -> bool:
"""Verify that a code is one-error detecting.
No one-bit error equals a codeword.
"""
flag=True
alphabet=set(str(i) for i in range(q))
for codeword in code:
if p:
print()
print(f"{'orig cw : ':10}{codeword}")
for i in range(len(codeword)):
a,b,c=codeword[:i],codeword[i],codeword[i+1:]
symbols=alphabet-set(codeword[i])
for symbol in symbols:
cw=codeword[:i]+symbol+codeword[i+1:] # SINGLE ERROR
if cw in code:
flag=False
if p:
print(f"{'ERROR':10}{cw}")
else:
if p:
print(f"{'':10}{cw}")
return flag
# set(''.join(l for l in i) for i in itertools.product('10',repeat=3))
# set(''.join(l for l in i) for i in itertools.combinations_with_replacement('012',r=3))
# set(''.join(l for l in i) for i in itertools.combinations('01',r=2))
[EXAMPLE]
HQ and X have identical maps but only HQ knows the route by which X can avoid enemy territory and return to HQ safely.
HQ can transmit binary data to X and wishes to send the route \(\text{NNWNNWWSSWWNNNNWWN}\).
In this situation, reliability or transmission is more important than speed of transmission.
The most efficient code is
\( C_1= \begin{cases} 00&=\text{N}\\ 01&=\text{W}\\ 10&=\text{E}\\ 11&=\text{S}\\ \end{cases} \)
However, if one or more errors have occurred there is no way for X to know.
c1 ={'00','01','10','11'}
f22=fqn(2,2)
c1.issubset(f22)
True
Let’s add a redundant bit to each codeword to protect them against noise.
A less efficient but more reliable code than \(C_1\) is
\( C_2= \begin{cases} 000&=\text{N}\\ 011&=\text{W}\\ 101&=\text{E}\\ 110&=\text{S}\\ \end{cases} \)
A single error in the received vector cannot be a codeword and so \(C_2\) is single-error-detecting.
X can recognize whether a single error has occurred and seek retransmission.
c2 ={'000','011','101','110'}
f23=fqn(2,3)
c2.issubset(f23)
True
one_error_detecting(2,c2)
True
Suppose X can receive binary data from HQ but cannot seek retransmission.
A less efficient but more reliable code than \(C_2\) is
\( C_3= \begin{cases} 00000&=\text{N}\\ 01101&=\text{W}\\ 10110&=\text{E}\\ 11011&=\text{S}\\ \end{cases} \)
A single error in the received vector cannot be a codeword and so \(C_2\) is single-error-detecting.
X can recognize whether a single error has occurred and seek retransmission.
c3 ={'00000','01101','10110','11011'}
f25=fqn(2,5)
c3.issubset(f25)
True
one_error_detecting(2,c3,True)
orig cw : 00000
10000
01000
00100
00010
00001
orig cw : 01101
11101
00101
01001
01111
01100
orig cw : 10110
00110
11110
10010
10100
10111
orig cw : 11011
01011
10011
11111
11001
11010
True
C1#
\( \begin{aligned} &(2,4,1)\text{-code} \\ C_{1,[4\times2]}&= \begin{cases} 00&=\text{N}\\ 01&=\text{W}\\ 10&=\text{E}\\ 11&=\text{S}\\ \end{cases} \end{aligned} \)
\( \begin{aligned} q&=2 \\ Z_q&=\{0,1\} \\ C_{1} &\subseteq(F_2)^2 \\ n&=2 \\ M&=4 \\ d(C)&=1 \\ d(C)&\ge1=(s=0)+1 &&\text{zero-error detecting} \\ d(C)&\ge1=2(t=0)+1 &&\text{zero-error correcting} \end{aligned} \)
c1={'00','01','10','11'}
c1
{'00', '01', '10', '11'}
q=2
n=2
f1=fqn(q,n)
f1
{'00', '01', '10', '11'}
c1.issubset(f1)
True
dC1=nbfmd(c1,True)
dC1
[[inf 1. 1. 2.]
[ 1. inf 2. 1.]
[ 1. 2. inf 1.]
[ 2. 1. 1. inf]]
np.int8(1)
C2#
\( \begin{aligned} &(3,4,2)\text{-code} \\ C_{2,[4\times3]}&= \begin{cases} 000&=\text{N}\\ 011&=\text{W}\\ 101&=\text{E}\\ 110&=\text{S}\\ \end{cases} \end{aligned} \)
\( \begin{aligned} q&=2 \\ Z_q&=\{0,1\} \\ C_{2} &\subseteq(F_2)^3 \\ n&=3 \\ M&=4 \\ d(C)&=2 \\ d(C)&\ge2=(s=1)+1 &&\text{one-error detecting} \\ d(C)&\ge2=2(t=0.5)+1 &&\text{zero-error correcting} \end{aligned} \)
c2={'000','011','101','110'}
c2
{'000', '011', '101', '110'}
q=2
n=3
f2=fqn(q,n)
f2
{'000', '001', '010', '011', '100', '101', '110', '111'}
c2.issubset(f2)
True
dC2=nbfmd(c2,True)
dC2
[[inf 2. 2. 2.]
[ 2. inf 2. 2.]
[ 2. 2. inf 2.]
[ 2. 2. 2. inf]]
np.int8(2)
C3#
\( \begin{aligned} &(5,4,3)\text{-code} \\ C_{3,[4\times5]}&= \begin{cases} 00000&=\text{N}\\ 01101&=\text{W}\\ 10110&=\text{E}\\ 11011&=\text{S}\\ \end{cases} \end{aligned} \)
\( \begin{aligned} q&=2 \\ Z_q&=\{0,1\} \\ C_{3} &\subseteq(F_2)^5 \\ n&=5 \\ M&=4 \\ d(C)&=3 \\ d(C)&\ge3=(s=2)+1 &&\text{two-error detecting} \\ d(C)&\ge3=2(t=1)+1 &&\text{one-error correcting} \end{aligned} \)
c3={'00000','01101','10110','11011'}
c3
{'00000', '01101', '10110', '11011'}
q=2
n=5
f3=fqn(q,n)
f3
{'00000',
'00001',
'00010',
'00011',
'00100',
'00101',
'00110',
'00111',
'01000',
'01001',
'01010',
'01011',
'01100',
'01101',
'01110',
'01111',
'10000',
'10001',
'10010',
'10011',
'10100',
'10101',
'10110',
'10111',
'11000',
'11001',
'11010',
'11011',
'11100',
'11101',
'11110',
'11111'}
c3.issubset(f3)
True
dC3=nbfmd(c3,True)
dC3
[[inf 3. 3. 4.]
[ 3. inf 4. 3.]
[ 3. 4. inf 3.]
[ 4. 3. 3. inf]]
np.int8(3)
Equivalent codes
\( \begin{aligned} C= \begin{cases} 00100\\ 00011\\ 11111\\ 11000\\ \end{cases} \,\,\,\,\, \underset{p_3}{ \left( \begin{matrix} 0&1\\ \downarrow&\downarrow\\ 1&0\\ \end{matrix} \right) } \,\,\,\,\, C= \begin{cases} 00000\\ 00111\\ 11011\\ 11100\\ \end{cases} \,\,\,\,\, \left( \begin{matrix} p_2&p_4\\ \downarrow&\downarrow\\ p_4&p_2\\ \end{matrix} \right) \,\,\,\,\, C_3= \begin{cases} 00000\\ 01101\\ 11011\\ 10110\\ \end{cases} \end{aligned} \)