The main coding theory problem

The main coding theory problem #

Programming Environment #

Show code cell source Hide code cell source

# %load imports.py
import numpy  as np
import pandas as pd

import matplotlib        as mpl
from   matplotlib.patches import Rectangle
import matplotlib.pyplot as plt
plt.style.use('ggplot');
plt.rcParams.update({'text.usetex' : True});
%matplotlib inline

from   collections import Counter,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__}")

#==================================================

def dec_to_bin_repr (a : int,
                     n : int) -> str:
  """Convert a decimal number [int] to a binary number of length n [str].
  
  Parameters
  ==========
  a : decimal number
  n : number of places

  Returns
  =======
  return the binary representation of an integer as a string to n positions
  """
  return format(a,f'0{n}b')
#print(dec_to_bin_repr(17,10))

def bin_repr_inv (a : int,
                  n : int) -> str:
  """Convert a decimal number [int] to the inverse of a binary number of length n [str].
  
  Parameters
  ==========
  a : decimal number
  n : number of places

  Returns
  =======
  return the inverse of the binary representation of an integer as a string to n positions
  """
  return format(a^(2**n-1),f'0{n}b')
#print(bin_repr_inv(17,10))

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))

def vadd (vecs : set[str],
          q    : int) -> str:
  """VECTOR SUM
  Takes a set of q-ary vectors and computes their sum mod q.
  """
  return ''.join((np.array(list(list(vec) for vec in vecs),dtype=np.int8).sum(axis=0)%q).astype(str))

def vmul (vecs : set[str],
          q    : int) -> str:
  """VECTOR PRODUCT
  Takes a set of q-ary vectors and computes their product mod q.
  """
  return ''.join((np.array(list(list(vec) for vec in vecs),dtype=np.int8).prod(axis=0)%q).astype(str))

def vw (v : str) -> int:
  """VECTOR WEIGHT"""
  c=Counter(v)
  if '0' in c.keys():
    c.pop('0')
  return c.total()

def overall_parity_check (code : set[str],
                          q    : int,
                          arr  : int = 0) -> np.ndarray:
  code=np.array(list(list(codeword) for codeword in sorted(code)),dtype=np.int8)
  code_as_array=np.concatenate([code,(code.sum(axis=1)%q).reshape((code.shape[0],1))],axis=1)
  if arr:
    return code_as_array
  else:
    return {''.join(codeword) for codeword in code_as_array.astype(str)}

EXECUTED            : 2024-05-21 15:46:17.642449

Platform            : 14.4.1 | Darwin | 23.4.0 | arm64
                    : UTF-8

Python              : 3.11.9 | packaged by conda-forge | (main, Apr 19 2024, 18:34:54) [Clang 16.0.6 ]
                    : sys.version_info(major=3, minor=11, micro=9, releaselevel='final', serial=0)
                    : CPython

Matplotlib          : 3.8.4
NumPy               : 1.26.4

The main coding theory problem #

A good \((n,M,d)\)-code has

(i) small \(n\) for fast transmission of messages

(ii) large \(M\) to enable transmission of a wide variety of messages

(iii) large \(d\) to correct many errors

The main coding theory problem is to optimize one of the parameters \(n,M,d\) for given values of the other two.

Usually, we want to find the largest code of a given length \(n\) and given minimum distance \(d\).

\(A_q(n,d)\) is the largest value of \(M\) such that there exists a \(q\)-ary \((n,M,d)\)-code.

\(A_q(n,d)=\max M\ni\exists\,q\text{-ary}\,(n,M,d)\text{-code}\)

Theorem #

(i) \(A_q(n,1)=q^n\)

(ii) \(A_q(n,n)=q\)

PROOF (i)

If \(d(C)\ge1\) then the codewords must be distinct.

The largest \(q\)-ary \((n,M,d)\)-code is just \((F_q)^n\), and \(M=q^n=|(F_q)^n|\).

\(\blacksquare\)

PROOF (ii)

Suppose \(C\) is a \(q\)-ary \((n,M,n)\)-code.

Then any two distinct codewords differ in all \(n\) positions (columns).

And so the symbols appearing in any fixed position (column) in the \(M\) codewords must be distinct.

Therefore, \(M\le q\). [There can be no more than \(q\) codewords.]

And \(A_q(n,n)\le q\). [The largest value of \(M\) such that… is bounded above by \(q\).]

We already know that the \(q\)-ary repetition code of length \(n\) is an \((n,q,n)\)-code.

Therefore, \(A_q(n,n)=q\).

\(\blacksquare\)

\(q\le A_q(n,d)\le q^n\) for \(1\le d\le n\)

Equivalence of Codes #

Permutation #

[PERMUTATION]

A permutation \(f\) of a set \(S=\{x_1,x_2,...,x_n\}\) is a one-to-one correspondence (or mapping) from \(S\) to itself.

\( \left( \begin{matrix} x_1 & x_2 & \dots & x_n \\ \downarrow & \downarrow & & \downarrow \\ f(x_1) & f(x_2) & \dots & f(x_n) \\ \end{matrix} \right) \)

Equivalence #

Two \(q\)-ary codes are called equivalent if one can be obtained from the other by a combination of operations of the following types:

(A) permutation of the positions (columns) of the code

(B) permutation of the symbols appearing in a fixed position (column)

If a code is displayed as an \(M\times n\) matrix whose rows are the codewords, then an operation of type (A) corresponds to a permutation or rearrangement of the columns of the matrix, while an operation of type (B) corresponds to a relabelling of the symbols appearing in a given column.

The distances between codewords are unchanged by such operations, and so equivalent codes have the same parameters \((n,M,d)\) and will correct the same number of errors.

Under the assumptions of a \(q\)-ary symmetric communication channel, the performances of equivalent codes will be identical in terms of probabilities of error correction.

Lemma #

Any \(q\)-ary \((n,M,d)\)-code over an alphabet \(\{0,1,...,q-1\}\) is equivalent to an \((n,M,d)\)-code which contains the zero vector \(\mathbf{0}=\underbrace{00...0}_{n}\).

PROOF

Choose any codeword \(\mathbf{x}=x_1x_2...x_n\) and for each \(x_i\ne0\) apply the permutation

\( \left( \begin{matrix} 0 & x_i & j \\ \downarrow & \downarrow & \downarrow \\ x_i & 0 & j \\ \end{matrix} \right) \forall j\ne0,x_i \)

to the symbols in position \(i\).

\(\blacksquare\)

Example #

What is \(A_2(5,3)\)? In other words, what is the largest value of \(M\) such that there exists a binary \((5,M,3)\)-code?

We are already familiar with a binary \((5,4,3)\)-code:

\( \begin{aligned} C= \begin{cases} 00000\\ 01101\\ 10110\\ 11011\\ \end{cases} \end{aligned} \)

So \(A_2(5,3)\ge4\).

Is there a binary \((5,5,3)\)-code?

Brute-force method: consider all subsets of order \(5\) in \((F_2)^5\) (over 200,000 of them) and find the minimum distance of each.

q=2
n=5
print(f"{q**n:,}")
f=fqn(q,n)
f

{'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'}

len(list(itertools.combinations(f,r=5)))

max(list(nbfmd(c) for c in itertools.combinations(f,r=5)))

Let’s show that a binary \((5,M,3)\)-code must have \(M\le4\) and that the \((5,4,3)\)-code is unique, up to equivalence.

Suppose \(C\) is a \((5,M,3)\)-code with \(M\ge4\).

By the lemma we can assume that \(\mathbf{0}\in C\) or an equivalent code.

[

\(00000\)

]

\(C\) contains at most one codeword having four or five 1s. For if there were even two such codewords \(\mathbf{x}\) and \(\mathbf{y}\) then they would have at least three 1s in common positions and \(d(\mathbf{x,y})\le2\), contradicting \(d(C)=3\).

[

No more than one of

\(11111,01111,10111,11011,11101,11110\)

]

Since \(\mathbf{0}\in C\), there can be no codewords containing just one or two 1s

[

None of

\(10000,01000,00100,00010,00001,11000,10100,10010,10001,01100,01010,01001,00110,00101,00011\)

]

and so there must be two codewords containing exactly three 1s

[

At least two of

\(11100,11010,11001,01110,01101,00111\)

]

So far, our code looks like this

\( C= \begin{cases} 00000\\ 11100\\ 00111\\ \end{cases} \)

By trial and error, there is no other codeword of three 1s that is three away from both the other codewords with three 1s and there is only one codeword with four or five 1s that is.

\( C= \begin{cases} 00000\\ 11100\\ 00111\\ 11011\\ \end{cases} \)

Therefore, \(A_2(5,3)=4\) and the code which achieves this value is unique, up to equivalence.

Vector operations modulo 2 #

Let \(\mathbf{x,y}\in(F_2)^n\) where \(\mathbf{x}=x_1x_2...x_n\) and \(\mathbf{y}=y_1y_2...y_n\).

x='11100'
y='00111'

Sum #

\(\mathbf{x+y}\in(F_2)^n\) where \(\mathbf{x+y}=(x_1+y_1\mod2,x_2+y_2\mod2,...,x_n+y_n\mod2)\)

vadd({x,y},2)

'11011'

Product #

\(\mathbf{x\cap y}\in(F_2)^n\) where \(\mathbf{x\cap y}=(x_1y_1\mod2,x_2y_2\mod2,...,x_ny_n\mod2)\)

vmul({x,y},2)

'00100'

Weight #

The weight \(w(\mathbf{x})\) of a vector \(\mathbf{x}\in(F_2)^n\) is the number of 1s in \(\mathbf{x}\).

vw(x)

Lemma 2.5 #

[LEMMA 2.5]

If \(\mathbf{x,y}\in(F_2)^n\) then \(d(\mathbf{x,y})=w(\mathbf{x+y})\).

[The distance between two binary vectors is just the weight of their modular sum.]

PROOF

\(\mathbf{x+y}\) has a \(1\) where \(\mathbf{x}\) and \(\mathbf{y}\) differ and a \(0\) where \(\mathbf{x}\) and \(\mathbf{y}\) agree.

\(\blacksquare\)

Lemma 2.6 #

[LEMMA 2.6]

If \(\mathbf{x,y}\in(F_2)^n\) then \(d(\mathbf{x,y})=w(\mathbf{x})+w(\mathbf{y})-2w(\mathbf{x\cap y})\).

PROOF

\(d(\mathbf{x,y})=w(\mathbf{x+y})=\) the number of 1s in \(\mathbf{x}-\) the number of 1s in \(\mathbf{y}-2\) the number of positions where both \(\mathbf{x}\) and \(\mathbf{y}\) have a 1

[We multiply the third term by 2 to subtract 1 from and account for each of the two vectors who share the 1 in a common position.]

\(\blacksquare\)

Theorem 2.7 #

[THEOREM 2.7]

Suppose \(d\) is odd.

Then a binary \((n,M,d)\)-code exists iff a binary \((n+1,M,d+1)\)-code exists.

PROOF [only if]

If a binary \((n,M,d)\)-code exists then a binary \((n+1,M,d+1)\)-code exists.

Suppose \(C\) is a binary \((n,M,d)\)-code where \(d\) is odd.

Let \(\hat{C}\) be the code of length \(n+1\) obtained from \(C\) by extending each codeword \(\mathbf{x}\) of \(C\) according to the rule

ADDING AN OVERALL PARITY CHECK TO THE CODE C

\( \begin{aligned} \mathbf{x}&=x_1x_2...x_n \\ \mathbf{\hat{x}}&= \begin{cases} x_1x_2...x_n0 & \text{if}\,w(\mathbf{x})\,\text{is even}\\ x_1x_2...x_n1 & \text{if}\,w(\mathbf{x})\,\text{is odd}\\ \end{cases} \\ &=x_1x_2...x_nx_{n+1} \,\,\,\text{where}\,\,\, x_{n+1}=\left(\sum_{i=1}^nx_i\right)\mod2 \end{aligned} \)

Since \(w(\mathbf{\hat{x}})\) is even for every codeword \(\mathbf{\hat{x}}\in\hat{C}\) it follows from lemma 2.6 that \(d(\mathbf{\hat{x},\hat{y}})\) is even for all \(\mathbf{\hat{x},\hat{y}}\in\hat{C}\).

Therefore, \(d(\hat{C})\) is even.

\(d\le d(\hat{C})\le d+1\)

Since \(d\) is odd, \(d(\hat{C})=d+1\).

Therefore, \(\hat{C}\) is a \((n+1,M,d+1)\)-code.

PROOF [if]

If a binary \((n+1,M,d+1)\)-code exists then a binary \((n,M,d)\)-code exists.

Suppose \(D\) is a binary \((n+1,M,d+1)\)-code where \(d\) is odd.

Choose codewords \(\mathbf{x,y}\in D\ni d(\mathbf{x,y})=d+1\).

Choose a position in which \(\mathbf{x}\) and \(\mathbf{y}\) differ and delete this from all codewords.

The result is a \((n,M,d)\)-code.

\(\blacksquare\)

Corollary 2.8 #

[COROLLARY 2.8]

If \(d\) is odd, then \(A_2(n+1,d+1)=A_2(n,d)\).

Equivalently, if \(d\) is even, then \(A_2(n,d)=A_2(n-1,d-1)\).

Known values of \(A_2(n,d)\)#

Sloane 1982 pp. 156
MacWilliams and Sloane 1977 pp. 674

\(n\)	\(d=3\)	\(d=5\)	\(d=7\)
5	4	2
6	8	2
7	16	2	2
8	20	4	2
9	40	6	2
10	72-79	12	2
11	144-158	24	4
12	256	32	4
13	512	64	8
14	1024	128	16
15	2048	256	32
16	2560-3276	256-340	36-37

\( \begin{aligned} A_2(5,3)&=4=A_2(6,4)\\ A_2(5,5)&=2=A_2(6,6)\\ A_2(6,3)&=8=A_2(7,4)\\ A_2(6,5)&=2=A_2(7,6)\\ ... \end{aligned} \)

Examples of constructing codes via adding an overall parity check #

\( \text{binary}\,\)(5,4,3)\(\text{-code}\, C= \begin{cases} 00000\\ 01101\\ 10110\\ 11011\\ \end{cases} \)

c={'00000','01101','10110','11011'}
c

{'00000', '01101', '10110', '11011'}

overall_parity_check(c,2)

{'000000', '011011', '101101', '110110'}

nbfmd(overall_parity_check(c,2))

Binomial Coefficients #

If \(n\) and \(m\) are integers with \(0\le m\le n\), then the binomial coefficient “\(n\) choose \(m\)” is

\( \begin{aligned} {n\choose m} =\frac{n!}{m!(n-m)!} \end{aligned} \)

where \(m!=m\cdot(m-1)\cdot...\cdot3\cdot2\cdot1\) for \(m\gt0\) and \(0!=1\).

Lemma 2.10 #

[LEMMA 2.10]

The number of unordered selections of \(m\) distinct objects from a set of \(n\) distinct objects is \(n\choose m\).

PROOF

An ordered selection of \(m\) distinct objects from a set of \(n\) distinct objects can be made in

\( \begin{aligned} n(n-1)...(n-m+1)=\frac{n!}{(n-m)!} \end{aligned} \)

ways, for the first object can be chosen in any of \(n\) ways, then the second in any of \(n-1\) ways, and so on.

Since there are \(m\cdot(m-1)\cdot...\cdot2\cdot1=m!\) ways of ordering the \(m\) objects chosen, the number of unordered selections is

\( \begin{aligned} \frac{n!}{m!(n-m)!} \end{aligned} \)

\(\blacksquare\)

The main coding theory problem

Contents

The main coding theory problem #

Table of Contents #

Programming Environment #

The main coding theory problem #

Theorem #

Equivalence of Codes #

Permutation #

Equivalence #

Lemma #

Example #

Vector operations modulo 2 #

Sum #

Product #

Weight #

Lemma 2.5 #

Lemma 2.6 #

Theorem 2.7 #

Corollary 2.8 #

Known values of \(A_2(n,d)\)#

Examples of constructing codes via adding an overall parity check #

Binomial Coefficients #

Lemma 2.10 #