Коды, позволяющие обнаружить и/или исправить ошибки в кодовых словах, возникающие при передаче через канал с шумом.
Строятся таким образом, что используются только часть всех возможных кодовых слов. Используемые кодовые слова называются разрешёнными, прочие – запрещёнными.
Разделяют на две группы:
Границы применимости кода:
Код может:
Если \(\forall \vect c_1, \vect c_2 \in C: d_H(\vect c_1, \vect c_2) \ge d_0\), то ошибка кратности \(t=d_0-1\), приводит к запрещённому коду.
Выбор однозначный при \(t\)-кратной ошибке, если \[\underset{{\vect c_1, \vect c_2 \in C \\ \vect c_1 \neq \vect c_2 }}\min d_H(\vect c_1, \vect c_2) > 2 t.\]
Пусть \(A_R(N,d)\) – мощность блочного кода \(C\) над алфавитом \(R\) с блоком длины \(N\) и кодовым расстоянием \(d_0 = d\). Тогда, \[A_R(N, d) \le \frac{|R|^N}{\sum_{k=0}^t C_N^k (|R|-1)^k}\] где \(C_N^k = \frac{N!}{k!(N-k)!}\) – биномиальный коэффициент, \(t = \floor{\frac{d-1}{2}}\)
\[B_{\vect c} = \brace{\vect x \bigg| \vect x \in R^N, d_H(\vect c, \vect x) \le \floor{\frac{d-1}{2}}}\]
Пусть код исправляет \(t= \floor{\frac{1}{2}(d-1)}\)-кратные ошибки, тогда
\(\forall \vect c_1 \neq \vect c_2 \in C: B_{\vect c_1} \cap B_{\vect c_2} = \varnothing;\)
\(\forall \vect c \in C:\:|B_{\vect c}| = \sum_{k=0}^t C_N^k (|R|-1)^k.\)
\[|B_c| |C| \le |R|^N\]
\[|B_c| A_R(N,d) \le |R|^N\]
\[A_R(N,d) \le \frac{|R|^N}{|B_c|}\]
\[A_R(N,d) \le \frac{|R|^N}{\sum_{k=0}^t C_N^k (|R|-1)^k}\phantom{\qquad\blacksquare}\]
\[A_R(N,d) \le \frac{|R|^N}{\sum_{k=0}^t C_N^k (|R|-1)^k}{\qquad\blacksquare}\]
Следствие:
\[A_R(N,d) \le \frac{|R|^N}{\sum_{k=0}^t C_N^k (|R|-1)^k}\]
\[\log_2 A_R(N,d) \le \log_2 \frac{|R|^N}{\sum_{k=0}^t C_N^k (|R|-1)^k}\]
\[\log_2 A_R(N,d) \le \log_2 {|R|^N} - \log_2{\sum_{k=0}^t C_N^k (|R|-1)^k}\]
\[\log_2 A_R(N,d) - \log_2 {|R|^N} \le - \log_2{\sum_{k=0}^t C_N^k (|R|-1)^k}\]
\[\log_2 {|R|^N} - \log_2 A_R(N,d) \ge \log_2{\sum_{k=0}^t C_N^k (|R|-1)^k}\]
Для \(|R|=2\): \[\log_2 {|R|^N} - \log_2 A_R(N,d) \ge \log_2 {\sum_{k=0}^t C_N^k}.\]
Пусть \(A_R(N,d)\) означает максимальную мощность для любого блочного кода \(C\) над алфавитом \(R\) с блоком длины \(N\) и кодовым расстоянием \(d_0 = d\). Тогда, \[A_R(N, d) \ge \frac{|R|^n}{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}\] где \(C_N^k = \frac{N!}{k!(N-k)!}\) – биномиальный коэффициент.
Пусть \(C\) – код, имеющий максимальную мощность, \(|C| = A_R(N,d)\).
Тогда, \(\forall \vect x \in R^N\), \(\exists \vect c_x \in C: d_H(\vect x, \vect c_x) \le d-1.\) В противном случае, мы могли бы добавить \(x\) в код, сохранив все его свойства, что противоречит предположению о его максимальной мощности.
Пусть \(B_{\vect c} = \brace{\vect x | \vect x \in R^N, d_H(\vect c, \vect x) \le d - 1}\). Тогда, \[R^N = \bigcup_{\vect c\in C} B_{\vect c}.\]
\[|B_c| = \sum_{k=0}^{d-1} C_N^k (|R|-1)^k.\]
\[|R|^N = |R^N|\]
\[|R|^N = |R^N| = \abs{\bigcup_{c\in C} B_c}\]
\[|R|^N = |R^N| = \abs{\bigcup_{c\in C} B_c} \le \sum_{c\in C} \abs{B_c}\]
\[|R|^N = |R^N| = \abs{\bigcup_{c\in C} B_c} \le \sum_{c\in C} \abs{B_c} = |C| |B_c|\]
\[|R|^N \le |C| |B_c|\]
\[|R|^N \le A_R(N,d) |B_c|\]
\[|R|^N \le A_R(N,d) \sum_{k=0}^{d-1} C_N^k (|R|-1)^k\]
\[\frac{|R|^N}{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k} \le A_R(N,d)\phantom{\qquad\blacksquare}\]
\[A_R(N,d) \ge \frac{|R|^N}{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}{\qquad\blacksquare}\]
Следствие:
\[A_R(N,d) \ge \frac{|R|^N}{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}\]
\[\log_2 A_R(N,d) \ge \log_2 \frac{|R|^N}{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}\]
\[\log_2 A_R(N,d) \ge \log_2 {|R|^N}-\log_2{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}\]
\[\log_2 A_R(N,d) -\log_2 {|R|^N} \ge -\log_2{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}\]
\[\log_2 {|R|^N} - \log_2 A_R(N,d) \le \log_2{\sum_{k=0}^{d-1} C_N^k (|R|-1)^k}\]
Для алфавита \(|R|=2\): \[\log_2 {|R|^N} - \log_2 A_R(N,d) \le \log_2{\sum_{k=0}^{d-1} C_N^k}\]
Любой код над двоичным алфавитом:
\[\log_2 {\sum_{k=0}^{t} C_N^k} \le I_R \le \log_2 {\sum_{k=0}^{d-1} C_N^k }\] \(t = \floor{\frac{d-1}{2}}\), \(I_R\) – количество проверочных бит.
Для максимизации пропускной способности, минимизируем \(I_R\): \[I_R = \log_2 {\sum_{k=0}^{t} C_N^k}\] аналогично \[A_R(N, d) = \frac{|R|^N}{\sum_{k=0}^t C_N^k (|R|-1)^k}.\]
Коды, удовлетворяющие этому равенству называются совершенными.
С совершенными кодами есть одна проблема.
Рассмотрим ДСК с вероятностью перехода \(f\). Пропускная способность \(C(f) = 1 - H_2(f)\). По теореме о кодировании канала, \(\exists\) код с \(\rho \approx C(f)\). Число битовых ошибок \(\approx fN\), т.е. код исправляет \(fN\) ошибок (почти наверняка).
Пусть \(f > 1/3\). Пусть \(\exists\) совершенный исправляющий \(fN\) ошибок код. Рассмотрим три кодовых слова (их должно быть \(2^{N\rho} \approx 2^{NC(f)}\), при больших N найдётся три).
\(\vect c_1 = \underbrace{000\ldots000}_{uN}\underbrace{000\ldots000}_{vN}\underbrace{000\ldots000}_{wN}\underbrace{000\ldots000}_{N(1-u-v-w)}\) \(\vect c_2 = \underbrace{111\ldots111}_{uN}\underbrace{111\ldots111}_{vN}\underbrace{000\ldots000}_{wN}\underbrace{000\ldots000}_{N(1-u-v-w)}\) \(\vect c_3 = \underbrace{000\ldots000}_{uN}\underbrace{111\ldots111}_{vN}\underbrace{111\ldots111}_{wN}\underbrace{000\ldots000}_{N(1-u-v-w)}\)
Если код исправляет \(fN\) ошибок, то \(d_0 > 2fN\),
\(d_H(\vect c_1, \vect c_2) = (u+v)N > 2 fN\), \(d_H(\vect c_1, \vect c_3) = (v+w)N > 2 fN\), \(d_H(\vect c_2, \vect c_3) = (u+w)N > 2 fN\).
\[ (u+v)N + (v+w)N + (u+w)N > 6 fN\]
\[ u+v + v+w + u+w > 6 f\]
\[ u+v +w > 3 f\]
Но \(f>1/3\), и \(u+v+w > 1\), тогда \(x < 0\), что невозможно.
То есть, совершенный исправляющий \(fN\) ошибок код не может иметь даже трёх кодовых слов, не говоря уже о \(2^{N\rho}\).
Все нетривиальные совершенные коды над двоичным алфавитом: