ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

3.1. Назначение и классификация кодов

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

Пусть источник выдает некоторое дискретное сообщение А, которое можно рассматривать как последовательность элементарных сообщений или символов а_i (i = 1, 2, . . . К). Совокупность символов а_i называется алфавитом источника, а К - объемом алфавита.

Кодирование заключается в том, что каждый символ источника (сообщения) а_i заменяется последовательностью кодовых символов - кодовой комбинацией. Совокупность правил, по которым образуется набор кодовых комбинаций, однозначно соответствующий алфавиту источника, называется кодом.

При кодировании отдельным символам а_i удобно сопоставить целые числа от 0 до К-1, обозначив их, например, M_i

Любое число M может быть представлено в позиционной системе счисления с основанием m в виде

M = b_n-1m^n-1 + b_n-2m^n-2 +. . . + b₁m¹ + b₀m⁰(3.1)

Основанием позиционной системы счисления называется количество символов в алфавите системы счисления, а в качестве коэффициентов b_i в (3.1) могут использоваться только символы, входящие в алфавит этой системы, т.е. b_i могут принимать значения 0, 1, . . . , m-1.

Тогда кодирующее преобразование можно отобразить так

а_i ® M_i ® (b_n-1 b_n-2 . . . b₁ b₀),(3.2)

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

Число m символов в алфавите кода называется основанием кода.

Число разрядов n в каждой кодовой комбинации постоянно при всех i, т.е. n=const, то такой код называется равномерным.

Необходимость замены каждого символа а_i из К символов источника последовательностью кодовых символов (b_n-1 b_n-2 . . . b₁ b₀) или кодовой комбинацией объясняется тем, что в большинстве случаев объем алфавита K>m, т.е. основания кода или объема алфавита кодовых символов. Например, в телеграфном коде каждая буква русского алфавита (К=32) кодируется кодовой комбинацией из n=5 двоичных (m=2) символов (0 и 1).

Если сообщение «а» заменяется кодовой комбинацией «b» при условии их однозначного соответствия и обратимости преобразования, то на основе свойств взаимной информации (2.13. и 2.14) можно записать I(a,b) = H(a) = =H(b), где I(a,b) - количество информации в кодовой последовательности «b» относительно сообщения «а», H(a) - энтропия сообщения, H(b) - энтропия кодовой последовательности. Следовательно, при кодировании энтропия не меняется.

Иначе обстоит дело с избыточностью, определяемой соотношением между энтропией (2.5) и ее максимальным значением при данном объеме алфавита (2.4). Поскольку при кодировании чаще всего происходит изменение объемов алфавитов, избыточность может как возрастать, так и уменьшаться.

Число возможных кодовых комбинаций из n разрядов для кода с основанием m равно N=mⁿ . Если из этих N комбинаций для кодирования используется только часть, равная N_р, которые называются рабочими или разрешенными, то величина N_р называется мощностью кода.

Избыточность кода характеризуется коэффициентом избыточности

r_к = 1 - (log_mN_p / log_mN). (3.3)

Код, у которого N_р = N , т.е. используются все возможные комбинации, имеет r_к = 0 и называется безизбыточным или неизбыточным.

Простейшим безизбыточным равномерным кодом является обычный двоичный (m=2) n-разрядный код, называемый иногда кодом на все сочетания. Число комбинаций такого кода N = 2ⁿ.

К таким кодам можно отнести уже упомянутый телеграфный код, а также стандартные коды для обмена информацией КОИ-7, КОИ-8, ASCII и другие.

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

Например: 1101

Или, другими словами, если начинать преобразование с младшего (правого) разряда, то алгоритм выглядит следующим образом: «Если последующий разряд равен 1, то данный разряд инвертируется, если последующий разряд равен 0, то данный разряд остается неизменным. Старший разряд остается неизменным».

Пример 3.1. Составить таблицу соответствия обычного двоичного четырехразрядного кода и кода Грея.

Решение. Таблица соответствия обычного двоичного четырехразрядного кода и кода Грея будет выглядеть следующим образом.

Функциональная схема преобразователя обычного двоичного кода в код Грея для четырехразрядных комбинаций представлена на рис. 3.1

Рис. 3.1

Рис. 3.2

Обратное преобразование из кода Грея в обычный двоичный код осуществляется в соответствии со следующим алгоритмом: 1. Старший разряд кодовой комбинации кода Грея остается без изменений. 2. Каждый последующий разряд, начиная от старшего, инвертируется столько раз, сколько единиц ему предшествует в кодовой комбинации кода Грея.

Пример 3.2. Синтезировать функциональную схему четырехразрядного преобразователя кода Грея в обычный двоичный код.

Решение. Функциональная схема четырехразрядного преобразователя кода Грея в обычный двоичный код представлена на рис. 3.2

Преимущества кода Грея проявляются при преобразованиях аналоговых (непрерывных) величин в код. Если при таком преобразовании используется обычный двоичный код, то некоторые комбинации отличаются друг от друга во всех разрядах и при считывании такого кода может возникнуть ошибка, достигающая максимальной величины 2^n-1, где n - число разрядов кода. Например, комбинация 0111 при неправильном считывании старшего разряда преобразуется в комбинацию 1111, т.е. ошибка составит величину 15-7 =8 = 2^4-1. При тех же значениях и при той же ошибке, но при использовании кода Грея (см. таблицу) комбинация 0100 будет считана как 1100, т.е. ошибка составит величину 8-7, т.е. единицу младшего разряда.

Еще одним классом примитивных кодов, используемых при различных промежуточных преобразованиях, являются т.н. двоично-десятичные коды. В таком коде каждая цифра (декада) десятичного числа записывается в виде четырехразрядного двоичного числа (тетрады). С помощью 4 разрядов можно образовать 2⁴ = 16 различных комбинаций, из которых любые 10 могут составить алфавит двоично-десятичного кода. В связи с этим существует большое количество различных двоично-десятичных кодов. Наиболее употребительные из них представлены в таблице.

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

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

Рассмотренные до сих пор безизбыточные коды были равномерными, т.е. содержали одинаковое число разрядов в каждой кодовой комбинации вне зависимости от статистических свойств символов источника, кодируемых этими комбинациями. В том случае, если символы источника неравновероятны, такие коды окажутся избыточными. Уменьшение существующей избыточности источника является задачей т.н. эффективного кодирования или кодирования для источника. Алгоритмы построения наиболее известных эффективных кодов будут рассмотрены в разделе 3.2. Здесь же отметим, что вследствие упомянутого выше негативного свойства безизбыточных кодов эффективное кодирование в чистом виде используется только тогда, когда кодовые комбинации не подвергаются воздействию помех.

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

3.2. Эффективное кодирование

Целью эффективного кодирования является устранение избыточности сообщений, поскольку избыточные сообщения требуют большего времени для передачи и большего объема памяти для хранения.

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

В качестве иллюстрации - простой пример. Пусть сообщение может состоять из двух слов. Длина первого - один кодовый символ, второго - три кодовых символа. Вероятности появления слов в сообщении соответственно 0,1 и 0,9. Тогда статистически средняя длина слова в сообщении 1*0,1 + 3*0,9 = 2,8 символа. Если слова будут иметь другие вероятности, например, 0,9 и 0,1, то средняя длина слова составит 1*0,9 + 3*0,1 = 1,2 символа. Отсюда видно, что длина кодовой комбинации должна выбираться в зависимости от вероятности появления кодируемого этой комбинацией символа сообщения. Чем чаще он появляется, т.е. чем больше его вероятность, тем более короткую кодовую комбинацию ему следует сопоставить.

Формализуем задачу эффективного кодирования. Пусть входным алфавитом кодирующего отображения является множество сообщений . Пусть выходным алфавитом кодирующего отображения будет множество В , число элементов которого равно m .Кодирующее отображение сопоставляет каждому сообщению а_i кодовую комбинацию, составленную из n_i символов алфавита В . Требуется оценить минимальную среднюю длину кодовой комбинации. Сравнивая ее со средней длиной кодовой комбинации, вычисленной для какого-либо конкретного кода, можно оценить, насколько данный конкретный код находится близко к эффективному, т.е. безизбыточному коду.

Энтропия сообщения А по определению (2.3)

. (3.4)

Средняя длина кодовой комбинации

, (3.5)

где n_i - длина кодовой комбинации, сопоставленной сообщению а_i. Максимальная энтропия, которую может иметь сообщение из n_СР символов алфавита В, число элементов которого равно m , равна в соответствии с (2.4)

. (3.6)

Очевидно, что для обеспечения передачи информации, содержащейся в сообщении А, с помощью кодовых комбинаций алфавита В должно выполняться неравенство

(3.7)

или с учетом (3.6) или с учетом (3.4)

. (3.8)

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

. (3.9)

Поскольку из (3.6) и (3.7) следует, что , то ясно, что

. (3.10)

Тогда формулу (3.9) для коэффициента избыточности для кода можно переписать в следующем виде

. (3.11)

Под эффективным кодом понимается код, r_К которого равен 0, т.е. для абсолютно эффективных кодов . Тогда и неравенство (3.8) переходит в равенство , откуда .

Предположив очевидное, что А не содержит элементов с p(a_i) = 0, получим

(3.12)

для всех i. Но отношение (3.12) не всегда дает целочисленный результат. Следовательно, не для любого набора А с заданным распределением вероятностей p(a_i) можно построить абсолютно эффективный код с r_К = 0. Тем не менее, всегда можно обеспечить выполнение неравенства , умножая которое на p(a_i) и суммируя по i , получим

. (3.13)

Неравенство (3.13) может служить критерием для оценки эффективности какого-либо конкретного кода.

Для построения эффективных кодов используются различные алгоритмы. Одним из них является код Шеннона - Фано. Код Шеннона - Фано строится следующим образом. Символы алфавита источника выписываются в порядке убывания их вероятностей. Затем вся совокупность разделяется на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковыми. Далее всем символам одной группы в качестве первого кодового символа приписывается 1, а другой группы - 0. Далее каждая из полученных групп в свою очередь разбивается на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой группе останется по одному символу.

Пример 3.3. Закодировать двоичным кодом Шеннона - Фано ансамбль {a_i} (i=1,2,...,8), если вероятности символов a_i имеют следующие значения

Найти среднее число символов в кодовой комбинации и коэффициент избыточности кода.

Решение.

По формуле (3.5) , по формуле (3.4) , тогда по формуле (3.10) и по формуле (3.11) , таким образом, построен абсолютно эффективный код.

Алгоритм кодирования Шеннона - Фано имеет простую графическую иллюстрацию в виде графа, называемого кодовым деревом. Граф для кода Шеннона - Фано строится следующим образом. Из нижней или корневой вершины графа исходят два ребра, одно из которых помечается символом 0, а другое – 1. Эти два ребра соответствуют разбиению множества символов алфавита источника на две примерно равновероятные группы, одной из которых сопоставляется кодовый символ 0, а другой – 1. Ребра, исходящие из вершин следующего уровня, соответствуют разбиению получившихся групп на равновероятные подгруппы и т.д. Построение графа заканчивается, когда множество символов алфавита источника будет разбито на одноэлементные подмножества. Каждая концевая вершина графа, т.е. вершина, из которой уже не исходят ребра, соответствует некоторой кодовой комбинации. Чтобы сформировать эту комбинацию, надо пройти путь от корневой вершины до соответствующей концевой, выписывая в порядке следования по этому пути кодовые символы с ребер пути.

Рассмотренная методика Шеннона - Фано не всегда приводит к однозначному построению кода, поскольку в зависимости от вероятностей отдельных символов можно несколькими способами осуществить разбиение на группы.

Пример 3.4. Закодировать двоичным кодом Шеннона - Фано ансамбль {a_i} (i=1,2,...,8), если вероятности символов a_i имеют следующие значения

Найти коэффициент избыточности кода.

Решение.1

По формуле (3.5) , по формуле (3.4) , тогда по формуле (3.10) и по формуле (3.11) ..

Решение.2

По формуле (3.5) , по формуле (3.4) , тогда по формуле (3.10) и по формуле (3.11) , т.е. второй вариант решения ближе к оптимальному, поскольку обеспечивает меньший коэффициент избыточности.

От данной неоднозначности построения эффективного кода свободен код Хаффмена. Для двоичного кода методика Хаффмена сводится к следующему. Символы алфавита источника выписываются в основной столбец таблицы в порядке убывания вероятностей. Далее два последних символа объединяются в один вспомогательный с вероятностью, равной сумме вероятностей объединяемых символов. Вероятности символов, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания в дополнительном столбце таблицы, после чего два последних символа вновь объединяются. Процесс повторяется до тех пор, пока не буде получен единственный вспомогательный символ с вероятностью, равной 1. Для составления кодовых комбинаций, соответствующих символам, необходимо проследить пути переходов по строкам и столбцам таблицы.

Для наглядного представления этого процесса удобнее всего построить граф, называемый кодовым деревом. Процедура построения кодового дерева выглядит следующим образом. Из вершины, соответствующей последнему единственному вспомогательному символу с вероятностью, равной 1, направляются две ветви, причем ветви с большей вероятностью присваивается кодовый символ 1, а с меньшей - 0. Такое последовательное ветвление из вершин, соответствующих вспомогательным символам, продолжается до получения вершин, соответствующих основным исходным символам.

Пример 3.5. Закодировать двоичным кодом Хаффмена ансамбль из примера 3.4. Решение представлено на рис. 3.3.

Рис. 3.3

Кодовое дерево для этого примера изображено на рис. 3.4 Рис. 3.4

Составленная в соответствии с графом таблица кодовых комбинаций   ai кодовая комбинация ni a1 01 2 a2 00 2 a3 111 3 a4 110 3 a5 100 3 a6 1011 4 a7 10101 5 a8 10100 5

Таким образом, получены те же параметры в смысле избыточности, что и в примере 3.4, решение 2 для кода Шеннона - Фано, хотя кодовые комбинации по составу другие.

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

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

Наличие или отсутствие свойства префиксности отражается и на кодовом дереве. Если свойство префиксности отсутствует, то некоторые промежуточные вершины кодового дерева могут соответствовать кодовым комбинациям.

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

Очевидно, что практическое применение могут иметь только префиксные коды. Коды Шеннона - Фэно и Хаффмена являются префиксными.

При использовании префиксных кодов возникает вопрос о том, каковы возможные длины кодовых комбинаций префиксного кода. Пусть a₁, a₂, . . . , a_N - кодовые комбинации префиксного двоичного кода. Пусть n_k -число кодовых комбинаций длины k . Число n_k совпадает с числом вершин k-го уровня кодового дерева. Конечно справедливо неравенство n_k £ 2^k, поскольку 2^k - максимально возможное число вершин на k-м уровне двоичного дерева. Однако для префиксного кода можно получить гораздо более точную оценку. Если n₁, n₂, . . . , n_k-1 - число вершин 1-го, 2-го, . . . , (k-1)-го уровней дерева, то число всех вершин k-го уровня кодового дерева префиксного кода равно , и поэтому , или иначе .

Деля обе части неравенства на 2^k,получим . Это неравенство справедливо для любого k£L , где L - максимальная длина кодовых комбинаций . Если обозначить l₁, l₂, . . . , l_N длины кодовых комбинаций a₁, a₂, . . . , a_N , то последнее неравенство можно записать следующим образом .

Это и есть условие, которому должны удовлетворять длины кодовых комбинаций двоичного префиксного кода. Это неравенство в теории кодирования называется неравенством Крафта и является достаточным условием того, что существует префиксный код с длинами кодовых комбинаций l₁, l₂, . . . , l_N .

Если кодовый алфавит содержит не два, а S символов, то подобным же образом доказывается, что необходимым и достаточным условием для существования префиксного кода является выполнение неравенства .

Контрольные

вопросы к

Лекции 12

12-1. Что называется кодом?

12-2. Что называется основанием кода?

12-3. Какой код называется равномерным?

12-4. Что называется мощностью кода?

12-5. Как определяется коэффициент избыточности кода?

12-6. Какой код называется безизбыточным?

12-7. Являются ли безизбыточными двоично-десятичные коды?

12-8. Что является целью эффективного кодирования?

12-9. Опишите методику Шеннона-Фано для построения эффективного кода.

12-10. В чем состоит недостаток методики Шеннона-Фано для построения эффективного кода?

12-11. Опишите методику Хаффмена для построения эффективного кода.

12-12. Опишите методику построения кодового дерева для кода Хаффмена.

12-13. Какие эффективные коды называются префиксными?

12-14. Что устанавливает неравенство Крафта?

Лекция 13

Общие

Принципы

Построения

Помехоустойчивых

Кодов

3.3. Помехоустойчивое кодирование

3.3.1. Общие принципы построения помехоустойчивых кодов

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

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

Любые коды могут быть представлены как конечные множества N_р слов, каждое из которых состоит из n символов. Интерпретировать кодовые слова можно по-разному:

1) как наборы из n предметов, располагаемых в некотором порядке в n позициях – т.н. комбинаторная интерпретация;

2) как наборы n-значных элементов множества, замкнутого относительно операций над наборами – т.н. алгебраическая интерпретация;

3) как множество точек некоторой геометрической фигуры – т.н. геометрическая интерпретация.

Все модели, представляющие коды, условно можно разделить на три соответствующих вида. К комбинаторным моделям относят сочетания, перестановки и т.п.; к алгебраическим – группы, поля, кольца, линейные векторные пространства и т.п.; к геометрическим – графы, многогранники и т.п. В дальнейшем изложении в той или иной степени будут использоваться все названные виды представления кодов.

Таким образом, все множество N=2ⁿ двоичных кодовых комбинаций, где n - число разрядов в комбинации, разбивается на два подмножества - разрешенных N_р и запрещенных N-N_р кодовых комбинаций. Если в результате воздействия помех передаваемая кодовая комбинация перейдет из подмножества разрешенных в подмножество запрещенных, ошибка будет обнаружена при приеме (рис. 3.5)

Рис. 3.5

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

Пусть, например, требуется передавать два сообщения - А₁ и А₂. Для этого достаточно одного двоичного разряда - А₁ = 0, А₂ = 1. Под воздействием помехи одно сообщение неминуемо преобразуется в другое.. Добавим к каждой кодовой комбинации еще по одному разряду, выбрав его значение таким, чтобы в каждой разрешенной кодовой комбинации было нечетное число единиц, т.е. А₁ = 01, А₂ = 10. Эти комбинации образуют подмножество разрешенных кодовых комбинаций. В подмножество запрещенных, следовательно, войдут комбинации, содержащие четное число единиц - 00 и 11. Одиночная ошибка может перевести сообщение А₁ в 00 или в 11, аналогично и по отношению к сообщению А₂, т.е. при наличии одиночной ошибки обе комбинации переходят в подмножество запрещенных, т.о. любая одиночная ошибка будет обнаружена.

При необходимости построения кода с исправлением ошибок все множество кодовых комбинаций N разбивается на N_p непересекающихся подмножеств. Каждое из подмножеств приписывается одной из N_p разрешенных кодовых комбинаций. Если передавалась кодовая комбинация A_j , принадлежащая подмножеству N_j , а принятой оказалась комбинация A_i , которая также принадлежит подмножеству N_j , то принимается решение о том, что принята комбинация A_j , т.е. ошибка исправляется. Если комбинация в результате воздействия помех перейдет в другое подмножество, то она будет принята с ошибкой (рис. 3.6).

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

Рис. 3.6

Для иллюстрации сказанного продолжим рассмотренный ранее пример, введя в использованные в нем кодовые комбинации еще один дополнительны разряд. В результате образуется множество из N=2³ = 8 кодовых комбинаций. Его следует разделить на два (по числу передаваемых сообщений А₁ и А₂) непересекающихся подмножества. Пусть, например, для передачи А₁¹ используется комбинация 001. Одиночная ошибка в любом из разрядов этой комбинации приведет к комбинациям А₁² = 000, А₁³ = 011 и А₁⁴ = 101. Эти четыре комбинации и образуют первое подмножество. При приеме любой из них будет принято решение о том, что передавалось А₁, т.е. любая одиночная ошибка будет исправлена. Аналогично относительно А₂, если положить, что А₂¹ = 110, то А₂² = 111, А₂³ = 100, А₂⁴ = 010. При приеме любой из этих комбинаций будет принято решение, что передавалось А₂.

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

В общем случае для двоичных кодов расстояние между i-ой и j-ой комбинациями кода определяется по формуле

(3.14)