Коды с обнаружением и исправлением ошибок

Коды с обнаружением и исправлением ошибок

понедельник, 3 июня 13 г.

КОД ГРЕЯ

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

понедельник, 3 июня 13 г.

КОД ГРЕЯ

понедельник, 3 июня 13 г.

Построение кода Грея

Шаг 1) код Грея для 0 и 1 равен 0 и 12, соответственно; Шаг 2) для построения кодов Грея для десятичных чисел 2 и 3 построим таблицу, в

которой для нумерации строк и столбцов использованы коды Грея для чисел 0 и 1 Шаг 3) получив коды Грея для четырех десятичных чисел, используем их в качестве номеров строк и столбцов, чтобы сформировать кодовые комбинации для первых шестнадцати десятичных цифр

Шаг 4) для формирования кода Грея для множества последовательных натуральных чисел, начинающихся с нуля, в количестве 2m строят таблицу размером mxm и нумеруют строки и столбцы в соответствии с кодами Грея, построенными на предыдущих этапах для m чисел. Получают коды Грея в соответствии с рассмотренными схемами.

понедельник, 3 июня 13 г.

Коды с контролем четности

Пример: Таблица ASCII для кодирования символов. Для кодирования используются 7 битов, 8-й добавляется, чтобы количество единиц было четным

понедельник, 3 июня 13 г.

Коды с повторением кодовых слов

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

Исправить ошибки при этом мы не можем.

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

понедельник, 3 июня 13 г.

Блоковые коды

Источник информации передает сообщение, состоящее из q-ичных знаков, где q - степень простого числа (обычно 2).

Кодер « защищает » сообщения посредством специальных кодов , исправляющих ошибки , и затем преобразует сообщения в сигналы, которые могут быть переданы по каналу. В кодере, приспособленном для использования блоковых кодов , непрерывная последовательность информационных символов разбивается на отрезки, содержащие по k символов, или блоки. Каждому информационному блоку сопоставляется набор из n символов, где n > k.

Этот набор называемый кодовым словом, передается по каналу связи, искажается шумом. Отношение R = k/n, которое характеризует избыточность, необходимую для исправления/обнаружения ошибок, называют

скоростью кода.

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

понедельник, 3 июня 13 г.

Таблицы

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

Пример. Предположим что четыре возможных сообщения a, b, c и d будут передаваться с помощью двоичного блокового кода длины 5. Тогда должны быть выбраны четыре кодовых слова, например 11000 для a, 00110 для b, 10011 для c и 01101 для d. Кроме того, предположим, что в канале возможны только ошибки типа замещения символов, т. е. при передаче по каналу в кодовом слове некоторые единицы могут замениться нулями, а некоторые нули - единицами. Для исправления ошибок на приемном конце канала

понедельник, 3 июня 13 г.

Понятие ощибки

Пусть слово длины n, состоящее из двоичных символов 0 и 1, передается по каналу передачи. Обычно при передаче символа 0 (1) на приемнике принимается тот же символ. Однако, иногда вместо 0 может быть принята 1 и, наоборот, вместо 1 может быть принят 0. Если в среднем ошибочным оказывается один из 100 символов, то можно считать, что вероятность неправильной передачи символа равна 0,01. Такие ошибки называются ошибками типа замещения символов.

Пусть было передано двоичное слово x = x1...xn, а на приемнике принято двоичное слово y = y1...yn. Так как канал с шумом, то принятый вектор y может отличаться от переданного вектора x.

Вектор ошибки

e = x y

Пусть p, 0 ≤ p << ½, - вероятность неправильной передачи двоичного символа. Тогда ej = 0 с вероятностью 1 - p, и ej = 1 с вероятностью p.

понедельник, 3 июня 13 г.

Расстояние Хемминга

Расстоянием Хэмминга между двумя двоичными векторами x и y, обозначение: d(x, y), называется число позиций, в которых эти векторы отличаются. Например, d(10111, 00011) = 2. Весом двоичного вектора, обозначение: w(x), называется число единичных компонент вектора x.

Таким образом,

d(x, y) = w(x y) = w(e)

Если вес вектора ошибок e равен t, то говорят, что при передаче кодового вектора x произошла t-кратная ошибка или ошибка кратности t.

понедельник, 3 июня 13 г.