(32,64,16) Reed-Muller Code#
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:52.788877
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))
Mariner 4#
Mariner 4 was the first spaceship to photograph another planet, taking 22 complete photographs of Mars in 1965.
Each picture consisted of 40,000 = 200 x 200 pixels.
Each pixel was assigned a binary 6-tuple representing one of 64 brightness levels, from white (000000) to black (111111).
No code was used for error-correction, so a brightness level was encoded as itself, a 6-bit codeword, with 0 redundant bits.
Therefore, the total number of bits per picture was 240K.
The transmission rate was 8 and 1/3 bits per second.
Therefore, it took about 8 hours to transmit a single picture.
\( \begin{aligned} &(6,64,1)\text{-code} \\ C_{[64\times6]}&= \begin{cases} \end{cases} \end{aligned} \)
\( \begin{aligned} q&=2 \\ Z_q&=\{0,1\} \\ C_{[64\times6]} &\subseteq(F_2)^{6} \\ n&=6 \\ M&=64 \\ 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} \)
nrows =2e2
ncols =2e2
pixels=nrows*ncols
bits_per_pixel=6
bits_per_photo=bits_per_pixel*pixels
transmission_rate=8+(1/3)
print(f"{'Pixels = ':20}{int(pixels):<15,}")
print(f"{'x better = ':20}{pixels/40e3:<15,}")
print(f"{'Bits per photo = ':20}{int(bits_per_photo):<15,}{'picture size'}")
print(f"{'Bits per second = ':20}{transmission_rate:<15,.2f}{'transmission rate'}")
print(f"{'Hours = ':20}{bits_per_photo/transmission_rate/3600:<15,.2f}{'time to transmit 1 picture'}")
Pixels = 40,000
x better = 1.0
Bits per photo = 240,000 picture size
Bits per second = 8.33 transmission rate
Hours = 8.00 time to transmit 1 picture
q=2
n=6
print(f"{q**n:,}")
f=fqn(q,n)
f
64
{'000000',
'000001',
'000010',
'000011',
'000100',
'000101',
'000110',
'000111',
'001000',
'001001',
'001010',
'001011',
'001100',
'001101',
'001110',
'001111',
'010000',
'010001',
'010010',
'010011',
'010100',
'010101',
'010110',
'010111',
'011000',
'011001',
'011010',
'011011',
'011100',
'011101',
'011110',
'011111',
'100000',
'100001',
'100010',
'100011',
'100100',
'100101',
'100110',
'100111',
'101000',
'101001',
'101010',
'101011',
'101100',
'101101',
'101110',
'101111',
'110000',
'110001',
'110010',
'110011',
'110100',
'110101',
'110110',
'110111',
'111000',
'111001',
'111010',
'111011',
'111100',
'111101',
'111110',
'111111'}
Mariner 6,7,9#
Mariner 9 was the first spaceship to be put into orbit around Mars.
Each picture consisted of 582,400 = 700 x 832 pixels, a 15x improvement over Mariner 4.
Each pixel was assigned a binary 6-tuple representing one of 64 brightness levels, from white (000000) to black (111111).
The Reed-Muller code was used for error-correction, and so a brightness level was encoded as a 32-bit codeword with 26 redundant bits.
It is well suited to very noisy channels, and has a fast decoding algorithm.
The transmission rate was 16,200 bits per second.
nrows =700
ncols =832
pixels=nrows*ncols
bits_per_pixel=32
bits_per_photo=bits_per_pixel*pixels
transmission_rate=1.62e4
print(f"{'Pixels = ':20}{int(pixels):<15,}")
print(f"{'x better = ':20}{pixels/40e3:<15,}")
print(f"{'Bits per photo = ':20}{int(bits_per_photo):<15,}{'picture size'}")
print(f"{'Bits per second = ':20}{transmission_rate:<15,.2f}{'transmission rate'}")
print(f"{'Hours = ':20}{bits_per_photo/transmission_rate/3600:<15,.2f}{'time to transmit 1 picture'}")
Pixels = 582,400
x better = 14.56
Bits per photo = 18,636,800 picture size
Bits per second = 16,200.00 transmission rate
Hours = 0.32 time to transmit 1 picture
\( \begin{aligned} &(32,64,16)\text{-code} \\ C_{[64\times32]}&= \begin{cases} \end{cases} \end{aligned} \)
\( \begin{aligned} q&=2 \\ Z_q&=\{0,1\} \\ C_{[64\times32]} &\subseteq(F_2)^{32} \\ n&=32 \\ M&=64 \\ d(C)&=16 \\ d(C)&\ge16=(s=15)+1 &&\text{15-error detecting} \\ d(C)&\ge16=2(t=7.5)+1 &&\text{7-error correcting} \end{aligned} \)
q=2
n=32
print(f"{q**n:,}")
f=fqn(q,n,g=64)
f
4,294,967,296
{'00000000000000000000000000000000',
'00000000000000000000000000000001',
'00000000000000000000000000000010',
'00000000000000000000000000000011',
'00000000000000000000000000000100',
'00000000000000000000000000000101',
'00000000000000000000000000000110',
'00000000000000000000000000000111',
'00000000000000000000000000001000',
'00000000000000000000000000001001',
'00000000000000000000000000001010',
'00000000000000000000000000001011',
'00000000000000000000000000001100',
'00000000000000000000000000001101',
'00000000000000000000000000001110',
'00000000000000000000000000001111',
'00000000000000000000000000010000',
'00000000000000000000000000010001',
'00000000000000000000000000010010',
'00000000000000000000000000010011',
'00000000000000000000000000010100',
'00000000000000000000000000010101',
'00000000000000000000000000010110',
'00000000000000000000000000010111',
'00000000000000000000000000011000',
'00000000000000000000000000011001',
'00000000000000000000000000011010',
'00000000000000000000000000011011',
'00000000000000000000000000011100',
'00000000000000000000000000011101',
'00000000000000000000000000011110',
'00000000000000000000000000011111',
'00000000000000000000000000100000',
'00000000000000000000000000100001',
'00000000000000000000000000100010',
'00000000000000000000000000100011',
'00000000000000000000000000100100',
'00000000000000000000000000100101',
'00000000000000000000000000100110',
'00000000000000000000000000100111',
'00000000000000000000000000101000',
'00000000000000000000000000101001',
'00000000000000000000000000101010',
'00000000000000000000000000101011',
'00000000000000000000000000101100',
'00000000000000000000000000101101',
'00000000000000000000000000101110',
'00000000000000000000000000101111',
'00000000000000000000000000110000',
'00000000000000000000000000110001',
'00000000000000000000000000110010',
'00000000000000000000000000110011',
'00000000000000000000000000110100',
'00000000000000000000000000110101',
'00000000000000000000000000110110',
'00000000000000000000000000110111',
'00000000000000000000000000111000',
'00000000000000000000000000111001',
'00000000000000000000000000111010',
'00000000000000000000000000111011',
'00000000000000000000000000111100',
'00000000000000000000000000111101',
'00000000000000000000000000111110',
'00000000000000000000000000111111'}