Файл: Зелигер Н.Б. Основы передачи данных учеб. пособие.pdf

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

Связь между способностью кода обнаруживать и исправлять ошибку и величиной кодового расстояния наиболее просто можно показать на геометрической модели. Если для передачи использу­ ются все восемь кодовых комбинаций, то наименьшее кодовое рас­ стояние между комбинациями d —1 (одно ребро куба), и при воз­ никновении ошибки переданная комбинация преобразуется в дру­ гую ближайшую комбинацию, вследствие чего ошибка не сможет быть обнаружена. Так, например, переданная комбинация 000 под воздействием помехи может быть принята как одна из следующих трех комбинаций: 100, 010, 001. Но эти три комбинации исполь­ зуются в трехэлементном коде.

Для обнаружения одиночной ошибки необходимо, чтобы кодо­ вое расстояние между комбинациями rf= 2 (два ребра куба). Та­ кому условию удовлетворяют комбинации 000, НО, 011 и 101. Любая одиночная ошибка в одной из четырех используемых («раз­ решенных») комбинаций превращает эту комбинацию в неисполь­ зуемую («запрещенную»), что и позволяет обнаружить ошибку. Любая двойная ошибка в одной из четырех используемых комби­ наций превращает эту комбинацию также в используемую. Поэто­ му в данном коде двойная ошибка не обнаруживается.

При кодовом расстоянии d = 2 и возникновении одиночной ошиб­ ки неверная комбинация будет отличаться в одном элементе как от действительно переданной, так и от других кодовых комбина­ ций. Таким образом, в результате'' ошибки неверная комбинация находится от действительно переданной на таком же расстоянии, как и другие кодовые комбинации; отсутствие отличия в расстоя­ ниях не позволяет исправить ошибку.

Для того чтобы одиночная ошибка могла быть не только об­ наружена, но и исправлена, необходимо, чтобы кодовое расстоя­ ние d = 3 (три ребра куба). Здесь, в результате одиночной ошибки, неверная комбинация будет отличаться от действительно передан­ ной только в одном элементе, а от других комбинаций кода — не менее чем в двух элементах. В данном случае возможно опреде­ лить, в какой именно комбинации произошла ошибка; это обеспе­ чивает возможность исправления ошибки.

Вгеометрической модели трехэлементного кода условию d = 3 удовлетворяет любая пара вершин куба, расположенных по кон­ цам его диагонали, например, вершины с координатами 000 и 111. При ошибке в первом элементе комбинации 000 неверная комби­ нация 100 расположена ближе к действительно переданной ком­ бинации 000 (с?=1), чем к комбинации 111 (d= 2), и исправление ошибки становится возможным.

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

59

икодовым расстоянием определяется выражениями:

^ d — 1

а< ----- при нечетном а

2

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

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

На основе (2.16) и (2.17) имеем:

б = 2ст при нечетном d

(2.18)

б = 2сг -+- 1 при четном d

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

<о>2<т+1. (2.19)

Учитывая (2.16), получим

Если же код используется для обнаружения ошибок, то наимень­ ший вес ш каждой разрешенной кодовой комбинации должен быть на единицу больше количества обнаруживаемых ошибок б:

Соотношения (2.20) и (2.22) устанавливают связь между коррек­ тирующей способностью кода (а и б), кодовым расстоянием d и весом кодовых комбинаций со.

Пример. Если d = б, то, пользуясь (2.16) и (2Л7), получим, что ст=2 и ö = 4, т. е. код можно использовать или только для исправления двойных ошибок, или только для обнаружения четырехкратных, тройных, двойных и одиночных оши­ бок. Из (2.18) следует, что если ограничиться исправлением только одиночных ошибок, то одновременно можно обнаруживать двойные и тройные ошибки.

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

60

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

КОЛИЧЕСТВО КО М Б И Н А Ц И И «-ЭЛЕМ ЕНТНОГО КО ДА , РАССТОЯНИЕ М Е Ж Д У КО ТО РЫ М И НЕ М ЕНЕЕ d

Из принципов обнаружения и исправления ошибок следует, что избыточные /г-элементные коды строятся таким образом, чтобы из общего числа N0 кодовых комбинаций возможно было выбрать тре­ буемое количество информационных комбинаций N, кодовое рас­ стояние между которыми не менее d. Этим достигается необходи­ мая корректирующая способность избыточного кода.

При нечетном d наибольшее количество информационных ком­ бинаций N находится из выражения

1 + с ' + с 2 + . . . + c„ 2

61

2.4.Код с исправлением одиночных ошибок

ОБЩ И Е СВЕДЕНИЯ

Методика построения кодов для обнаружения и исправления ошибок впервые наиболее полно была изложена в работе Р. В. Хем­ минга [7]. Рассмотренный в этой работе код с исправлением оди­ ночных ошибок известен под названием кода Хемминга. Ознако­ мимся с основными идеями, положенными в основу его построе­ ния.

В коде Хемминга для обнаружения и исправления одиночной ошибки из п элементов кодовой комбинации выбирается /г групп, составленных определенным образом. В каждой группе количество единиц должно быть четным. Для этого на передаче к информаци­ онным элементам группы добавляется одни проверочный (избы­ точный) элемент, а на приеме осуществляется проверка на чет­ ность каждой из /г групп принятой комбинации (а не всей комби­ нации в целом). Таким образом, общее число проверочных эле­ ментов комбинации, как и число проверок комбинации, равно k.

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

ОПРЕДЕЛ ЕНИ Е КО Л И ЧЕС ТВА П Р О ВЕРО ЧН Ы Х ЭЛЕМ ЕНТОВ k

Пусть /г-элементная кодовая комбинация состоит из т инфор­ мационных посылок и k проверочных посылок. Очевидно, что п, т

и k могут принимать только целые значения. Так как каждый из

пэлементов комбинации может быть принят с ошибкой, то коли­ чество проверочных чисел, указывающих номера этих ошибок, должно быть не менее п; кроме того, требуется еще одно прове­ рочное число (из k нулей), указывающее на отсутствие ошибок в поступившей комбинации. Таким образом, общее число провероч­ ных чисел будет п + 1.

Поскольку наибольшее число комбинаций ^-элементного дво­ ичного кода равно 2к, то справедливо неравенство

(2.25)

откуда

62