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

Содержание

Введение. 3

1. Обнаружение  ошибок. 4

2. Коррекция  ошибок. 6

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

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

Заключение 18

Литература. 19

 

Введение.

 

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

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

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

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

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

 

1. Обнаружение ошибок.

 

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

Простейшим способом обнаружения  ошибок является контроль по четности. Обычно контролируется передача блока  данных (М бит). Этому блоку ставится в соответствие кодовое слово  длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1–M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).

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

Пусть А и Б две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.

Можно показать, что для  детектирования ошибок в n битах, схема  кодирования требует применения кодовых слов с расстоянием Хэмминга не менее N+1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования  с расстоянием Хэмминга между  кодами не менее 2N+1. Таким образом, конструируя  код, мы пытаемся обеспечить расстояние Хэмминга между возможными кодовыми последовательностями больше, чем оно  может возникнуть из-за ошибок.

Широко распространены коды с одиночным битом четности. В  этих кодах к каждым М бит добавляется 1 бит, значение которого определяется четностью (или нечетностью) суммы  этих М бит. Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем четности будут 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, четность кода из М+1 бита изменится.

Предположим, что частота  ошибок (BER) равна р=10^-4. В этом случае вероятность передачи 8 бит с ошибкой составит: 1–(1–p)⁸=7,9∙10^-4.

Добавление бита четности позволяет детектировать любую  ошибку в одном из переданных битах. Здесь вероятность ошибки в одном  из 9 бит равна 9p(1–p)⁸. Вероятность же реализации необнаруженной ошибки составит: 1– (1– p)⁹ – 9p(1– p)⁸ = 3,6∙10^-7.

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

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

 

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

 

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

Но существуют и более  простые методы коррекции ошибок. Например, передача блока данных, содержащего N строк и M столбцов, снабженных битами четности для каждой строки и столбца. Обнаружение ошибки четности в строке i и столбце j указывает на бит, который  должен быть инвертирован. Может показаться, что в случае, когда неверны  два бита, находящиеся в разных строках и столбцах, они также  могут быть исправлены. Но это не так. Ведь нельзя разделить варианты i1,j1 - i2,j2 и i1,j2 - i2,j1. Этот метод может быть развит путем формирования блока данных с N строками, M столбцами и K слоями. Здесь биты четности формируются для всех строк и столбцов каждого из слоев, а также битов, имеющих одинаковые номера строк и столбцов i,j. Полное число битов четности в этом случае равно (N+M+1)×K +(N+1)×(M+1). Если M=N=K=8, число бит данных составит 512, а число бит четности - 217. Нетрудно видеть, что в этом случае число исправляемых ошибок будет больше 1. (Рис. 1).

 

Рис. 1. Метод коррекции более одной  ошибки в блоке данных

(битам  данных соответствуют окрашенные  квадраты)

Алгоритм Хэмминга.

 

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

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

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

 Для того, чтобы понять работу данного алгоритма, рассмотрим пример.

Допустим, у нас есть сообщение  «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.

 На этом этапе стоит  определиться с, так называемой, длиной информационного слова,  то есть длиной строки из  нулей и единиц, которые мы  будем кодировать. Допустим, у нас  длина слова будет равна 16. Таким образом, нам необходимо  разделить наше исходное сообщение  («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:

 и

 После этого процесс  кодирования распараллеливается, и  две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.

 Прежде всего, необходимо  вставить контрольные биты. Они  вставляются в строго определённых  местах — это позиции с номерами, равными степеням двойки. В нашем  случае (при длине информационного  слова в 16 бит) это будут  позиции 1, 2, 4, 8, 16. Соответственно, у  нас получилось 5 контрольных бит  (выделенные):

 Было:

 Стало:

 Таким образом, длина  всего сообщения увеличилась  на 5 бит. До вычисления самих  контрольных бит, мы присвоили  им значение «0». 

Вычисление контрольных  бит.

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

 Здесь знаком «X»  обозначены те биты, которые контролирует  контрольный бит, номер которого  справа. То есть, к примеру, бит  номер 12 контролируется битами  с номерами 4 и 8. Ясно, что чтобы  узнать какими битами контролируется  бит с номером N надо просто  разложить N по степеням двойки.

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

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

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

 и для второй части: 

Декодирование и  исправление ошибок.

 Теперь, допустим, мы получили  закодированное первой частью  алгоритма сообщение, но оно  пришло к нас с ошибкой. К примеру, мы получили такое (11-ый бит передался неправильно):

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

 Как мы видим, контрольные  биты под номерами: 1, 2, 8 не совпадают  с такими же контрольными битами, которые мы получили. Теперь просто  сложив номера позиций неправильных  контрольных бит (1 + 2 + 8 = 11) мы получаем  позицию ошибочного бита. Теперь  просто инвертировав его и  отбросив контрольные биты, мы  получим исходное сообщение в первозданном виде.

Метод коррекции ошибок FEC.

Для FEC(Forward Error Correction)-кодирования иногда используется метод сверки, который впервые был применен в 1955 году. Главной особенностью этого метода является сильная зависимость кодирования от предыдущих информационных битов и высокие требования к объему памяти. FEC-код обычно просматривает при декодировании 2-8 бит десятки или даже сотни бит.

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

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