perfect-related-codes.md (1548B)
1 +++ 2 title = 'Perfect & related codes' 3 template = 'page-math.html' 4 +++ 5 # Perfect & related codes 6 bounds for codes: 7 - if ints t ≤ n and word v length n, then num words length n of max distance t from v is $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}$. If t = n, then 2ⁿ. 8 - all words of distance t from word v: add to v all words weight t 9 - Hamming bound: C length n and distance d = 2t + 1 or 2t + 2, then $|C| = \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}}$ (i.e. max num of words length n distance d in code) 10 - singleton bound: for (n, k, d) linear code, d-1 ≤ n-k 11 - for (n, k, d) linear code: 12 - d = n-k+1 13 - every (n-k) rows of the parity check matrix are linearly independent 14 - every k columns of generator matrix are linearly independent 15 - C is MDS 16 - there exists code length n dimension k distance d if $\binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{d-2} \lt 2^{n-k}$ 17 18 ## Perfect codes 19 perfect code: if length n, distance d = 2t+1, $|C| = \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}}$ 20 21 if C nontrivial perfect code length n, distance d = 2t+1, then n=23 and d=7, or n=2ᴿ-1 for some R ≥ 2 and d=3 22 23 if C perfect code length n distance d = 2t+1, then corrects all error patterns weight ≤ t and no others. 24 25 ## Hamming codes 26 Hamming code length 2ᴿ-1 if n = 2ᴿ-1, R ≥ 2, parity check matrix rows consist of all nonzero vectors length R 27 28 - has dimension 2ᴿ-1-R, contains $2^{2^{R}-1-R}$ codewords 29 - has distance d=3 30 - is a perfect single error correcting code