Двоичное кодирование

Квант 1979, №7 с. 14-20 Тег EP49

Как передают сообщения по линиям связи? Схема такой передачи представлена на рисунке.

Кодирующее устройство сопоставляет каждому передаваемому сообщению определенную комбинацию сигналов (приемлемую для передачи по данному каналу связи), называемую кодом. Операция передода сообщения в последовательность различных сигналов называется кодированием, обратное преобразование, состававливающей ее по принятым сигналам переданное сообщение, — декодированием. Коды, используемые два различных элементарных сигнала, называются двойными. В телефонном диопчье коды Морзе и Бодо. В азбуке Морзе каждой букве сопоставляется определенная последовательность кратковременных (называемых моичками) и длительных (мире) импульсов тока. В коде Бодо каждой букве сопоставляется определенная последовательность из пятни элементарных сигналов — импульса и паузы.

Процесс кодирования, когда различных типов, требования, предъявляемые к ним, и многое смежные проблемы изучает теория информации и кодирования. В ней сочетаютсявероятностиные, алгебраические и комбинаторные методы.

Здесь мы останавливаемся лишь на некоторых частных вопросах кодирования, а заинтересовавшихся читателей отсылаем к специальным книгам — например, А. М. Яглом и И. М. Яглом «Вероятность и информации» (М., «Нayka», 1973), У. Питерсон «Коды, исправляющие ошибки (М., «Мир», 1964), У. Питерсон, Э. Уэлдон «Коды, исправляющие ошибки (М., «Мир», 1976).

Спрашиваем — ответаем

В основе двойного кодирования лежит очень простой принцип. Разьясним его на такой задаче.

Некто задумал число, заключенное между 0 и 7. Угадывающий разрешено задавать вопросы, ответы на которые даются лишь в форме «да» или «нет». Каким намененный числом вопросов можно обойтись, чтобы наверняка узнать задуманное число?

Самый бескатростный путь (так, наверное, поступил бы ребенок) — перебирать числа нагада, найдя на

удачу. При очень сильном воздействии может хранить и одного вопроса, но если не повезет, то может попадать целых семь. Поэтому оставим надежду на мгновенную удачу и постараемся построить такую систему вопросов, чтобы любоий из ответов на них — «да» или «нет» — давал нам одинаковую (пустых хотя и неполную) информацию о задуманном числе, а число вопросов было минимальным.

Например, первый вопрос может быть таким: «Заключено ли задуманное число в пределах от 0 до 3?». Оба ответа — и «да» и «нет» — одинаково приближают нас к цели: в общих случаях остаются четые возможности для неизвестного числа (первоначально их было воспеть).

Если на первый вопрос получен утвердительный ответ, то во второй раз можно просить: «Не является ли задуманное число нулем или единицей?}; если же ответ был отрицательным, просим: «Не является ли задуманное число четверкой или пятеркой?»

В любом случае после ответа на второй вопрос остается выбор из двух возможностей. Для того чтобы осуществить этот последний выбор, достаточно одного вопроса. Итак, для угадывания задуманного числа, каким бы он был, достаточно трех вопросов.

Если каждый из двух возможных ответов «да» или «нет» обозначить условно символами «0» и «1», то ответ записывается в виде последовательности, состоящей из 0 и 1. Так, например, если в разобранном выше примере задуманное число было нулем, то на каждый из трех вопросов ответом будет «да». Трем «да» соответствует последовательность 000.

Если было задумано число «3», то ответами будет: да, нет, нет. То есть «тройке» соответствует последовательность 011. По результатам ответов можно составить таблицу 1, приведенный ниже. Тот из вас, кто знаком с двойной системой чиселления, узнет в нижней строке двойную запись соответствующих чисел верхней строки.

Заметим, что вместе множества чисел от 0 до 7 можно рассматривать любое множество из возможных, и каждое из них мы можем за-

Таблица 1

кодировать последовательности из 0 и 1 длины 3. Последовательности из нуля и единиц можно закодировать любое конечное множество сообщений.

Действительно, двойных последовательностей длины 3 равно $2^3 = 8$ (все они приведены в таблице), двойных последовательностей длины 4 вдвое больше — их $2^4 = 16$ . Вообще, число двойных последовательностей длины $n$ равно $2^n$ . Поэтому, если требуется закодировать нуля и единиц, к примеру, 125 сообщений, то для этого с лихвой хватит двойных последовательностей длины 7 (их в нашем распоряжении $2^7 = 128$ ). Наконец, для закодирования любого числа $M$ сообщений можно использовать двойные последовательности длины $n$ такой, что $2^n \geq M$ .

Код Фано

Всегда ли выгодно кодировать сообщения словами одинаковой длины так, как мы это делали выше?

Представим себе, что один сообщения приходится передать довольно часть, другие — сравнительно редко, третьи — совсем в исключительных случаях. Довольно понятно, что первые лучшие закодировать коротками словами, оставив более длинные слова для кодирования сообщений, появляющихся режем.

В математике меры частоты поовления того или иного сообщения являются его вероятность. Тот, кто не знаком с этим понятем, может представлять себе вероятность неокоторого сообщения (сообщения) как долю тех случав, в которых оно появляется, от общего числа рассматриваемых сообщений (сообщений) *). Вероятность сообщения $A$ обозначают $P(A)$ .

Пусть четыре сообщения $A_1, A_2, A_3, A_4$ имеют вероятности

$P(A_1) = \frac{1}{2}, P(A_2) = \frac{1}{4}, P(A_3) = P(A_4) = \frac{1}{8}.$

*) См., например, указаны выше книгу А. Яглома и И. Яглома.

Это означает, что среди, например, 1000 переданных сообщений около 500 раз появляется сообщение $A_1$ , около 250 — сообщение $A_2$ и примерно 125 раз — каждое из сообщений $A_3$ и $A_4$ .

Эти сообщения нетрудно закодировать двойными словами длины 2, как показано в таблице:

| $A_1$ | $A_2$ | $A_3$ | $A_4$ |
| :— | :— | :— | :— |
| 00 | 01 | 10 | 11 |

При этом вероятность их появления никак не учитывается. Поступим теперь иначе. Разобем сообщения на две равноверятные группы: в первую попадает сообщение $A_1$ , во вторую — $A_2$ , $A_3$ , $A_4$ . Сопоставим первый группе символ «0», второй группе — символ «1». Это вплоне в двух прицilia, применящегося в задаче с угадыванием. Действительно, символ «0» соответствует ответу «да» на вопрос «Принадлежит ли сообщение первого группы?», а «1» — ответу «нет». Разница лишь в том, что раньше все множество разбиалось на две группы, состоящие из одинакового числа элементов, теперь — из разного. Но, как и раньше, разница это таково, что оба ответа «да» и «нет» равноверзможны. Продолжая в таком же духе, разобем множество сообщений $A_2, A_3, A_4$ снова на две равноверятные группы. Первой, состоящей из одного сообщения $A_2$ , сопоставляем символ «0», второй, в которой входят сообщения $A_3$ и $A_4$ , — символ 1. Наконец, оставшуюся группу из двух сообщений разобем на сообщения $A_3$ и $A_4$ , сопоставляем первый символ 0, второй — 1 (они равноверятны). Процесс закончен. Сообщение $A_1$ на первом шаг образовало «самостояльную» группу, и ему был сопоставлен символ 0, он и кодирует это сообщение. Сообщение $A_2$ образовало самостояльную группу за два шага, на первом шаг ему соответствовал символ 1, на втором — 0; значит, сообщение $A_2$ кодируется словом 10. Аналогично, для

сообщений $A_3$ и $A_4$ имеем, соответствно, последовательности 110 и 111. Итак, мы получаем следующую кодовую таблицу:

| $A_1$ | $A_2$ | $A_3$ | $A_4$ |
| :— | :— | :— | :— |
| 0 | 10 | 110 | 111 |

Именно такой способ кодирования предложил Фано. Возникает вопрос, что же мы выиграли по сравнению с равномерным кодом, применив код Фано? Чтоы ответить на него, представим, что непрерывным потоком передаются сообщения $A_1$ , $A_2$ , $A_3$ , $A_4$ — всего 1000 сообщений. Посчитаем, сколько потребуется потребить двойных символов для их передачи при первом и втором способе кодирования.

При использовании равномерного кода это посчитать нетрудно: на каждое сообщение — два символа, значит, в общей сложности 2000 символов.

Пусть теперь использовать код Фано. Вспомним, что из 1000 сообщений примерно 500 раз появляется первоое, которое кодируется всего один символом (500 символов), 250 раз — сообщение $A_1$ , оно кодируется двумя символами (еще 500), на сообщении $A_3$ и $A_4$ , появляющиеся примерно 125 раз, придает потребить еще $3 \times 250 = 750$ символов. Итого нужно передать примерно 1750 символов. Выиграш? Конечно. Ведь во втором случае передача займет меньше времени. Можно представить себе ситуацию, когда выиграш от применения кода Фано оказывается значительнее, чем в приведенном примере.

Доверяй, но проверяй

Мы установили, что любое конечное множество сообщений можно закодировать кодовым словами из 0 и 1 (двоичными кодовым словами). Беда в том, что при передаче закодированных сообщений возможны ошибки.

Как правило, не в нашей власти полностью устранить источник ошибок. Как же тогда уберечься от их влияния и возможного ли это вообществу? А если возможно, то какой ценой?

Оказывается, такие возможности — обнаруживать ошибки и даже их исправлять — имеются. Но неизбежной платой за это является удлинение кодовых слов, то есть добавление некоторого числа символов. Эти символы уже не несут информацию о передаваемых сообщениях, но могут дать информацию о производших при передаче ошибках. Иными словами, их назначение — контролировать правильность передачи кодового слова. Вводимые дополнительные символы так и называют контROLНЫми (или проверочными).

Всero одна проверка

Минимальная дань — добавить к каждому кодовому слову лишь один проверочный символ. Разберемся, на что мы можем расчитывать в этом случае. Пусть $\alpha_1 \alpha_2 \dots \alpha_n$ — двойное кодовое слово ( $\alpha_i = 0$ или 1). По всей видимости, контрольный символ $\alpha_{n+1}$ выгодно выбрать так, чтобы на его значение влиял каждый символ кодового слова. Самое простое — положить $\alpha_{n+1} = \alpha_1 + \alpha_2 + \dots + \alpha_n$ (mod 2) *. Эта запись означает, что проверочный символ $\alpha_{n+1}$ равен нулю, если в кодовом слове $\alpha_1 \alpha_2 \dots \alpha_n$ содержалось четное число единиц, и единица — в противном случае. Например, присоединя такой проверочный символ к слову 1010, получаем слово 10100; соответственно, из слова 1110 получим 11101.

Заметьте, что все удаленные кодовые слова $\alpha_1 \alpha_2 \dots \alpha_n \alpha_{n+1}$ содержат число единиц, то есть $\alpha_1 + \alpha_2 + \dots + \alpha_n + \alpha_{n+1} = 0$ (mod 2). (1)

Представим себе, что в процессе передачи в удаленное кодовое слово $\alpha_1 \alpha_2 \dots \alpha_n \alpha_{n+1}$ включается одна ошибка (или даже любое нечетное число ошибки).

*) О сложении «по модулю» можно прочитать в статье Н. Виленкина «Сравнения и классы вычетов» («Квант», 1978, № 10).

бок). Тогда в исключном слове $\alpha'_1\alpha'_2 \dots \alpha'_n\alpha'_{n+1}$ число единиц станет нечетным. Это и служит индикатором того, что в принятом слове содержится ошибка. Разумеется, нам не надо скрупулезно подсчитывать число единиц, достаточно лишь проверить, выполняется ли для символов принятого слова равенство (1),— это легко сделать простейшее вычислительное устройство. Если равенство (1) выполняется, считаем, что сообщение передано правильно, в противном случае констатируем, что произошла ошибка, и, если это возможно, требуется повторения передачи кодового слова. Но самостоятельное исправить ошибку мы не сможем. Например, если принято «неправильное слово» 11100, то возможно, что было послан любое из кодовых слов:

01100; 10100; 11000; 11110; 11101.

Каждай из перечисленных случаев соответствует одиночной ошибке. Ошибки могут произойти также в трех или даже в пяты символах. Гораздо хуже, если произошла двойная ошибка или вообщее четное число ошибок. Ведь тогда соответствие (1) не нарушится, и мы воспримем искаженное слово как верное, в результате будет принято ложное сообщение.

Описанный код (его называют кодом с общей проверкой на четность) позволяет, следовательно, обнаружить нечетное число ошибок, но приводит к неверному декодированию, если ошибок четное число. Его выборно применять позитomy, когда достаточно влика верятность одиночной ошибки и очень мало верятны ошибки в большем числе символов.

Гораздо чаще применяют коды с несколькими проверочными символами — это позволяет не только обнаружить, но и исправлять ошибки, и не только одиночные, но и кратные.

Самый медленный код

Простейший прим, позволяющий исправлять ошибки, состоит в том, что каждый информационный символ повторяется несколько раз так, что символы 0 и 1 кодируются блоками, состоящими из $n$ нулей (соответственно, $n$ единиц). При декодировании $n$ -буквенного блока, содержащого, быть может, ошибочные символы, принимается решение «большинством голосов». Если в принятом блоке нулей больше, чем единиц, то он декодируется как 00 … 0, в противном случае — как 11 … 1. Такое правило декодирования позволяет верно восстановить последанные символы, если помехи в канале искажают меньше положины символов в каждом передаваемом блоке. Если длину блока $n$ выбрать достаточно большой, то мы практически обезопасим себя от возможных ошибок, однако передача сообщений будет идти черезышми темпами.

Когда с общей проверкой на четность и код с повторением — два антипода. Первый очень быстро, но зачастую «легкомыслен». Возможности второго исправлять ошибки теоретически безграничны, но делает он это чересчур медленно.

Из сообщений, высказанных разнее, можно усмотреть, что для исправления ошибок нужно, чтобы использовать для декодирования слова достаточно сильно отличались друг от друга. В этом случае возможно при передаче ошибок они скорее всего останут различными, и искажения не помещают нам «угадать» посланное слово.

Необучное общное расстояние

Мы подошли к понятному расстоянию между кодовым словами. Расстоянием (точнее, расстоянием Хемминга) $ρ(x, y)$ между двумя кодовым словами $x, y$ называют числом символов, в которых они отличаются. Например, расстояние между словами 1010111 и 0110010 равно 4 — они отличаются символами на 1-м, 2-м, 5-м и 7-м местах.

Термин «расстояние» для величины $ρ(x, y)$ определяет тем, что она обладает основными свойствами общного расстояния между точкими на плоскости или в пространстве (п. 4 в «Геометрии 6» или п. 132 в «Геометрии 8»).

Важной характеристикой корректуриших способностей кода является его кодовое расстояние $d$ , которое определяется как минимальное расстояние между различными кодовыми словами $\min \rho(x, y)$ .

Ясно, что м чебольше кодовое расстояние, тем больше исправляющих способности обладает данный код. Мы можем сформулировать этот факт более точно:

Чтобы код исправляющие комбинации из $t$ (и меньше числа) ошибок, необходимо и достаточно, чтобы его кодовое расстояние было больше 2 $t$ .

Действительно, если это так, то $\rho(x, y) \geq 2t + 1$ для любых кодовых слов $x$ и $y$ . Если в результате искажений оба слова перешли в одно слово $z$ (т. е. стали неразличными), то (в силу одного из свойств расстояния — аксиомы треугольника)

$\rho(x, z) + \rho(z, y) \geq 2t + 1$ , и следовательно, либо $\rho(x, z) > t$ , либо $\rho(z, y) > t$ . Значит, любые ошибки в $t$ или меньше символьных любых кодовых слов $x$ и $y$ оставляют их еще различными, и поэтому можно восстановить оригинал. Еще проще доказывается обратное утверждение.

Задание

Имеется 8 двойных кодовых слов длины 3. Их можно изобразить в пространственной системе координат как вершины куба со стороны 1. Каков в этом случае «геометрический смысл» расстояния между кодовыми словами?
Доказать, что максимальный двойный код длины 5 (то есть код, у которого все кодовые слова имеют длину 5) с кодовым расстоянием, равным 3, содержит 4 кодовых слов. Указать такой код.
Существует ли код длины 20, содержащий 1000 кодовых слов и исправляющий кодификацию из трех или менее ошибок?
Доказать, что для обнаржения $s$ (или меньше числа) ошибок необходимо и остаточно, чтобы кодовое расстояние $d \geq s + 1$ .
Доказать, что для исправления $t$ (или меньше числа) ошибок и вместе с этим обнаржения $s$ (≥ $t$ ) необходимо и остаточно, чтобы кодовое расстояние удовлетворило неравенству $d \geq t + s + 1$ .

Код Хемминга

Пусть количество сообщений, которые требуется передавать абоненту, равно 16. Для их кодирования можно использовать слова длины 4, но тогда код не будет корректировать ошибки. Мы уже знаем, что при использовании слов длины 5 можно обнаружить любую одиночную ошибку в кодовом слове, но, увы, нельзя исправить. Двух добавочных символов тоже оказывается недостаточно для исправления одиночных ошибок (убедитесь в этом самостоянию).

А вот tremя добавочных символами можно распорядиться так, чтобы вывить и исправить любую одиночную ошибку.

Предположим, что нам удалось указать 16 кодовых слов длины семь — $\alpha_1\alpha_2\alpha_3\alpha_4\alpha_5\alpha_6\alpha_7$ , для которых по модели два выполнены следующие равенства:

$\begin{cases} S_1 = \alpha_4 + \alpha_5 + \alpha_6 + \alpha_7 = 0, \\ S_2 = \alpha_2 + \alpha_3 + \alpha_6 + \alpha_7 = 0, \\ S_3 = \alpha_1 + \alpha_3 + \alpha_5 + \alpha_7 = 0. \end{cases}$

Тогда разряд, в котором допущена одиночная ошибка, указается числом с двойной записью $S_1S_2S_3$ (напомним, что каждое $S_i$ — это 0 или 1). В частности, для кодовых слов этого числа равно 0 (= 000), что указает на отсутствие разряда с ошибкой.

Сделанное утверждение вытекает из того, что при нашей кодировании (т. е. при нашей наборе кодовых чисел) для двойного слова длины 7 с одиночной ошибкой $S_1 = 1$ тогда и только тогда, когда эта ошибка допущена в четвертом, пятом, шестом или седьмом разряде (см. (2)), $S_2 = 1$ тогда и только тогда, когда ошибка — во втором, третьем, шестом или седьмом разряде, и $S_3 = 1$ — когда в первом, третьем, шестом или седьмом.

Пусть, например, $S_1 = 1$ , $S_2 = 0$ , $S_3 = 1$ . Тогда ошибка — в одном из четырех последних разрядов ( $S_1 = 1$ ), но в двух последних разрядах ошибки нет ( $S_2 = 0$ ); значит, ошибка — в четвертом или пятом разряде; поскольку $S_3 = 1$ , она — в пятом разряде, но $S_1S_2S_3 =$

=101 как раз и есть двойная запись числа 5. Остальные случаи рассматривают аналогично.

Осталось отыскать 16 кодовых слов, удовлетворяющих соответствием (2). Для этого достаточно заменить, что, если $\alpha_1, \alpha_2, \alpha_3$ и $\alpha_4$ выбраны произвольно и по mod 2 выполняются равенства

$\begin{cases} \alpha_5 = \alpha_2 + \alpha_3 + \alpha_4, \\ \alpha_6 = \alpha_1 + \alpha_3 + \alpha_4, \\ \alpha_7 = \alpha_1 + \alpha_2 + \alpha_4, \end{cases}$

то соответствия (2) верны.

Изученный здесь код — это код Хемминга длины 7 с четырьмя информатонными символами.

В общем случае кодовые слова двойного кода Хемминга, позволяющего исправить одиночный ошибку, имеют длину $2^m - 1$ . Для определения положения ошибки тогда нужно $m$ проверок, т. е. $m$ проверочных символов. Оставшиеся $2^m - 1 - m$ символов являются информатонными.

Список читателей, приславших правила решения задач из Задачника «Кванта»

В этом номере мы публикуем фамилии читателей, приславших правила решения задач М516 — М530, Ф523 — Ф532 (жирные цифры после фамилия — последние цифры номеров решенных задач).

Математика

К. Абдухаликов (Алма-Ата) 16—18, 19a), 20, 21, 26—28; Е. Абрамчкин (Куйбышев) 16a); И. Авемисян (с. Мулки АрмССР) 18; О. Авраммава (Москва) 21; А. Адеев (с. Покровка АзССР) 166), 21, 22, 24, 26; С. Азнабаев (Новотроицк Оренбургской обл.) 26; В. Айриян (Раздан) 16a), 6) 18, 20, 22, 24, 26, 27; З. Алавердян (Иджеван) 26; В. Алиев (Тбилиси) 26; В. Андрусевич (Кобрин) 28; Р. Ардан (Львов) 28; К. Аромамян (Кафан) 26; Н. Арутиной (Киев) 28; А. Ахметхозин (Анджан) 27; А. Ашкинази (Москва) 16—19; Д. Бабарикин (Магнитогорск) 16a); А. Бадалян (пос. Берд АрмССР) 16, 21—23, 26—28, 30a); Б. Байсакалов (Алма-Ата) 166), 18, 19, 21, 24, 26—29; А. Балинский (с. Дубляны Львовской обл.) 16, 18, 19, 21—24, 26—28, 30; И. Баранец (пос. Дзержинский Московской обл.) 26—28; А. Барвинок (Ленинград) 28, 29; А. Барре (Николаев)

16a; 6); Б. Беун (Москва) 16, 21; А. Белуосов (Калининград Московской обл.) 26; С. Беспамятных (Артемовский Свердловской обл.) 19a), 24, 27, 28; В. Бобов (Ленинград) 26; Н. Бовсуновский (с. Путлювчи Житомирской обл.) 21; Т. Болотников (Харьков) 16, 18, 19a), 21, 26, 28, 29, 30a); А. Борцев (Ленинград) 19, 26—28; В. Боровко (Новополошк) 26; И. Бородин (Соликамск) 22, 23; О. Бохонов (Москва) 21, 22, 236), 24, 26, 27, 30a); А. Брациский (Воронеж) 24; А. Бурин (Москва) 28; А. Васильев (Саратов) 16a), 21, 26, 28, 30a); С. Великович (Минск) 28; В. Винорезадов (Москва) 16, 18, 19a), 21, 22, 23a), 24, 26—28, 30a); А. Воронов (Москва) 16; А. Габович (Харьков) 26; Э. Гаджilarов (Тбилиси) 26—28; А. Галенко (Москва) 16a), 6), 26; Э. Галстян (с. Айгезард АрмССР) 18; Н. Гасилов (Баку) 26; К. Гедалин (Тбилиси) 26; А. Гильман (Москва) 16, 18, 19, 21, 22, 24, 26—28; Л. Гитлин (Витебск) 16a), 6), 21, 23; М. Гладина (В. Волочек) 21; Ю. Глухов (Шелково) 166), 18, 21, 28; А. Головин (Москва) 21; О. Гордиенко (Павлодар) 16a), 21, 22, 27; М. Горолев (Белороцк) 16, 18, 19, 26, 28, 30a); Г. Грабарник (Ташкент) 26, 27, 29, 30a; Г. Грабужик (Ташкент) 16, 18—24; П. Григорук (Гайворон) 21, 24; Н. Грибере (Киев) 26, 28; Л. Гройсман (Харьков) 28; В. Губа (Вологда) 16, 18—21, 24—29;

(Продолжение см. с. 32)