Далее: §29. Коды Фано и Вверх: Глава IV. Энтропия и Назад: §27. Кодирование и декодирование

§30. Блочные коды

Блочный код заменяет каждый блок из $m$ символов более длинным блоком из $n$ символов, которые после передачи подлежат декодированию. Из соображений простоты и надежности большинство систем связи конструируются для передачи двоичных последовательностей, такими являются и $(m,n)$-коды.

Одним из ключевых понятий теории кодирования является понятие расстояния между двоичными словами. Расстояние $d(\mbox{\boldmath$a,b$})$ между словами $\mbox{\boldmath$a$} = (a_{1},a_{2},\ldots ,a_{n})$ и $\mbox{\boldmath$b$} = (b_{1},b_{2},\ldots ,b_{n})$ равно числу позиций, в которых $a_i \ne b_i$. Весом $w\mbox{\boldmath$a$}$ слова $\mbox{\boldmath$a$}$ называется число единиц среди его координат. Тогда расстояние $d(\mbox{\boldmath$a$},\mbox{\boldmath$b$})$ будет равно весу $\mbox{\boldmath$a$}+\mbox{\boldmath$b$}$, т.е. $d(\mbox{\boldmath$a$},\mbox{\boldmath$b$}) = w(\mbox{\boldmath$a$}+\mbox{\boldmath$b$})$.

Пример 146. Показать, что сдвиг $\mbox{\boldmath$x$} \to \mbox{\boldmath$x$}+\mbox{\boldmath$c$}$ не изменяет расстояние между словами $\mbox{\boldmath$a$}$ и $\mbox{\boldmath$b$}$.

Решение. $d(\mbox{\boldmath$a$}+\mbox{\boldmath$c$}, \mbox{\boldmath$b$}+\mbox{\boldmath$... ...\boldmath$a$}+\mbox{\boldmath$b$}) = d(\mbox{\boldmath$a$},\mbox{\boldmath$b$})$.

Пример 147. Найти вероятность того, что переданное слово $\mbox{\boldmath$a$}$ будет принято как $\mbox{\boldmath$a$}^{\ast }$.

Решение. Воспользуемся функцией расстояния $d(\mbox{\boldmath$a$},\mbox{\boldmath$a$}^{\ast })$ для представления вероятностей ошибок. Ошибочно будет принято $d(\mbox{\boldmath$a$},\mbox{\boldmath$a$}^{\ast })$ символов, каждый с вероятностью $q$, а вероятность того, что переданное слово $\mbox{\boldmath$a$}$ будет принято как $\mbox{\boldmath$a$}^{\ast }$, равна $p^{n - d(a,a^\ast)}\cdot q^{d(a,a^\ast)}$.

Пример 148. Для того, чтобы код давал возможность исправлять все ошибки в не более чем $k$ позициях, необходимо и достаточно, чтобы наименьшее расстояние между двумя кодовыми словами было $2k+1$.

Решение. Если это условие на $E$ выполнено, то в качестве $\mbox{Д}$ следует взять функцию $а \to$ (ближайшее слово из образа $E$), которая исправит ошибки в $k$ позициях.

Для блоков большой длины задание кодового слова для каждого блока требует большого объема памяти. Значительно экономней результат дает методика матричного кодирования. Пусть $m\times n$ - матрица $E$ с элементами $e_{ij}$ из нулей и единиц. Обозначая знаком $+$ сложение по модулю $2$, определим схему кодирования уравнениями:

$$b_{j}=a_{1}e_{1j }+a_{2}e_{2j }+\ldots + a_{m}e_{mj} (j= 1, 2, \ldots , n) .$$

Она отвечает умножению строки на кодированную матрицу $Е$ справа и определяет ($m,n$)-код.

Код не должен приписывать одно и то же кодовое слово разным словам. Одним из способов добиться этого состоит в том, чтобы первые $m$ столбцов матрицы $Е$ образовали единичную матрицу.

Пример 149. Построить (3,5)-код, используя следующую 355 матрицу:

$$Е = \left[ {\begin{array}{l} { 1 0 0 1 0} \\ { 0 1 0 1 1} \\ { 0 0 1 0 1} \\ \end{array}} \right].$$

Решение. Полный список кодирования таков:

$\mbox{\boldmath$a$}^{0}$ = 000 $\to$ 00000	$\mbox{\boldmath$a$}^{4}$ = 110 $\to$ 11001
$\mbox{\boldmath$a$}^{1}$ = 100 $\to$ 10010	$\mbox{\boldmath$a$}^{5}$ = 101 $\to$ 10111
$\mbox{\boldmath$a$}^{2}$ = 010 $\to$ 01010	$\mbox{\boldmath$a$}^{6}$ = 011 $\to$ 01110
$\mbox{\boldmath$a$}^{3}$ = 001 $\to$ 00101	$\mbox{\boldmath$a$}^{7}$ = 111 $\to$ 11100

Этот список показывает преимущество матричного кодирования: достаточно запомнить $m$ кодовых слов вместо $2^{m}$ слов.

Блочный код называется групповым, если его кодовые слова образуют группу относительно покоординатного сложения по модулю 2. Поскольку $d(\mbox{\boldmath$b$}^{i},\mbox{\boldmath$b$}^{j}) = w(\mbox{\boldmath$b$}^{i}+\mbox{\boldmath$b$}^{j})$, то в групповом коде наименьшее расстояние между двумя кодовыми словами равно наименьшему весу ненулевого кодового слова.

Рассмотрим задачу оптимизации декодирования группового кода $Е$: $\mbox{\boldmath$a$} \to \mbox{\boldmath$a$}Е$ с двоичной матрицей кодирования $Е$. Наша задача - минимизировать вероятность того, что $\mbox{\it Д}[\mbox{\boldmath$a$}E] \ne \mbox{\boldmath$a$}$, предполагая равными вероятности передачи сигнала по двоичному симметричному каналу.

Схема декодирования основана на таблице С всех слов, которые могут быть приняты. Поскольку кодовые слова образуют подгруппу $В \subset С$, то можно расположить $С$, записав в одну строку элементы смежного класса по модулю $В$. Первая строка отвечает нулевому классу:

$$\mbox{\boldmath $0$}, \mbox{\boldmath $b$}^{1}, \mbox{\boldmath $b$}^{2}, \ldots , \mbox{\boldmath $a$}^{2^m - 1} .$$

Если $\mbox{\boldmath$c$}^{i} \in С$ и $\mbox{\boldmath$c$}^{i} \notin В$, то строка, содержащая слово $\mbox{\boldmath$c$}^{i}$, имеет вид

$$\mbox{\boldmath $0$}+\mbox{\boldmath $c$}^{i}, \mbox{\boldma... ...s , \mbox{\boldmath $b$}^{2^m - 1}+\mbox{\boldmath $c$}^{i} ,$$

где в качестве $\mbox{\boldmath$c$}^{i}$ выбирается слово наименьшего веса, называемого лидером этого класса.

Декодирование слова $\mbox{\boldmath$c$} = \mbox{\boldmath$b$}^{j }+ \mbox{\boldmath$c$}^{i}$ состоит в выборе кодового слова $\mbox{\boldmath$b$}^{j}$ в качестве переданного и последующем применении операции $Е ^{ - 1}$.

Пример 150. Составить таблицу декодирования для (3,5)-кода из предыдущего примера.

Решение. В первой строке поместим кодовые слова, а в первом столбце - лидеров класса, вес которых равен 0 и 1.

00000	10010	01010	00101	11001	10111	01110	11100
10000	00010	11010	10101	01001	00111	11110	01100
01000	11010	00010	11101	10001	11111	00110	10100
00100	10110	01110	00001	11101	10011	01010	11000

Чтобы декодировать принятое слово, следует отыскать его в таблице и выбрать в качестве переданного кодовое слово из того же столбца и из первой строки.

Вопросы для самоконтроля

1. Как определяется вес слова?

2. Какая связь между кодовым расстоянием и весом слова?

3. Существует ли связь между вероятностью принятия переданного слова и расстоянием между переданным и принятым словами?

4. Необходимые и достаточные условия обнаружения ошибок.

5. Назовите условия исправления ошибок.

6. В чем заключается методика матричного кодирования?

7. Какой код называется групповым?

8. Геометрические интерпретации кодирующих и декодирующих систем.

Задачи

I 291. Докажите, что если расстояние между кодовыми словами равно 5, то код способен обнаруживать до четырех ошибок и исправлять до двух ошибок.

292. Какова вероятность того, что не будет обнаружена ошибка при пере-даче слова в (6,7)-коде с проверкой на четность?

293. Вычислите вероятность пропуска ошибок в таком (4,8)-коде, что минимальное расстояние между кодовыми словами равно 4.

294. Рассмотрите (3,4)-код с проверкой на четность и (3,6)-код с двукратной передачей. При $p = 0,9$ вычислите вероятность того, что ошибочно переданное слово не будет обнаружено.

295. Найдите кодирующую матрицу для (3,4)-кода с проверкой на четность.

296. Найдите кодирующую матрицу для (2,6)-кода с трехкратной передачей.

II 297. Код задан матрицей

$$\left[ {\begin{array}{l} { 1 0 0 0 1 1} \\ { 0 1 0 1 0 1} \\ { 0 0 1 1 1 1} \\ \end{array}} \right]$$

Какова вероятность того, что слово будет принято как правильное, тогда как на самом деле остались необнаруженными ошибки?

298. Постройте стандартную матрицу, порождающую код, эквивалентный коду с матрицей

$$\left[ {\begin{array}{l} {\rm0 0 0 1 1 1} \\ {\rm0 1 1 0 1 1} \\ {\rm 1 1 0 0 0 1} \\ \end{array}} \right].$$

III 299. Покажите, что следующие операции над кодирующей матрицей приводят к эквивалентному коду:

а) перестановка строк,

б) перестановка столбцов,

в) замена одной строки суммой ее с другой строкой.

300. (4,8)-код состоит из слов вида $а = (\alpha _1 ,\alpha _2 ,\alpha _3 ,\alpha _4 ,\beta _1 ,\beta _2 ,\beta _3 ,\beta _4 ),$ где $\alpha _1 + \alpha _2 = \beta _1 ,\alpha _3 + \alpha _4 = \beta _2 ,\alpha _1 + \alpha _3 = \beta _3 ,\alpha _2 + \alpha _4 = \beta _4$. Является ли этот код групповым? Чему равно минимальное расстояние этого кода?

Далее: §29. Коды Фано и Вверх: Глава IV. Энтропия и Назад: §27. Кодирование и декодирование