КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ


Код Рида — Соломона над



, исправляющий



ошибок, требует



проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной



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



дополнительных проверочных символов, исправляется



ошибок (и менее).

Теорема (граница Рейгера)
. Каждый линейный блоковый код, исправляющий все пакеты длиной



и менее, должен содержать, по меньшей мере,



проверочных символов.

Код, двойственный коду Рида — Соломона, есть также код Рида — Соломона. Двойственным кодом для циклического кода
называется код, порожденный его проверочным многочленом.

Матрица




порождает код Рида — Соломона тогда и только тогда когда любой минор
матрицы



отличен от нуля.

При выкалывании
или укорочении
кода Рида — Соломона снова получается код Рида — Соломона. Выкалывание
 — операция, состоящая в удалении одного проверочного символа. Длина



кода уменьшается на единицу, размерность



сохраняется. Расстояние кода



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



кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство
.


Исправление многократных ошибок

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

Код Рида — Соломона



над полем



с кодовым расстоянием



можно рассматривать как



-код над полем



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



или меньшем числе блоков из m символов. Наибольшее число блоков длины



, которые может затронуть пакет длины



, где



, не превосходит



, поэтому код, который может исправить



блоков ошибок, всегда может исправить и любую комбинацию из



пакетов общей длины



, если



.

Расстояния между кодами

Рассмотрим поподробнее код с утроением. Итак, мы получили работающий код, который исправляет одиночную ошибку. Но за всё хорошее надо платить: он кодирует один бит тремя. Не очень-то и эффективно.

И вообще, почему этот код работает? Почему нужно именно утраивать для устранения одной ошибки? Наверняка это всё неспроста.

Давайте подумаем, как этот код работает. Интуитивно всё понятно. Нолики и единички — это две непохожие последовательности. Так как они достаточно длинные, то одиночная ошибка не сильно портит их вид.

Пусть мы передавали $000$
, а получили $001$
. Видно, что эта цепочка больше похожа на исходные $000$
, чем на $111$
. А так как других кодовых слов у нас нет, то и выбор очевиден.

Но что значит «больше похоже»? А всё просто! Чем больше символов у двух цепочек совпадает, тем больше их схожесть. Если почти все символы отличаются, то цепочки «далеки» друг от друга.

Можно ввести некоторую величину $d(\alpha, \beta)$
, равную количеству различающихся цифр в соответствующих разрядах цепочек $\alpha$
и $\beta$
. Эту величину называют расстоянием Хэмминга. Чем больше это расстояние, тем меньше похожи две цепочки.

Например, $d(010, 010) = 0$
, так как все цифры в соответствующих позициях равны, а вот $d(010101, 011011) = 3$
.

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

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

Достаточно разумные требования.

Математически это можно записать так (нам это не пригодится, просто ради интереса посмотрим):

Предлагаю читателю самому убедиться, что для расстояния Хэмминга эти свойства выполняются.


  • Блейхут Р.

    Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.
    : Мир
    , 1986. — 576 с.
  • Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
  • Морелос-Сарагоса Р.

    Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева

    . — М.
    : Техносфера, 2006. — 320 с. — (Мир связи). —  — ISBN 5-94836-035-0
    .


  1. Коды Хемминга — “Все о Hi-Tech”

    . all-ht.ru. Дата обращения: 20 января 2016.
    Архивировано
    15 января 2016 года.


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

Окрестности

Таким образом, разные цепочки мы считаем точками в каком-то воображаемом пространстве, и теперь мы умеем находить расстояния между ними. Правда, если попытаться сколько нибудь длинные цепочки расставить на листе бумаги так, чтобы расстояния Хэмминга совпадали с расстояниями на плоскости, мы можем потерпеть неудачу. Но не нужно переживать. Всё же это особое пространство со своими законами. А слова вроде «расстояния» лишь помогают нам рассуждать.

Пойдём дальше. Раз мы заговорили о расстоянии, то можно ввести такое понятие как окрестность. Как известно, окрестность какой-то точки — это шар определённого радиуса с центром в ней. Шар? Какие ещё шары! Мы же о кодах говорим.

Но всё просто. Ведь что такое шар? Это множество всех точек, которые находятся от данной не дальше, чем некоторое расстояние, называемое радиусом. Точки у нас есть, расстояние у нас есть, теперь есть и шары.

Так, скажем, окрестность кодового слова $000$
радиуса 1 — это все коды, находящиеся на расстоянии не больше, чем 1 от него, то есть отличающиеся не больше, чем в одном разряде. То есть это коды:

$ \{000, 100, 010, 001\}. $

Да, вот так странно выглядят шары в пространстве кодов.

А теперь посмотрите. Это же все возможные коды, которые мы получим в канале в одной ошибкой, если отправим $000$
! Это следует прямо из определения окрестности. Ведь каждая ошибка заставляет цепочку измениться только в одном разряде, а значит удаляет её на расстояние 1 от исходного сообщения.

Аналогично, если в канале возможны две ошибки, то отправив некоторое сообщение $x$
, мы получим один из кодов, который принадлежит окрестности $x$
радиусом 2.

Тогда всю нашу систему декодирования можно построить так. Мы получаем какую-то цепочку нулей и единиц (точку в нашей новой терминологии) и смотрим, в окрестность какого кодового слова она попадает.


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

КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
Структура систематического кодового слова Рида — Соломона

При систематическом кодировании к информационному блоку из



символов приписываются



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



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



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



.

Схема применения кода Рида — Соломона
Схема применения кода Рида — Соломона


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



длины



на неприводимый полином при систематическом кодировании можно выполнить следующим образом:

Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.

Существует и другая процедура
кодирования (более практичная и простая).
Положим



 — примитивный элемент поля



, и пусть



 — вектор информационных символов, а значит



 — информационный многочлен. Тогда вектор <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/456cf861844b62d7723eff39289fc3820b14dfb3" aria-hidden="true" alt="u=(a

,a(\alpha ),\ldots ,a(\alpha ^{{q-2}}))”>



есть вектор кода Рида — Соломона, соответствующий информационному вектору



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




по примитивному элементу



и размерность кода



(длина кода в этом случае определяется как



). Все дело в том, что за разностью



полностью скрывается порождающий многочлен



и кодовое расстояние.


Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:

  • Вычисляет синдром ошибки
  • Строит полином ошибки
  • Находит корни данного полинома
  • Определяет характер ошибки
  • Исправляет ошибки


Вычисление синдрома ошибки

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


Построение полинома ошибки

Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна



, что много меньше степени кодового слова



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


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


Определение характера ошибки и её исправление



где



формальная производная по



многочлена локаторов ошибок



, а

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



Построение кодов Хэмминга основано на принципе проверки на чётность числа единичных символов: к последовательности добавляется такой элемент, чтобы число единичных символов в получившейся последовательности было чётным:




Знак



здесь означает сложение по модулю 2
:




Если



 — то ошибки нет, если



 — то однократная ошибка.

Такой код называется



или



. Первое число — количество элементов последовательности, второе — количество информационных символов.

Для каждого числа проверочных символов



существует классический код Хэмминга с маркировкой:





то есть —



.

При иных значениях



получается так называемый усечённый код, например международный телеграфный код МТК-2, у которого



. Для него необходим код Хэмминга



который является усечённым от классического


Для примера рассмотрим классический код Хемминга



. Сгруппируем проверочные символы следующим образом:










Получение кодового слова выглядит следующим образом:









=



.

На вход декодера поступает кодовое слово




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














называется синдромом последовательности.

Получение синдрома выглядит следующим образом:









=



.

Кодовые слова



кода Хэмминга приведены в таблице.

Синдром



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

Читайте также:  Ошибки на ваз 2110 коды и расшифровка результатов таблица

Для кода



в таблице справа указаны ненулевые синдромы и соответствующие им конфигурации ошибок (для вида:



























).
КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ


Блоковый код, разбивающий информацию на фрагменты длиной



бит и преобразующий их в кодовые слова длиной



бит обычно обозначают



; при этом число



называется скоростью кода
. Если исходные



бит код оставляет неизменными, и добавляет



проверочных, такой код называется систематическим
, иначе — несистематическим
.

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



информационных бит сопоставляется



бит кодового слова. Однако хороший код должен удовлетворять как минимум следующим критериям:

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

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


Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует



-мерное линейное подпространство



в



-мерном линейном пространстве
, изоморфное
пространству



-битных векторов
.

Это значит, что операция кодирования соответствует умножению исходного



-битного вектора на невырожденную матрицу




, называемую порождающей матрицей.

Для ортогонального
по отношению к



подпространства



 и матрицы



, задающей базис
этого подпространства, и для любого вектора



справедливо:





.


Минимальное расстояние и корректирующая способность

Расстоянием Хэмминга (метрикой Хэмминга) между двумя кодовыми словами



и



называется количество отличных бит на соответствующих позициях:





.

Минимальное расстояние Хэмминга



является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность
:





.

Корректирующая способность
определяет, сколько ошибок передачи кода (типа



) можно гарантированно исправить. То есть вокруг каждого кодового слова



имеем



-окрестность




, которая состоит из всех возможных вариантов передачи кодового слова



с числом ошибок (



) не более



. Никакие две окрестности двух любых кодовых слов не пересекаются друг с другом, так как расстояние между кодовыми словами (то есть центрами этих окрестностей) всегда больше двух их радиусов
2t”>



.

Таким образом, получив искажённую кодовую комбинацию из



, декодер принимает решение, что исходной была кодовая комбинация



, исправляя тем самым не более



ошибок.

Например, при наличии всего двух кодовых слов



и



с расстоянием Хэмминга между ними, равным 3, ошибка в одном бите слова



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



, чем к



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



отличалось от



), то результат ошибочной передачи



окажется ближе к



, чем



, и декодер примет решение, что передавалось слово



.


Коды Хэмминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хэмминга может быть представлен в таком виде, что синдром:





,

где



 — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.


Общий метод декодирования линейных кодов

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



соответствует наиболее вероятное переданное слово



. Однако данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора



вычисляется синдром




. Поскольку



, где



 — кодовое слово, а



 — вектор ошибки, то



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


Линейные циклические коды

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

Циклическим кодом является линейный код
, обладающий следующим свойством: если



является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово



представляется в виде полинома



. При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на


по модулю






.

Чаще всего используются двоичные циклические коды (то есть


могут принимать значения 0 или 1).

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему (генераторному) многочлену




. Порождающий многочлен является делителем

.

С помощью порождающего многочлена осуществляется кодирование циклическим кодом. В частности:

Коды

CRC
( англ.
 
cyclic redundancy check

 — циклическая избыточная проверка) являются

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


на

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

Таким образом, вид многочлена



задаёт конкретный код CRC. Примеры наиболее популярных полиномов:


Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.


Коды коррекции ошибок Рида — Соломона

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами
( октетами
).

Математически коды Рида — Соломона являются кодами БЧХ
.


Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок
, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ
), менее высока.


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



должно быть выбрано так, чтобы удовлетворялось неравенство



или



, где



 — количество информационных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице.

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

Основные характеристики самокорректирующихся кодов:

  1. Число разрешённых и запрещённых комбинаций. Если



     — число символов в блоке,



     — число проверочных символов в блоке,



     — число информационных символов, то




     — число возможных кодовых комбинаций,




     — число разрешённых кодовых комбинаций,




     — число запрещённых комбинаций.
  2. Избыточность кода. Величину




    называют избыточностью корректирующего кода.
  3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием



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



     — количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы



  5. Корректирующие возможности кодов.

Граница Плоткина
даёт верхнюю границу кодового расстояния:








при



Граница Хэмминга
устанавливает максимально возможное число разрешённых кодовых комбинаций:


где



 — число сочетаний из

элементов по




элементам. Отсюда можно получить выражение для оценки числа проверочных символов:




Для значений



разница между границей Хэмминга и границей Плоткина невелика.

Граница Варшамова — Гилберта
для больших n определяет нижнюю границу числа проверочных символов:




Все вышеперечисленные оценки дают представление о верхней границе




при фиксированных



и



или оценку снизу
числа проверочных символов.


В середине 1940-х годов в лаборатории Белла
была создана счётная машина Bell Model V
. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: одна операция за несколько секунд. Данные вводились в машину с помощью перфокарт
с ненадёжными устройствами чтения, поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и снова запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.

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


  1. Морелос-Сарагоса Р.

    Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева

    . — М.
    : Техносфера, 2006. — С. 92—93. — (Мир связи). —  — ISBN 5-94836-035-0
    .

  2. Морелос-Сарагоса Р.

    Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева

    . — М.
    : Техносфера, 2006. — 320 с. — (Мир связи). —  — ISBN 5-94836-035-0
    .

  3. . Дата обращения: 24 декабря 2018.
    Архивировано
    24 декабря 2018 года.

  4. Сагалович, 2007
    , с. 212—213.


  5. М. Вернер.
    Основы кодирования. — Техносфера, 2004. — С. 268—269. — ISBN 5-94836-019-9
    .

  6. Морелос-Сарагоса Р.

    Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева

    . — М.
    : Техносфера, 2006. — С. 116—119. — (Мир связи). —  — ISBN 5-94836-035-0
    .

Удлинение кодов РС

Тогда проверочная матрица, удлиненного на один символ РС кода будет



Питерсон У., Уэлдон Э.
Коды, исправляющие ошибки

. —

М.
: Мир, 1976. — С.  596
.

Блейхут Р.

Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.

: Мир
, 1986. — 576 с.

Берлекэмп Э.

Алгебраическая теория кодирования

= Algebraic Coding Theory. —

М.

: Мир, 1971. — С.  478
.

Егоров С. И.
Коррекция ошибок в информационных каналах периферийных устройств ЭВМ. — Курск: КурскГТУ, 2008. — С. 252.

  • Сагалович Ю. Л.

    Введение в алгебраические коды
    — : МФТИ
    , 2007. — 262 с. — ISBN 978-5-7417-0191-1


  • Морелос-Сарагоса Р.

    Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева

    . — М.
    : Техносфера, 2006. — 320 с. — (Мир связи). —  — ISBN 5-94836-035-0
    .
  • М. Вернер.
    Основы кодирования. — Техносфера, 2004. — 288 с. — ISBN 5-94836-019-9
    .


    • Алгоритм декодирования по Хэммингу абсолютно идентичен алгоритму кодирования. Матрица преобразования соответствующей размерности умножается на матрицу-столбец кодового слова, и каждый элемент полученной матрицы-столбца берётся по модулю 2. Полученная матрица-столбец получила название «матрица синдромов». Легко проверить, что кодовое слово, сформированное в соответствии с алгоритмом, описанным в предыдущем разделе, всегда даёт нулевую матрицу синдромов.

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

    Заметим, что при однократной ошибке матрица синдромов всегда представляет собой двоичную запись (младший разряд в верхней строке) номера позиции, в которой произошла ошибка. В приведённом примере матрица синдромов (01100) соответствует двоичному числу 00110 или десятичному 6, откуда следует, что ошибка произошла в шестом бите.

    Сколько ошибок может исправить код?

    Чтобы код мог исправлять больше ошибок, окрестности должны быть как можно шире. С другой стороны, они не должны пересекаться. Иначе если точка попадёт в область пересечения, непонятно будет, к какой окрестности её отнести.

    В коде с удвоением между кодовыми словами $00$
    и $11$
    расстояние равно 2 (оба разряда различаются). А значит, если мы построим вокруг них шары радиуса 1, то они будут касаться. Это значит, точка касания будет принадлежать обоим шарам и непонятно будет, к какому из них её отнести.

    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    Именно это мы и получали. Мы видели, что есть ошибка, но не могли её исправить.

    Что интересно, точек касания в нашем странном пространстве у шаров две — это коды $01$
    и $10$
    . Расстояния от них до центров равны единице. Конечно же, в обычно геометрии такое невозможно, поэтому рисунки — это просто условность для более удобного рассуждения.

    В случае кода с утроением, между шарами будет зазор.

    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    Минимальный зазор между шарами равен 1, так как у нас расстояния всегда целые (ну не могут же две цепочки отличаться в полутора разрядах).

    В общем случае получаем следующее.

    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    Этот очевидный результат на самом деле очень важен. Он означает, что код с минимальным кодовым расстоянием $d_{\min}$
    будет успешно работать в канале с $k$
    ошибками, если выполняется соотношение

    $ d_{\min} \geqslant 2k+1. $

    Полученное равенство позволяет легко определить, сколько ошибок будет исправлять тот или иной код. А сколько код ошибок может обнаружить? Рассуждения такие же. Код обнаруживает $k$
    ошибок, если в результате не получится другое кодовое слово. То есть, кодовые слова не должны находиться в окрестностях радиуса $k$
    других кодовых слов. Математически это записывается так:

    $d_{\min}\geqslant k + 1.$

    Рассмотрим пример. Пусть мы кодируем 4 буквы следующим образом.

    $ \begin{aligned} A \to 10100,\\ B \to 01000,\\ C \to 00111,\\ D \to 11011.\\ \end{aligned} $

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

    Минимальное расстояние $d_{\min}=3$
    , а значит $3\geqslant2k+1$
    , откуда получаем, что такой код может исправить до $k=1$
    ошибок. Обнаруживает же он две ошибки.

    $ A \to 10100 \rightsquigarrow 101\underline{1}0. $

    Чтобы декодировать полученное сообщение, посмотрим, к какому символу оно ближе всего.

    $ \begin{aligned} A:\, d(10110, 10100) &= 1,\\ B:\, d(10110, 01000) &= 4,\\ C:\, d(10110, 00111) &= 2,\\ D:\, d(10110, 11011) &= 3. \end{aligned} $

    Минимальное расстояние получилось для символа $A$
    , значит вероятнее всего передавался именно он:

    $ A \to 10100 \rightsquigarrow 101\underline{1}0 \to A?. $

    Итак, этот код исправляет одну ошибку, как и код с утроением. Но он более эффективен, так как в отличие от кода с утроением здесь кодируется уже 4 символа.

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

    Для декодирования можно было бы использовать таблицу, в которой указывались бы все возможные принимаемые сообщения, и кодовые слова, которым они соответствуют. Но такая таблица получилась бы очень большой. Даже для нашего маленького кода, который выдаёт 5 двоичных цифр, получилось бы $2^5 = 32$
    варианта возможных принимаемых сообщений. Для более сложных кодов таблица будет значительно больше.

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

    Коды, исправляющие ошибки

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

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

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

    Основной принцип
    построения корректирующих кодов
    заключается в том, что в каждую
    передаваемую кодовую комбинацию,
    содержащую k
    информаци­онных двоичных символов,
    вводят р
    дополнительных двоичных
    символов. В результате получается новая
    кодовая комбинация, содержащая КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    двоичных символов. Такой код будем
    обозначать КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .
    Доля информационных символов в нем
    характеризуется относительной
    скоростью кода
    , определяе­мой
    соотношением

    Количество
    возможных кодовых комбинаций кода
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    равно КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .
    Из них передаваться могут КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    кодовых комбинаций, называемых
    разрешенными. Остальные КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    кодовые комбинации являются запрещенными.
    Появление одной из этих запрещенных
    комбинаций в приемной части означает,
    что имеется ошибка.

    Для оценки
    способности кода обнаруживать и
    исправлять ошибки использу­ется
    понятие кодового расстояния
    (расстояния Хемминга). Кодовое расстоя­ние КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    между кодовыми комбинациями КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    и КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    определяется как число дво­ичных
    разрядов, в которых эти комбинации
    различаются. Например, кодовое расстояние
    между кодовыми комбинациями 0001 и 0011
    равно 1, а между ком­бинациями 0000 и
    1111 равно 4.

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

    Одиночная ошибка
    переводит исходную кодовую комбинацию
    в кодовую комбинацию, отстоящую от нее
    на d
    = 1.
    Следовательно, для обнаружения одиночных
    ошибок необходимо, чтобы кодовое
    расстояние между любыми двумя разрешенными
    кодовыми комбинациями корректирующего
    кода было не менее 2. Для обнаружения r
    1
    ошибок в
    кодовой комбинации необходимо, чтобы
    кодовое расстояние между двумя
    разрешенными кодовыми комбинациями
    удовлетворяло неравенству КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .

    Один
    из самых простых и известных примеров
    помехоустойчивого кодиро­вания –
    проверка на четность. В каждую кодовую
    комбинацию вводится один дополнительный
    двоичный символ х
    р

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

    где
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    – двоичные символы исходной кодовой
    комбинации.

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

    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    Рис. 4.3.
    Схема
    обнаружения одной ошибки в кодовом
    слове

    ля исправления одиночных ошибок
    необходимо, чтобы кодовое расстояние
    между любыми двумя разрешенными кодовыми
    комбинациями корректирующе­го кода
    было не менее 3. В этом случае принятая
    запрещенная кодовая комби­нация
    заменяется ближайшей к ней разрешенной
    кодовой комбинацией. Так как ошибки
    одиночные, то переданная разрешенная
    кодовая комбинация от­стоит от
    принятой запрещенной кодовой комбинации
    на 1, а остальные разре­шенные кодовые
    комбинации – не менее чем на 2. В этом
    случае ошибка на­дежно исправляется.
    В общем случае для коррекции r
    2
    ошибок в кодовой ком­бинации кодовое
    расстояние d
    между
    любыми двумя разрешенными кодовыми
    комбинациями должно удовлетворять
    неравенству КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .

    Для увеличения
    кодового расстояния между разрешенными
    кодовыми ком­бинациями необходимо
    увеличивать число р
    контрольных
    символов в переда­ваемых кодовых
    комбинациях. Известно соотношение

    где
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    – минимальное кодовое расстояние между
    двумя разрешенными кодо­выми
    комбинациями. Чтобы при этом относительная
    скорость кода не стала чрезмерно малой,
    необходимо в соответствии с увеличивать
    и число k
    информационных
    символов в кодовой комбинации.

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

    Корректирующие коды

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

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

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

    Для корректирующих кодов справедливо
    неравенство

    N
    =
    K
    m


    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    M
    ,

    где М
    – количество сообщений; N
    – количество кодовых комбинаций; К
    – основание кода;

    m
    – длина кодовой
    комбинации: m
    =
    n

    +
    k
    ; n
    – число информационных разрядов, k
    – число контрольных разрядов,
    обеспечивающих локализацию и исправление
    искаженных элементов кодовой комбинации.

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

    + 1
    исходов. Используяkконтрольных разрядов необходимо
    различить все эти исходы. С помощьюkразрядов можно закодировать 2kисходов. Значит, должно выполняться
    условие

    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    Например, если М = 10
    , то в соответствии
    с равенством M
    =
    K
    n

    получаем
    n



    3,3 = 4
    . Чтобы иметь возможность
    обнаруживать ошибочные кодовые комбинации
    и исправлять их следует добавить k
    контрольных разрядов в соответствии с
    выражением:

    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ

    При выполнении равенства получим
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .
    Таким образом, чтобы проверить четыре
    информационных разряда, требуется три
    контрольных.

    При этом избыточность кода составит

    Коды обнаруживающие ошибки должны иметь
    кодовое расстояние d

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

    где α
    – кратность обнаруживаемых
    ошибок,

    β
    – кратность исправляемых ошибок,

    1
    – кодовое расстояние для оптимального
    кода;

    Рассмотрим эту формулу на примере
    равномерного трехразрядного кода.

    При α =
    0
    , β = 0
    d
    = 1
    . Этот результат
    соответствует равномерному оптимальному
    коду. Его кодовые комбинации: 000, 001,
    010, 100, 110, 101, 011, 111
    .

    При этом избыточность кода равна
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .

    При α = 1
    , β = 0
    d

    = 2
    . Этот результат соответствует
    равномерному коду, обнаруживающему
    однократную ошибку. Его кодовые
    комбинации: 001, 010, 101, 110
    .

    При этом избыточность кода равна
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .

    При α = 1
    , β = 1
    d

    = 3
    . Этот результат соответствует
    равномерному оптимальному коду. Его
    кодовые комбинации: 000, 111
    .

    При этом избыточность кода равна
    КОДЫ КОРРЕКТИРУЮЩИЕ ОШИБКУ
    .



    16-ричный (15,11) код Рида — Соломона

    Пусть



    . Тогда



    Степень



    равна 4,



    и



    . Каждому элементу поля <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba31478dec2e8a8edc32349ce92af6bdd8130976" aria-hidden="true" alt="{\mathrm {GF}}“>



    можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba31478dec2e8a8edc32349ce92af6bdd8130976" aria-hidden="true" alt="{\mathrm {GF}}“>



    , что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.


    8-ричный (7,3) код Рида — Соломона

    Пусть



    . Тогда



    Пусть информационный многочлен имеет вид:



    Кодовое слово несистематического кода запишется в виде:



    что представляет собой последовательность семи восьмеричных символов.


    Альтернативный метод кодирования 9-ричного (8,4) кода Рида — Соломона

    Построим поле Галуа




    по модулю многочлена



    . Пусть



    его корень, тогда



    , таблица поля имеет вид: 

            
  
      
        

     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bcca0afad428746479f16c125898f5381e3e7d56" aria-hidden="true" alt="{\displaystyle \alpha ^{0}=1=,}">  
  
      
        

       
  
      
        

     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93be24fee838862e916adba5c94346205d238bd1" aria-hidden="true" alt="{\displaystyle \alpha ^{2}=1+2\alpha =
    ,}">  
  
      
    
 
     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e3f3e9d3268ff366b9d4bea8e2fb2f847b8da37" aria-hidden="true" alt="{\displaystyle \alpha ^{3}=2+2\alpha =,}">  
  
      
        

     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/138dd563069d4deade2d4feaae233cbc1c771553" aria-hidden="true" alt="{\displaystyle \alpha ^{4}=2=<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bcca0afad428746479f16c125898f5381e3e7d56" aria-hidden="true" alt="{\displaystyle \alpha ^{0}=1=,}">,}">  
  
      
        

       
  
      
        

     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4c470b22055f2b9a4828bcb645fc14582d4d77e7" aria-hidden="true" alt="{\displaystyle \alpha ^{6}=2+\alpha =
    ,}">  
  
      
        

     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1c6f627ae36309d2d7b08a3c6bb6ff7eb9d50f21" aria-hidden="true" alt="{\displaystyle \alpha ^{7}=1+\alpha =.}">  
  
      
        

  
    

      Пусть информационный многочлен     
    
  
     
    
  
    
, далее производя соответствующие вычисления над построенным полем получим:
    
     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/38a0fc7bf6252f7966512cd334656f29a86ef77b" aria-hidden="true" alt="{\displaystyle a
    

    =\alpha ^{2},\ a(\alpha )=0,\ a(\alpha ^{2})=\alpha ^{6},\ a(\alpha ^{3})=0,\ a(\alpha ^{4})=\alpha ^{5},\ a(\alpha ^{5})=0,\ a(\alpha ^{6})=\alpha ^{7},\ a(\alpha ^{7})=1.}">
    
  
     
    
    
    

      Что же дальше?  
    

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

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

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

      Оценка эффективности кодов  
    

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

          
    
    Граница Хэмминга и совершенные коды  
    
  
    

      Пусть имеется двоичный блоковый     
    
  
     
    
  
    
 код с    корректирующей способностью  
    
     
    
  
     
    
  
    
.  Тогда справедливо неравенство (называемое границей Хэмминга):
  
    

    

          
    
  
     
    
      
  
    

    

      Коды, удовлетворяющие этой границе с равенством, называются совершенными.  К совершенным кодам относятся, например,    коды Хэмминга  
    
.  Часто применяемые на практике коды с большой    корректирующей способностью  
    
 (такие, как    коды Рида — Соломона  
    
) не являются совершенными.
  
    

          
    
  
    

      Пусть поле     
    
  
     
    
  
    
 генерируется примитивным элементом, неприводимый многочлен которого     
    
  
     
    
  
    
.  Тогда
    
     
    
  
     
    
  
    
.  Пусть     
    
  
     
    
  
    
.  Тогда порождающий многочлен кода РС равен
    
     
    
  
     
    
  
    
.  Пусть теперь принят многочлен     
    
  
     
    
  
    
.  Тогда     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c8a532a1aa309f5d447324e4fa4fc794459d5f97" aria-hidden="true" alt="{\displaystyle S_{1}=r
    

    =\alpha +\alpha ^{5}=\alpha ^{6},\ S_{2}=r(\alpha )=\alpha ^{5},\ S_{3}=\alpha ,\ S_{4}=\alpha }">
    
  
     
    
  
    
.  Тогда    ключевая система уравнений  
    
 получается в виде:
  
    

       
    
  
     
  
    

      Теперь рассмотрим    Евклидов алгоритм  
    
 решения этой системы уравнений.
  
    

      

    •      Начальные условия  
      
:  
      • 

    

            
  
      
        

       
  
      
        

  
    

            
  
      
        

       
  
      
        

       
  
      
        

     <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/75f64908816de8e0b6e50acb291a13b34579fa61" aria-hidden="true" alt="{\displaystyle b_{2}(x)=0+(\alpha ^{6}x+\alpha ^{6})
    =\alpha ^{6}x+\alpha ^{6};}">  
  
      
        

  
    

       
    
  
     
  
    

       
    
  
     
  
    

       
    
  
     
  
    

       
    
  
     
  
    

      Алгоритм останавливается, так как     
    
  
     
    
  
    
, отсюда следует, что     
    
  
     
    
        
    

      Далее полный перебор по алгоритму Чени выдает нам позиции ошибок, это     
    
  
     
    
  
    
.  Потом по формуле     
    
  
     
    
  
    
 получаем что     
    
  
     
    
        
    

      Код с утроением  
    

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

                                                                                                                      
    
                                                         
    
                                                                                                                  
    

                                                             Правда, это нам не очень поможет.  В самом деле, рассмотрим канал с одной возможной ошибкой:                                                                                                                
    

                                                                                                                                                                           
     
    
                                                        
    
                                                                                                                
    

                                                                                                                    Какие выводы мы можем сделать, когда получили                                                        
    

    ? Понятно, что раз у нас не две одинаковые цифры, то была ошибка, но вот в каком разряде? Может, в первом, и была передана буква                                                        
    

    
.  А может, во втором, и была передана                                                        
    

    .    
    

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

       $ \begin{aligned} A &\to 000,\\ B &\to 111. \end{aligned} $
    
  
     
  
    

      Проверим в деле:  
    

       $ A \to 000 \rightsquigarrow 0\underline{1}0 \to A?. $
    
  
     
  
    

      Получили  $010$
    
.  Тут у нас есть две возможности: либо это  $B$
    
 и было две ошибки (в крайних цифрах), либо это  $A$
    
 и была одна ошибка.  Вообще, вероятность одной ошибки выше вероятности двух ошибок, так что самым правдоподобным будет предположение о том, что передавалась именно буква  $A$
    
.  Хотя правдоподобное — не значит истинное, поэтому рядом и стоит вопросительный знак.    
    

      Если в канале связи возможна максимум одна ошибка, то первое предположение о двух ошибках становится невозможным и остаётся только один вариант — передавалась буква  $A$
    
.    
    

      Про такой код говорят, что он исправляет одну ошибку.  Две он тоже обнаружит, но исправит уже неверно.    
    

      Это, конечно, самый простой код.  Кодировать легко, да и декодировать тоже.  Ноликов больше — значит передавался ноль, единичек — значит единица.    
    

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

      
    

          
    
  
    

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

      Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования.  Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняя строка, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова.  В каждом столбце матрицы преобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный — младший бит расположим в верхней строке, старший — в нижней.  Например, в третьем столбце матрицы будут стоять числа 11000, что соответствует двоичной записи числа три: 00011.
  
    

      В правой части таблицы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов.  Вычисление контрольных битов производим следующим образом: берём одну из строк матрицы преобразования (например,     
    
  
     
    
  
    
) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений.  Если сумма получилась больше единицы, находим остаток от его деления на 2.  Иными словами, мы подсчитываем, сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы, и берём это число по модулю 2.
  
    

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

      Например, для строки     
    
  
     
    
  
    
:
  
    

    

          
    
  
     
    
  
    
 = (1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·1+0·1+1·1+0·0+1·0+0·0+1·0+0·1) mod 2 = 5 mod 2 = 1.    
    

    

      Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей.  По аналогии находим проверочные биты в остальных строках.  Кодирование по Хэммингу завершено.  Полученное кодовое слово — 11110010001011110001.
  
    

          
    
  
    

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

      Кодирование  
    

      Итак, у нас есть система для проверки  
    

       $ \left\{ \begin{aligned} x_1 + x_2 &= 0,\\ x_2 + x_3 &= 0. \end{aligned} \right. $
    
  
     
  
    

      Её решения — это кодовые слова.  Собственно, мы систему и строили на основе кодовых слов.  Попробуем теперь решить обратную задачу.  По системе (или, что то же самое, по матрице  $H$
    
) найдём кодовые слова.    
    

      Правда, для нашей системы мы уже знаем ответ, поэтому, чтобы было интересно, возьмём другую матрицу:  
    

       $ H = \begin{pmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}. $
    
  
     
  
    

      Соответствующая система имеет вид:  
    

       $ \left\{ \begin{aligned} x_1 + x_3 &= 0,\\ x_2 + x_3 + x_5 &= 0,\\ x_4 + x_5 &= 0. \end{aligned} \right. $
    
  
     
  
    

      Чтобы найти кодовые слова соответствующего кода нужно её решить.    
    

      В силу линейности сумма двух решений системы тоже будет решением системы.  Это легко доказать.  Если  $a$
    
 и  $b$
    
 — решения системы, то для их суммы верно  
    

       $H(a+b)^T=Ha^T+Hb^T=0+0=0,$
    
  
     
  
    

      что означает, что она тоже — решение.    
    

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

      Выразим сперва все зависимые слагаемые.  Их столько же, сколько и уравнений.  Выражать надо так, чтобы справа были только независимые.  Проще всего выразить  $x_1, x_2, x_4$
    
.    
    

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

     он тоже работает.    
    

       $ \left\{ \begin{aligned} x_1 &= x_3,\\ x_2 &= x_3 + x_5,\\ x_4 &= x_5. \end{aligned} \right. $
    
  
     
  
    

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

       <img src="https://habrastorage.org/getpro/habr/post_images/f26/b2b/c9a/f26b2bc9a9ab9a6d14d51a378653c01f.svg" alt="$ \begin{aligned} x_3=1, x_5=0:\quad x_1=1, x_2=1, x_4=0 \Rightarrow x^{
    

    } = (1, 1, 1, 0, 0),\\ x_3=0, x_5=1:\quad x_1=0, x_2=1, x_4=1 \Rightarrow x^{
    

    } = (0, 1, 0, 1, 1). \end{aligned} $" data-tex="display">
    
  
     
  
    

      Всевозможные суммы этих независимых решений (а именно они и будут кодовыми векторами) можно получить так:  
    

       <img src="https://habrastorage.org/getpro/habr/post_images/4de/caf/d26/4decafd26623b55fecc3e410989a2f5d.svg" alt="$ a_1 x^{
    

    }+a_2 x^{
    

    }, $" data-tex="display">
    
  
     
  
    

      где  $a_1, a_2$
    
 равны либо нулю или единице.  Так как таких коэффициентов два, то всего возможно  $2^2=4$
    
 сочетания.    
    

      Но посмотрите! Формула, которую мы только что получили — это же снова умножение матрицы на вектор.    
    

       $ (a_1, a_2)\cdot \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} = aG. $
    
  
     
  
    

      Строчки здесь — линейно независимые решения, которые мы получили.  Матрица  $G$
    
 называется порождающей.  Теперь вместо того, чтобы сами составлять таблицу кодирования, мы можем получать кодовые слова простым умножением на матрицу:  
    

       $ a \to aG. $
    
  
     
  
    

      Найдём кодовые слова для этого кода.  ( Не забываем, что длина исходных сообщений должна быть равна 2 — это количество найденных решений.)  
    

       $ \begin{aligned} 00 &\to 00000,\\ 01 &\to 01011,\\ 10 &\to 11100,\\ 11 &\to 10111. \end{aligned} $
    
  
     
  
    

      Итак, у нас есть готовый код, обнаруживающий ошибки.  Проверим его в деле.  Пусть мы хотим отправить 01 и у нас произошла ошибка при передаче.  Обнаружит ли её код?  
    

       <img src="https://habrastorage.org/getpro/habr/post_images/c65/e4a/4da/c65e4a4da6a38487d63d74f66f7bf647.svg" alt="$ a=01 \to aG=01011 \rightsquigarrow x=01\underline{1}11 \to Hx^T = 
    

  • ^T \neq 0. $" data-tex="display">
    
  
     
  
    

      А раз в результате не нулевой вектор, значит код заподозрил неладное.  Провести его не удалось.  Ура, код работает!  
    

      Для кода с утроением, кстати, порождающая матрица выглядит очень просто:  
    

       $G=\begin{pmatrix}1&1&1\end{pmatrix}.$
    
  
     
  
    

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

      
    

          
    
  
    

      

    •      Питерсон У., Уэлдон Э.    
      
 Коды, исправляющие ошибки: Пер.  с англ.  М.: Мир, 1976, 594 c.    
      • 

    •      Пенин П. Е., Филиппов М. Р.    
      
 Радиотехнические системы передачи информации.  М.: Радио и Связь, 1984, 256 с.    
      • 

    •      Блейхут Р.    
      
 Теория и практика кодов, контролирующих ошибки.  Пер.  с англ.  М.: Мир, 1986, 576 с.    
      • 

    

          
    
  
    

      

    •      Могущество кодов Рида — Соломона или информация, воскресшая из пепла (статья Криса Касперски)  
  
      • 

    •      Помехоустойчивое кодирование в пакетных сетях (статья В.  Варгаузина)  
  
      • 

    •      Error Correcting Code (ECC)  
  
      • 

    •      CD-R диски, технология изнутри  
  
      • 

    •      Формат CD  
  
      • 

    •      Коды Рида-Соломона  
  
      • 

    •      wiki.linuxformat.ru/wiki/LXF134:par2  
      
 — использование    par2  
      
, утилиты восстановления файлов методом Кода Рида-Соломона     (рус.)  
  
      •

    • Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    ➤