Первая страница / Теория / Кодирование /

Линейные блоковые коды

Голосование: 28, 5

Введение

Описание процесса цифровой связи

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

Модель передачи информации

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

Говоря о кодах, контролирующих ошибки, следует различать две стратегии их использования.

  1. Непосредственное исправление ошибок за счет избыточности (Forward Error Correction — FEC).
  2. Обнаружение ошибок с последующими запросами на повторную передачу ошибочно принятой информации (Automatic Repeat Request — ARQ).

При выборе методов кодирования и декодирования руководствуются многими факторами, взаимосвязь которых представлена на рисунке.

Взаимосвязь параметров кодирования

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

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

Общие сведения

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

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

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

Рассмотрим простейшую модель передачи данных с применением помехоустойчивого кодирования.

Модель передачи данных с применением помехоустойчивого кодирования

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

Из данного описания можно сделать 2 вывода:

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

Линейные блоковые коды

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

СложениеУмножение
01×01
001000
110101

Наиболее известным линейным кодом является блоковый код Хэмминга. Далее описание линейных блоковых кодов будет производиться на примере этого кода. В частности, будет рассмотрен (7,4)-код Хэмминга.

Кодер двоичного блокового (n,k)-кода отображает множество 2k возможных двоичных информационных слов в множество 2k n-мерных кодовых слов. В теории кодирования между этими множествами всегда существует взаимно однозначное соответствие.

Кодер

Вместо k бит информационного вектора в канал передается n бит кодового вектора. В этом случае говорят об избыточном кодировании со скоростью: R = n ⁄ k.

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

Описание процессов кодирования и декодирования

Структура кодовых векторных пространств

Исходным материалом для построения кодовых конструкций служит n-мерное двоичное векторное пространство, в котором заданы операции арифметики по модулю 2. В него вложено k-мерное линейное пространство, содержащее 2k кодовых слов. Код С образуется с помощью 2k комбинаций k линейно независимых базисных векторов {g1,…,gk}.

Структура кодовых векторных пространств

Эти векторы образуют строки порождающей матрицы кода С.

Порождающая матрица

Для кода C существует дуальный код Cd такой, что скалярное произведение любой пары векторов, один из которых принадлежит пространству С, а другой — пространству Cd, всегда равно нулю. Это значит, что векторы кода Сd ортогональны векторам кода С. С другой стороны, если некоторый вектор ортогонален всем векторам кода С, то он принадлежит коду Сd и наоборот. Дуальное векторное подпространство «натянуто» на nk линейно независимые базисные векторы {h1,…,hnk}. Эти векторы образуют строки проверочной матрицы.

Проверочная матрица

Рассмотрим пример порождающей и проверочной матриц (7,4)-кода Хэмминга:

Порождающая матрица (7,4)-кода Хэмминга Проверочная матрица (7,4)-кода Хэмминга

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

Кодирование

Кодовое слово v и информационное слово u связаны соотношением:

v = u × G,

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

Например, информационный вектор u = (1010) отобразится в кодовый вектор следующим образом:

Кодирование информационного вектора

Легко заметить, что последние четыре разряда кодового вектора совпадают с информационным вектором. Это свойство называется систематичностью кода.

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

Gk×n = (Pk×(nk) Ik),

где Ik — единичная матрица размерности k×k.

Таким образом, в кодовом векторе систематического кода всегда можно выделить информационные и проверочные символы.

v = ( v0 … vnk−1 vnk … vn−1 ).
  n − k проверочных символов k информационных символов  

Роль проверочных символов и их использование будут подробно разъяснены ниже.

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

Задача декодера заключается в том, чтобы, используя структуру кода, по принятому слову r, восстановить переданный информационный вектор. Для рассмотренного выше (7, 4)-кода Хэмминга можно предложить следующий алгоритм обнаружения ошибок. Так как рассматриваемый код является систематическим, выразим каждый из трех проверочных символов через символы информационного вектора:

v0 = v3 ⊕ v5 ⊕ v6
v1 = v3 ⊕ v4 ⊕ v5
v2 = v4 ⊕ v5 ⊕ v6

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

r0 ⊕ r3 ⊕ r5 ⊕ r6 = s0
r1 ⊕ r3 ⊕ r4 ⊕ r5 = s1
r2 ⊕ r4 ⊕ r5 ⊕ r6 = s2

Таким образом, из первых трех столбцов порождающей матрицы G мы получили систему трех проверочных уравнений. Если в полученной системе уравнений хотя бы одна из компонент {s0, s1, s2} не равна нулю, то в канале произошла ошибка.

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

H(nkn = (Ink PTk×(nk)).

Тогда систему проверочных уравнений можно записать в виде

s = r × HT

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

В качестве примера рассмотрим синдромное декодирование (7, 4)-кода Хэмминга. При передаче информационного слова u = (1010) по каналу без шума r = v = (0011010). Можем убедиться, что в этом случае синдром равен 0.

Синдромное декодирование при передаче по каналу без шума

Если, например, в кодовом слове произошла одиночная ошибка на четвертой позиции (r = (0010010)), то синдромом является четвертая строка транспонированной проверочной матрицы.

Синдромное декодирование при передаче по зашумленному каналу

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

Ошибочный разряд r0 r1 r2 r3 r4 r5 r6
Синдром s 100 010 001 110 011 111 101

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

Разновидности ошибок

У линейных блоковых кодов имеются 3 разновидности ошибок:

  1. Распознаваемая и исправляемая ошибка
    • Принятое слово не соответствует ни одному из кодовых слов
    • Синдром присутствует в таблице синдромов
    • Декодер распознает и исправляет ошибку, а затем передает на приемник корректное слово
  2. Распознаваемая ошибка
    • Принятое слово не соответствует ни одному из кодовых слов
    • Синдром не присутствует в таблице синдромов
    • Декодер распознает ошибку и посылает запрос на повторную передачу информационного слова.
  3. Нераспознаваемая ошибка
    • Принятое слово соответствует одному из кодовых слов (не соответствующему исходному кодовому слову)
    • Синдром равен 0
    • Декодер не распознает ошибку и выдает потребителю ошибочное информационное сообщение

Заключение

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

Литература

  1. Вернер М. Основы кодирования.  — М.: Техносфера, 2004.
  2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.

Олег Рыбак


Андрей / 2010-04-07 14:57:11

Замечательный материал

Арсений / 2010-05-05 23:51:24

Единственное понятное объяснение!

:-)

Дмитрий / 2010-05-26 14:55:21

Действительно понятное объяснение, которое с трудом можно найти!!! Благодарю

Алексей / 2013-06-23 02:10:56

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

пак / 2014-03-13 16:34:39

Сложно разобраться, книжки смотрите ребята

Михаил / 2017-05-15 11:05:22

Даже Носырева так не объясняет! Браво!!!

А кто это?

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий