Любой циклический (n, k ) – код может быть задан в соответствии с определением 2, порождающим многочленом g(x) или проверочным многочленом .
Знание этих многочленов позволяет построить порождающую матрицу и матрицу проверок. Для циклического (n, k ) – кода существует простой способ нахождения k линейно независимых кодовых комбинаций, образующих порождающую матрицу . Этот способ состоит в следующем. Записывается порождающий многочлен g(x) . В соответствии с определением 2 комбинация, соответствующая порождающему многочлену, принадлежит циклическому (n, k ) – коду. В соответствии с определением 1 циклические сдвиги комбинации, соответствующей g(x) , также должны принадлежать этому же коду. Алгебраически сдвиг соответствует умножению кодовой комбинации на х . Так как степень g(x) равна n-k , то подобным образом мы можем получить кодовые комбинации
Легко проверить, что эти кодовые комбинации линейно независимы, хотя бы потому, что степени всех этих многочленов различны, поэтому данный набор многочленов может быть использован в качестве :
.
Путем элементарных преобразований эта матрица может быть приведена к канонической форме.
Аналогичным образом по проверочному многочлену можно построить матрицу проверок
.
Пример 6.4. Для циклического (7,4) – кода с порождающим многочленом 
(см. пример 6.3.) построить порождающую матрицу.
Следовательно, порождающая матрица для данного кода имеет вид:
Полученные результаты и рассуждения относительно алгебраической структуры циклических кодов, приведенные в разделе 6.2, позволяют подметить одно важное свойство циклических кодов, определенное их циклической структурой.
Свойство 6.1. Произведение кодовой комбинации циклического кода на произвольный многочлен дает кодовую комбинацию этого же циклического кода.
Действительно , а любое произведение такого вида равно нулю, т.е. принадлежит кодовому подпространству (раздел 6.2).
Более элементарное доказательство:
Полученная сумма есть сумма циклических сдвигов кодовых комбинаций, что по свойству замкнутости группового кода должно дать комбинацию того же циклического кода.
При описании циклических кодов следует учитывать специфику действий над многочленами, по сравнению с векторами и, в частности, тот факт, что умножение многочленов не совпадает со скалярным умножением векторов, отображающих эти многочлены. Однако в классе вычетов многочленов по модулю между этими понятиями существует весьма тесная связь. Пусть имеется вектор и соответствующий ему многочлен , а также вектор и соответствующий ему многочлен . Будем считать многочлены и ортогональными, если выполнено условие .
Коэффициент при х
в произведении 
равен
Слагаемые, содержащие , появляются вследствие слагаемых в произведении , которые содержат . Но так как , т.е. , то . Равенство для можно представить в виде скалярного произведения:
В этом произведении первый вектор соответствует а(х) . Второй вектор содержит коэффициенты b(х) , расположенные в обратном порядке и сдвинутые циклически на j +1 элемент вправо.
Таким образом, если произведение равно нулю, то вектор, соответствующий многочлену а(х) , ортогонален вектору, соответствующему многочлену b(х) , компоненты которого расположены в обратном порядке, и кроме того каждому циклическому сдвигу этого вектора. Верно также и обратное утверждение. Если вектор ортогонален вектору и каждому циклическому сдвигу этого вектора, то
Учитывая эту специфику необходимо при матричном описании кода коэффициенты матрицы проверок записывать в обратном порядке. В этом случае будет выполнено условие
Пример 6.5. Построить матрицу проверок для циклического (7,4) – кода из предыдущего примера.m , являющихся сомножителями двучленов и не являющихся сомножителями никаких двучленов меньшей степени. Корни этих многочленов имеют порядок 2 m -1, т.е они являются примитивными элементами поля GF(2 m). Это означает, что порождающий многочлен кода Хэмминга порождает поле GF(2 m).
Условимся в любом циклическом коде первые n-k
элементов кодовой комбинации, то есть коэффициенты при 
использовать в качестве проверочных элементов, а последние k
элементов, то есть коэффициенты при 
, - в качестве информационных (рис. 6.0).
a 0 a, ….., a n-1 = a 0 x 0 +a 1 x 1 + …. + a n-1 x n+1
x 0 x 1 x 2 x n-k-1 x n-k x n-2 x n-1
Пусть x1, x2, ..., xk означают слово из k информационных битов на входе кодера, кодируемое в кодовое слово C размерности n битов:
вход кодера: X =[x 1, x 2, ...,xk ]
выход кодера: C =[c 1, c 2, ..., cn ]
Пусть задана специальная порождающая матрица G n , k ,
задающая блочный код (n ,k ).
Строки матрицы G n , k должны быть линейно независимы.
Тогда разрешенная кодовая комбинация C , соответствующая кодируемому слову X :
C =x 1 g 1 + x 2 g 2 + ... + x k g k .
Систематическая (каноническая) форма порождающей матрицы G размером k xn :
Порождающая матрица систематического кода создает линейный блочный код, в котором первые k битов любого кодового слова идентичны информационным битам, а остальные r =n -k битов любого кодового слова являются линейными комбинациями k информационных битов.
Проверочная матрица H n , k имеет r xn элементов, причем справедливо:
C xH T = 0.
Это выражение используется для проверки полученной кодовой комбинации. Если равенство нулю не выполняется, то получаем матрицу-строку ||c 1 , c 2 , ..., c r ||, называемую синдромом ошибки.
Код Хэмминга. Корректирующая и обнаруживающая способности. Правила выбора соотношения между длиной кодового слова и числом информационных битов. Формирование порождающей и проверочной матриц кода Хэмминга. Толкование синдрома ошибки
Рассмотрим код Хэмминга с кодовым расстоянием d =3, позволяющий исправлять одиночные ошибки (d =2q max +1).
Число разрешенных кодовых комбинаций для кода с d =3, для кода Хэмминга строго равно 2 n /(n +1). Первые k разрядов кодовых комбинаций кода используются в качестве информационных и их число равно
k = log 2 (2 n /(n +1)] = n – log 2 (n +1).
Данное уравнение имеет целочисленные решения k = 0, 1, 4, 11, 26, которые и определяют соответствующие коды Хэмминга: (3,1)-код, (7,4)-код, (15,11)-код и т.д. (всегда n =2 w ‑1).
Проверочная матрица H кода Хэмминга (r =n-k строк и n столбцов): для двоичного (n,k)-кода n=2 w -1 столбцов состоят из всех возможных двоичных векторов с r=n-k элементами, исключая вектор со всеми нулевыми элементами .
Легко проверить, что G xH T = 0 (нулевая матрица размером k xr элементов).
Пример. Проверим работу кода при передаче сообщения X =1011. Передаваемая кодовая комбинация будет сформирована в виде линейной комбинации (сложения по модулю 2) строк № 1, 3, 4 матрицы G 7,4:
Предположим, что на передаваемое кодовое слово C воздействовала ошибка 0000100, что привело к получению на приемной стороне слова C "=10111 10.
Тогда при перемножении C" на проверочную матрицу H T получаемматрицу-строку синдрома ошибки, которая соответствует тому столбцу проверочной матрицыH с номером бита, содержащего ошибку.
Сравнивая полученный синдром со строками H T , получаем, что ошибочен бит № 5 слева.
Декодер Хэмминга может работать в двух взаимоисключающих режимах:
Режим исправления (коррекции) ошибок (т.к. d min =3, то он позволяет исправлять одиночные ошибки);
Режим обнаружения ошибок (т.к. d min =3, то он обнаруживает ошибки кратности q £2). Если синдром не равен 0, то декодер выдает сигнал ошибки.
Если в принятом кодовом слове имеются 2 ошибки, а декодер работает в режиме коррекции, то он не сможет по синдрому определить, произошла ли одна ошибка или две, и выполнит неправильную коррекцию кодового слова.
Расширенный код Хэмминга. Режимы работы декодера, корректирующая и обнаруживающая способности. Формирование кодового слова. Формирование проверочной матрицы расширенного кода Хэмминга. Толкование синдрома ошибки
Расширение кода Хэмминга заключается в дополнении кодовых векторов дополнительным двоичным разрядом таким образом, чтобы число единиц, содержащихся в каждом кодовом слове, было четным. Благодаря этом коды Хэмминга с проверкой на четность обладают следующими преимуществами:
Длины кодов увеличиваются с 2 w -1 до 2 w , что удобно с точки зрения передачи и хранения информации;
Минимальное расстояние d min расширенных кодов Хэмминга равно 4, что дает возможность обнаруживать (!) 3-кратные ошибки.
Дополнительный разряд проверки на четность позволяет использовать декодер в новом гибридном режиме – обнаружения и коррекции ошибок.
Рассмотрим расширение (7,4,3)-кода Хэмминга.
Каждый кодовый вектор C a получается из кодового вектораc путем добавления дополнительного разряда проверки на четностьC a = (c 1 , ..., c 7, c 8), где .
Проверочная матрица H (8,4)-кода получается из проверочной матрицы (7,4)-кода в два приема:
К матрице (7,4)-кода дописывается нулевой столбец;
Полученная матрица дополняется строкой, полностью состоящей из одних единиц.
Получаем:
При синдромном декодировании
s " = C "ÄH T ,
причем все компоненты s" должны быть равны 0.
При одиночной ошибке s"(4) = 1. По значению синдрома (младшие 3 бита) находим и исправляем (инвертируем) ошибочный бит.
При двойной ошибке компонента s"(4)= 0, а синдром отличен от нуля. В отличие от стандартного кода Хемминга такая ситуация ужеобнаруживается , но не исправляется (передается запрос на повторную передачу слова и т.п.).
Таким образом, расширенный декодер Хэмминга может использоваться в одном из двух взаимоисключающих режимах:
Для исправления однократных и обнаружения двукратных ошибок;
Для обнаружения трехкратных ошибок.
Введение
Описание процесса цифровой связи
Источник выдает сообщение, представляющее в общем случае некоторый электрический сигнал. Этот сигнал преобразуется в цифровую форму, которая является удобной для дальнейшей обработки.
Далее производится сжатие информации (кодирование источника), минимизирующее избыточность сообщения. Кодирование источника снижает затраты на передачу и хранение информации. После этого сообщение должно быть передано по зашумленному каналу. Для того чтобы сообщение дошло до потребителя в неискаженном виде, используется помехоустойчивое кодирование информации (кодирование канала). На стороне потребителя информация декодируется. Декодер канала исправляет ошибки в принятом слове, а декодер источника преобразует исправленное слово в форму, удобную потребителю.
Говоря о кодах, контролирующих ошибки, следует различать две стратегии их использования.
- Непосредственное исправление ошибок за счет избыточности (Forward Error Correction — FEC).
- Обнаружение ошибок с последующими запросами на повторную передачу ошибочно принятой информации (Automatic Repeat Request — ARQ).
При выборе методов кодирования и декодирования руководствуются многими факторами, взаимосвязь которых представлена на рисунке.
В общую сложность входят аппаратные и программные затраты на реализацию кодера и декодера, стоимость хранения и передачи информации и т. д. Интенсивность потока данных включает в себя передачу полезной информации, проверочных разрядов, а также запросов и повторений по этим запросам отдельных информационных блоков.
Помехоустойчивое кодирование
Общие сведения
Реальные системы передачи данных не совершенны. Применяя информационную технику, мы должны учитывать возможность возникновения ошибок при передаче и хранении информации. Это в первую очередь относится к
- хранению информации на носителях с высокой плотностью записи (магнитные носители, CD-ROM, DVD);
- передаче данных при ограниченной мощности сигнала (спутниковая и мобильная связь);
- передаче информации по сильно зашумленным каналам (мобильная связь, высокоскоростные проводные линии связи);
- каналам связи с повышенными требованиями к надежности информации (вычислительные сети, линии передачи со сжатием данных).
Во всех вышеперечисленных случаях используются коды, контролирующие ошибки.
Рассмотрим простейшую модель передачи данных с применением помехоустойчивого кодирования.
Пусть кодер источника последовательно выдает информационные слова фиксированной длины. Кодер канала заменяет каждое информационное слово u кодовым словом v . Передатчик генерирует сигналы, соответствующие кодовому слову v и посылает их в канал. Приемник производит обратное преобразование, в результате которого на декодер поступает двоичное принятое слово r . Декодер сравнивает принятое слово r со всеми возможными кодовыми словами используемого кода. Если слово r совпадает с одним из кодовых слов, то соответствующее информационное слово и выдается потребителю. Если r отличается от всех кодовых слов, то в канале произошла обнаруживаемая ошибка. Целью применения кодирования канала является достижение совпадения переданного информационного слова u и принятого информационного слова u ′.
Из данного описания можно сделать 2 вывода:
- Если в процессе передачи по зашумленному каналу кодовое слово отобразится в другое кодовое слово, не совпадающее с переданным, то происходит необнаруживаемая ошибка. Назовем ее остаточной ошибкой декодирования.
- Требуется построить коды, обладающие некоторой математической структурой, которая позволяет эффективно распознать, а в некоторых случаях и исправлять ошибки, возникающие при передаче информации по каналу связи.
Линейные блоковые коды
Важное семейство кодов образуют линейные двоичные блоковые коды. Эти коды замечательны тем, что, представляя информационные и кодовые слова в форме двоичных векторов, мы можем описать процессы кодирования и декодирования с помощью аппарата линейной алгебры. При этом компонентами вводимых векторов и матриц являются символы 0 и 1. Операции над двоичными компонентами производятся по правилам арифметики по модулю 2 .
Наиболее известным линейным кодом является блоковый код Хэмминга. Далее описание линейных блоковых кодов будет производиться на примере этого кода. В частности, будет рассмотрен (7,4)-код Хэмминга.
Кодер двоичного блокового (n , k)-кода отображает множество 2 k возможных двоичных информационных слов в множество 2 k n -мерных кодовых слов. В теории кодирования между этими множествами всегда существует взаимно однозначное соответствие.
Вместо k бит информационного вектора в канал передается n бит кодового вектора. В этом случае говорят об избыточном кодировании со скоростью: R = n ⁄ k .
Чем ниже скорость, тем больше избыточность кода, и тем большими возможностями для защиты от ошибок он обладает. Однако, следует учитывать, что с увеличением избыточности затраты на передачу информацию также возрастают.
Описание процессов кодирования и декодирования
Исходным материалом для построения кодовых конструкций служит n -мерное двоичное векторное пространство, в котором заданы операции арифметики по модулю 2. В него вложено k -мерное линейное пространство, содержащее 2 k кодовых слов. Код С образуется с помощью 2 k комбинаций k линейно независимых базисных векторов { g 1 ,…, g k }.
Эти векторы образуют строки порождающей матрицы кода С.
Для кода C существует дуальный код C d такой, что скалярное произведение любой пары векторов, один из которых принадлежит пространству С, а другой — пространству C d , всегда равно нулю. Это значит, что векторы кода С d ортогональны векторам кода С. С другой стороны, если некоторый вектор ортогонален всем векторам кода С, то он принадлежит коду С d и наоборот. Дуальное векторное подпространство «натянуто» на n − k линейно независимые базисные векторы { h 1 ,…, h n − k }. Эти векторы образуют строки проверочной матрицы.
Рассмотрим пример порождающей и проверочной матриц (7,4)-кода Хэмминга:
 |
 |
Следует отметить важное свойство: как в порождающей, так и в проверочной матрице присутствует единичная матрица. Это свойство используется в процессах кодирования и декодирования.
Кодирование
Кодовое слово v и информационное слово u связаны соотношением:
где G — порождающая матрица, структура которой была описана выше.
Например, информационный вектор u = (1010) отобразится в кодовый вектор следующим образом:
Легко заметить, что последние четыре разряда кодового вектора совпадают с информационным вектором. Это свойство называется систематичностью кода.
Коды, в которых информационное слово может быть непосредственно выделено из соответствующего ему кодового вектора, называются систематическими. Порождающую матрицу любого систематического кода всегда можно путем перестановки столбцов привести к виду:
G k × n = (P k ×(n − k) I k),
где I k — единичная матрица размерности k × k .
Таким образом, в кодовом векторе систематического кода всегда можно выделить информационные и проверочные символы.
Роль проверочных символов и их использование будут подробно разъяснены ниже.
Декодирование
Задача декодера заключается в том, чтобы, используя структуру кода, по принятому слову r , восстановить переданный информационный вектор. Для рассмотренного выше (7, 4)-кода Хэмминга можно предложить следующий алгоритм обнаружения ошибок. Так как рассматриваемый код является систематическим, выразим каждый из трех проверочных символов через символы информационного вектора:
V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6
Если в канале произошла ошибка, то в принятом векторе r хотя бы одно из равенств не будет выполняться. Запишем полученные проверочные соотношения в виде системы уравнений для компонент вектора r:
R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2
Таким образом, из первых трех столбцов порождающей матрицы G мы получили систему трех проверочных уравнений. Если в полученной системе уравнений хотя бы одна из компонент { s 0 , s 1 , s 2 } не равна нулю, то в канале произошла ошибка.
Запишем систему проверочных уравнений в общем виде. Для любого систематического кода с порождающей матрицей G , проверочная матрица определяется следующим образом:
H (n − k)× n = (I n − k P T k ×(n − k)).
Тогда систему проверочных уравнений можно записать в виде
Вектор s принято называть синдромом. Таким образом, ошибка будет обнаружена, если хотя бы одна из компонент s не равна нулю.
В качестве примера рассмотрим синдромное декодирование (7, 4)-кода Хэмминга. При передаче информационного слова u = (1010) по каналу без шума r = v = (0011010) . Можем убедиться, что в этом случае синдром равен 0 .
Если, например, в кодовом слове произошла одиночная ошибка на четвертой позиции (r = (0010010)), то синдромом является четвертая строка транспонированной проверочной матрицы.
Перебрав все возможные позиции одиночной ошибки, получим полную таблицу синдромов однократных ошибок — таблицу соответствий номера ошибочного разряда получающемуся при этом синдрому.
| Ошибочный разряд | r 0 | r 1 | r 2 | r 3 | r 4 | r 5 | r 6 |
|---|---|---|---|---|---|---|---|
| Синдром s | 100 | 010 | 001 | 110 | 011 | 111 | 101 |
Можно заметить, что ошибке в i -ой позиции кодового слова соответствует синдром, образованный i -ым столбцом матрицы Н. Так как все столбцы матрицы различны, мы можем с помощью таблицы синдромов исправлять одиночную ошибку, вносимую каналом.
Разновидности ошибок
У линейных блоковых кодов имеются 3 разновидности ошибок:
- Распознаваемая и исправляемая ошибка
- Синдром присутствует в таблице синдромов
- Декодер распознает и исправляет ошибку, а затем передает на приемник корректное слово
- Распознаваемая ошибка
- Принятое слово не соответствует ни одному из кодовых слов
- Синдром не присутствует в таблице синдромов
- Декодер распознает ошибку и посылает запрос на повторную передачу информационного слова.
- Нераспознаваемая ошибка
- Принятое слово соответствует одному из кодовых слов (не соответствующему исходному кодовому слову)
- Синдром равен 0
- Декодер не распознает ошибку и выдает потребителю ошибочное информационное сообщение
Заключение
Следует отметить, что эффективность конкретного кода зависит от области его применения и, в особенности, от канала связи. Если в канале отношение сигнал/шум достаточно велико, то вероятность одиночной ошибки во много раз превышает вероятность ошибок высших кратностей, поэтому, использование в таком канале кода Хэмминга с исправлением однократной ошибки может оказаться весьма эффективным. С другой стороны, в каналах, где преобладают многократные ошибки (например, в каналах с замираниями), исправление одиночных ошибок лишено смысла. При практическом выборе конкретного помехоустойчивого кода необходимо также учитывать скорость его декодирования и сложность технической реализации.
Литература
- Вернер М. Основы кодирования . — М.: Техносфера, 2004.
- Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
Олег Рыбак
Действительно с трудом можно найти адекватное объяснение. Чаще всего авторы предполагают, что читателю многое известно заранее и не стремятся пояснять, казалось бы простые моменты, в которых заключена суть. Очень рад, что наткнулся на данный материал, кое-что для себя прояснил.
Линейные коды обладают следующим свойством:
Из всего множества 2 k разрешенных кодовых слов, образующих линейную группу, можно выделить подмножества из k слов, обладающих свойством линейной независимости.
Линейная независимость означает, что никакое из слов, входящих в подмножество линейно-независимых кодовых слов, нельзя получить путем суммирования (с помощью линейного выражения) любых других слов, входящих в это подмножество.
В то же время любое из разрешенных кодовых слов можно получить путем суммирования определенных линейно-независимых слов.
Таким образом, построение кодовых комбинаций линейного кода связано с линейными операциями. Для выполнения таких операций удобно пользоваться хорошо разработанным аппаратом матричных вычислений.
Для образования n -разрядных кодовых слов из k- разрядных кодируемых слов (кодирования) используют матрицу, которая называется образующей(порождающей).
Образующая матрица получается путем записи в столбец k линейно-независимых слов.
Обозначим кодируемую информационную последовательность X и будем записывать ее в виде матрицы-строки ||X|| размерностью 1* k , например:
||X||=||11001||, где k=5 .
Один из способов построения образующей (порождающей) матрицы следующий: Она строится из единичной матрицы ||I|| размерностью k*k и приписанной к ней справа матрицы добавочных (избыточных) разрядов ||МДР|| размерности k*r .
где при k =4
Такая структура ОМ обеспечивает получение систематического кода.
Порядок построения матрицы МДР будет рассмотрен ниже.
7.4 Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||Х|| на образующую матрицу ||ОМ||:
Умножение выполняется по правилам матричного умножения: (ТАК наТАК)
Надо только помнить, что сложение здесь ведется по модулю 2.
допустим, образующая матрица
||ОМ||= 0010 011
и вектор-строка информационной последовательности
Так как множимая матрица имеет всего одну строку, умножение упрощается. В этом случае следует поставить в соответствие строкам образующей(порождающей) матрицы ||ОМ|| разряды матрицы информационной последовательности ||X|| и сложить те строки образующей(порождающей) матрицы, которые соответствуют единичным разрядам матрицы ||Х||.
Заметим, что ||KC|| = ||X, ДР||,
где ||X||- информационная последовательность (т.к. умножается на единичную матрицу ||I|| ),
а ||ДР|| - добавочные разряды, зависящие от матрицы добавочных разрядов ||МДР|| :
|| ДР ||= || Х || * || МДР||
7.5 Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Искажение можно описать с помощью следующей формулы:
|| ПКС || = ||КС || + ||ВО ||,
где ||ВО|| - вектор ошибки - матрица-строка размерностью 1* n , с 1 в тех позициях, в которых произошли искажения.
Декодирование основано на нахождении так называемого опознавателя или синдрома ошибки -матрицы-строки ||ОП|| длиной r разрядов (r - количество добавочных или избыточных разрядов в кодовом слове).
Опознаватель используется для нахождения предполагаемого вектора ошибки.
Опознаватель находят по следующей формуле:
||ОП|| = ||ПКС||* ||ТПМ||,
где ||ПКС||- принятое и, возможно, искаженное кодовое слово;
||ТПМ||,- транспонированная проверочная матрица, которая получается из матрицы добавочных разрядов ||МДР|| путем приписывания к ней снизу единичной матрицы:
Пример ||ТПМ||:
Поскольку ||ПКС|| = ||КС|| + ||BO||, последнюю формулу можно записать в виде:
||ОП|| = ||КС|| * ||ТПМ||+||ВО|| * ||ТПМ||.
Рассмотрим первое слагаемое.
||КC|| - матрица-строка, причем первые k разрядов - информационные.
Докажем теперь, что произведение кодового слова ||КС|| на ||ТПМ|| приводит к получению нулевой матрицы ||0||.
Поскольку ||КС|| - матрица-строка, возможен упрощенный порядок умножения матриц, рассмотренных выше.
Следовательно, первое слагаемое в
||ОП|| = ||КС|| * ||ТПМ|| + ||ВО|| * ||ТПМ||
всегда равно нулю и опознаватель полностью зависит от вектора ошибки ||ВО||.
Если теперь подобрать такую проверочную матрицу ТПМ , а значит и МДР , чтобы разным векторам ошибки соответствовали разные опознаватели ОП, то по этим опознавателям можно будет находить вектор ошибки ВО, а значит и исправлять эти ошибки.
Соответствие опознавателей векторам ошибки находится заранее путем перемножения векторов исправляемых ошибок на ТПМ;
Таким ооразом, способность кода исправлять ошибки целиком определяется ||МДР||. Для построения МДР для кодов, исправляющих однократные ошибки нужно в каждой строке МДР иметь не менее 2-х единиц. При этом также необходимо иметь хотя бы одно различие между двумя любыми строчками МДР .
Полученный нами код неудобен тем, что опознаватель, хотя и связан однозначно с номером искаженного разряда, как число не равен ему. Для поиска искаженного разряда нужно использовать дополнительную таблицу соответствия между опознавателем и этим номером. Коды, в которых опознаватель как число определяет позицию искаженного разряда, были найдены и получили название кодов Хэмминга .
Построение МДР для случая исправления многократных ошибок значительно усложняется. Разными авторами были найдены различные алгоритмы построения ||МДР || для этого случая, а соответствующие коды называются именами их авторов.
В системах связи возможны несколько стратегий борьбы с ошибками:
- обнаружение ошибок в блоках данных и автоматический запрос повторной передачи поврежденных блоков - этот подход применяется в основном на канальном и транспортном уровнях;
- обнаружение ошибок в блоках данных и отбрасывание поврежденных блоков - такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
- исправление ошибок (англ. forward error correction ) применяется на физическом уровне.
Коды обнаружения и исправления ошибок
Корректирующие коды - коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех , а также при её хранении.
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
С кодами, исправляющими ошибки , тесно связаны коды обнаружения ошибок . В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.
В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).
По способу работы с данными коды, исправляющие ошибки делятся на блоковые , делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и сверточные , работающие с данными как с непрерывным потоком.
Блоковые коды
Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают (n ,k ) . При этом число называется скоростью кода .
Если исходные k бит код оставляет неизменными, и добавляет n − k проверочных , такой код называется систематическим , иначе несистематическим .
Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из k информационных бит сопоставляется n бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:
- способность исправлять как можно большее число ошибок,
- как можно меньшая избыточность,
- простота кодирования и декодирования.
Нетрудно видеть, что приведенные требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.
Практически все используемые коды являются линейными . Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую легкость кодирования и декодирования.
Линейные пространства
Порождающая матрица
Это соотношение устанавливает связь между векторами коэффициентов 
и векторами . Перечисляя все векторы коэффициентов можно получить все векторы . Иными словами, матрица G
порождает линейное пространство .
Проверочная матрица
Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G , называемую порождающей матрицей .
Пусть - ортогональное подпространство по отношению к C , а H - матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:
.
Свойства и важные теоремы
Минимальное расстояние и корректирующая способность
Коды Рида-Соломона
Преимущества и недостатки линейных кодов
Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок , их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока. Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
Оценка эффективности
Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).
Граница Хемминга и совершенные коды
Пусть имеется двоичный блоковый (n ,k ) код с корректирующей способностью t . Тогда справедливо неравенство (называемое границей Хемминга ):
.
Коды, удовлетворяющие этой границе с равенством, называются совершенными . К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.
Энергетический выигрыш
При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определенных системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.
Wikimedia Foundation Википедия
Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Циклический код … Википедия
Циклический код линейный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и… … Википедия
В области математики и теории информации линейный код это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы… … Википедия
- (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передаче информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью является малая плотность значимых… … Википедия
Код с малой плотностью проверок на чётность (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передачи информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью… … Википедия
структура - (framework): Логическая структура для классификации и организации сложной информации .
