Коррекция ошибок

В результате через канал  передается n-битовое кодовое слово (n>k). Конкретная реализация алгоритма FEC характеризуется комбинацией (n,k). Применение FEC в Интернет регламентируется документом RFC-3452. Коды FEC могут исключить необходимость обратной связи при потере или искажении доставленных данных (запросы повторной передачи). Особенно привлекательна технология FEC при работе с мультикастинг-потоками, где ретрансмиссия не предусматривается.

В 1974 году Йозеф Оденвальдер (Joseph Odenwalder) объединил возможности алгебраического кодирования и метода свертки. Хорошего результата можно добиться, введя специальную операцию псевдослучайного перемешивания бит (interleaver).

В 1993 году группой Клода  Берроу (Claude Berrou) был разработан турбо код. В кодеке, реализующем этот алгоритм, содержатся кодировщики как минимум двух компонент (реализующие алгебраический метод или свертку). Кодирование осуществляется для блоков данных. Здесь также используется псевдослучайное перемешивание бит перед передачей. Это приводит к тому, что кластеры ошибок, внесенных при транспортировке, оказываются разнесенными случайным образом в пределах блока данных.

 

3. Циклические коды.

 

Обобщением кодов Хэмминга являются циклические коды BCH (Bose-Chadhuri-Hocquenghem). Циклические коды являются частным случаем линейных и представляют собой наиболее разработанную часть последних. Основным их достоинством является простота технической реализации, благодаря чему они и обратили на себя внимание специалистов. Ценным свойством таких кодов является способность обнаруживать не только одиночные ошибки, но и пакеты ошибок. Пакетом ошибок длиной L называют число разрядов сообщения, искаженных подряд.

Свое название циклические  коды получили из-за следующего свойства: если комбинация a_n-1a_n-2 ... a₁a₀ относится к коду, то комбинация, полученная путем циклического сдвига элементов, т.е. комбинация a_n-2 ... a₁a₀a_n-1, также относится к коду. Направление сдвига не имеет значения. Один сдвиг в одном направлении эквивалентен n-1 сдвигам в другом направлении.

 Математической основой  построения циклических кодов  является представление кодовых  комбинаций в виде многочленов  от некоторой переменной x с коэффициентами, равными элементам кодовых комбинаций, и операцией по mod2. Кодовая комбинация 

a_n-1a_n-2 ... a₁a₀

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

a_n-1x^n-1 + a_n-2x^n-2 + ... + a₁x + a₀

Пример. Многочлен кодовой комбинации 01001 имеет вид x³ + 1.

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

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

Кодовый полином.

 Циклический код строится  с помощью, так называемого порождающего многочлена g(x) степени r. Признаком принадлежности n-разрядной комбинации данному коду является делимость соответствующего ей многочлена на порождающий. Если многочлен принятой комбинации делится на порождающий, то считается, что она совпадает с посланной. Если деление происходит с остатком, то принятая комбинация к коду не относится, т.е. произошло наложение ошибки. Вид остатка при достаточной избыточности позволяет указать место ошибки.

Свойства циклических  кодов:

• Минимальное кодовое расстояние d циклического кода не превышает числа членов порождающего многочлена.
• Циклический код с порождающим многочленом степени r > 1 обнаруживает любую одиночную и любую двойную ошибку, т.е. имеет d > 3.
• Код с порождающим многочленом x + 1 является кодом с четным числом единиц.
• Циклический код с порождающим многочленом g(x)(x+1) имеет d > 4.
• Код с порождающим многочленом g(x) степени r обнаруживает все пакеты ошибок длины r или меньше.

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

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

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

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

• Контроль циклически избыточным кодом — CRC (Cyclical Redundancy Check). Это гораздо  более  мощный  и  широко  используемый  метод  обнаружения  ошибок передачи  информации.  Он  обеспечивает  обнаружение  ошибок  с  высокой вероятностью.  Кроме  того,  этот  метод  обладает  рядом  других  полезных  моментов, которые могут найти свое воплощение в практических задачах. 

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

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

Redundancy Check. CRC некоторой последовательности вычисляется на основании другой (исходной) битовой последовательности.  Главная  особенность  (и  практическая  значимость)  значения  CRC  состоит  в том,  что  оно  однозначно  идентифицирует  исходную  битовую  последовательность  и  поэтому используется  в  различных  протоколах  связи,  а  также  для  проверки  целостности  блоков  данных, передаваемых различными устройствами. Благодаря относительной простоте алгоритм вычисления CRC часто реализуется на аппаратном уровне.

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

фиксированное  двоичное  число  (полином,  CRC-полином,  генераторный  полином,  англ.  generator polinomial). Интерес представляет остаток от этого деления, который и является значением CRC. Все, что теперь требуется, — это некоторым образом запомнить его и передать вместе с исходной последовательностью. Приемник данной информации всегда может таким же образом выполнить деление  и  сравнить  его  остаток  с  исходным  значением  CRC.  Если они  равны,  то  считается,  что исходное сообщение не повреждено, и т. д. Степенью  CRC-полинома  W  называют  позицию  самого  старшего  единичного  бита.

Например, степенью полинома 10011₂  равна 4. Для вычисления CRC используют специальную т.н. полиномиальную арифметику.

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

 

4. Линейные блочные коды.

 

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

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

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

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

Блоковые коды. Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают (n,k) . При этом число R= k/n называется скоростью кода.

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

Пример  линейного блочного кода  (6, 3).

 Код (6, 3) состоит из 2^k = 2³ = 8 векторов сообщений, т.е. восьми кодовых слов. В векторном пространстве V₆  имеется 2ⁿ = 2⁶ = 64  6-кортежей. Восемь кодовых слов, показанных в таблице 1, образуют в V₆ подпространство (имеется нулевой вектор, сумма любых двух кодовых слов дает кодовое слово этого же подпространства). Таким образом, эти кодовые слова представляют линейный блочный код. Возникает вопрос о соответствии кодовых слов и сообщений для этого кода (6, 3). Однозначного соответствия для отдельных кодов (n, k) не существует.

 

 

Таблица 1. Соответствие кодовых слов и сообщений

Вектор сообщения	Кодовое слово
000	000000
100	110100
010	011010
110	101110
001	101001
101	011101
011	110011
111	000111

 

Порождающая матрица (матрица генератора). Реализация таблицы соответствия кодера при больших значениях k становится слишком громоздкой. Например, для кода (127, 92) существует 2⁹² или приблизительно    кодовых векторов. Если с помощью простой таблицы соответствия выполняется кодирование, то нужно большое количество памяти для такого огромного числа кодовых слов. Эту задачу можно значительно упростить, по мере необходимости генерируя необходимые кодовые слова, вместо того чтобы хранить их в памяти постоянно.

Так как множество  кодовых слов, составляющих линейный блочный код, является k–мерным подпространством n–мерного двоичного векторного пространства, то всегда можно найти такое множество п–кортежей (с числом элементов, меньшим 2^k), которое может генерировать все 2^k кодовых слова подпространства. Генерирующее множество векторов охватывает все подпространство. Наименьшее линейно независимое множество, охватывающее подпространство, называется базисом подпространства, а число векторов в этом базисном множестве называется размерностью подпространства. Пусть V₁, V₂, ..., V_k любое базисное множество k линейно независимых п–кортежей. Тогда это базисное множество можно использовать для генерации нужных векторов линейного блочного кода, поскольку каждый вектор кода является линейной комбинацией V₁, V₂, ..., V_k.  Другими словами, каждое из множества 2^k кодовых слов U можно представить следующим образом:

U = m₁ V₁ + т₂ V₂ + ... + т_k V_k ,                                        (1)

где т_i – это цифры сообщения 0 или 1, а i = 1, ... , k.

Кодирование линейного блочного (n, k) – кода задается порождающей матрицей G_n,k, которая определяется как массив размером k п [2, 3]:

G_n,k = .                                    (2)

Кодовые векторы  представляются векторами-строками, таким  образом, последовательность k бит сообщения, т.е. сообщение m, представляется как вектор-строка: т = т₁, т₂, ... , т_k.