Коды исправляющие ошибки

Курс: Теория информации и кодирования

Тема: КОРРЕКТИРУЮЩИЕ КОДЫ

Содержание

1. КОРРЕКТИРУЮЩИЕ КОДЫ. ОСНОВНЫЕ ПОНЯТИЯ

2. ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

3. КОД ХЭММИНГА

Список Литературы

1. КОРРЕКТИРУЮЩИЕ КОДЫ. ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

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

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

Коды, исправляющие ошибки

Для исправления двух и более ошибок (d0 ³ 5 ) используются циклические коды БЧХ (Боуза — Чоудхури — Хоквингема), а также Рида-Соломона, которые широко используются в устройствах цифровой записи звука на магнитную ленту или оптические компакт-диски и позволяющие осуществлять коррекцию групповых ошибок. Способность кода обнаруживать и исправлять ошибки достигается за счет введений избыточности в кодовые комбинации, т. е. кодовым комбинациям из к двоичных информационных символов, поступающих на вход кодирующего устройства, соответствует на выходе последовательность из n двоичных символов (такой код называется (n, k ) — кодом).

Если N0 = 2n -общее число кодовых комбинаций, а N = 2k — число разрешенных, то число запрещенных кодовых комбинаций равно

N0 -N = 2n -2k .

При этом число ошибок, которое приводит к запрещенной кодовой комбинации равно:

, (1)

где S — кратность ошибки, т. е. количество искаженных символов в кодовой комбинации S = 0, 1, 2, …

Cni — сочетания из n элементов по i , вычисляемое по формуле:

, (2)

дляS = 0 ;

S = 1 ;

S = 2 ;

S = 3 ;

ит. д.

Для исправления S ошибок количество комбинаций кодового слова, составленного из m проверочных разрядов N = 2m , должно быть больше возможного числа ошибок (2), при этом количество обнаруживаемых ошибок в два раза больше, чем исправляемых

(3)

2m ³ откуда

.

Для одиночной ошибки, как наиболее вероятной

.

В зависимости от исходных данных кода (n или k ) можно использовать

формулы

. (4)

При этом, m = [log2 (1+n)] или m = [log2 {(k+1)+ [log2 (k+1)]}], где ква-дратные скобки обозначают округление до большего целого.

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

Для исправления двукратной ошибки

или . (5)

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

Например, для кода (31, 26) скорость передачи информации равна

,

т. е. скорость передачи уменьшается на 16%.

Таблица 1

Как видно из таблицы 1, чем больше n, тем эффективнее используется канал.

Пример 1. Определить количество проверочных разрядов для систематического кода исправляющего одиночную ошибку и состоящего из 20 информационных разрядов.

Решение: Общая длина кодовой комбинации равна n = k+m, где k — количество информационных разрядов, а m — проверочных разрядов.

Для обнаружения двойной и исправления одиночной ошибки зависимости для разрядов имеют вид

, при этом

m = [log2 {(k+1)+ [log2 (k+1)]}]=[log2 {(20+1)+ [log2 (20+1)]}]=5,

т.

е. получим (25, 20)-код.

2. ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

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

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

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами k и n . Число строк равно k, а число столбцов равно n = k+m.

. (6)

Коды, порождаемые этими матрицами, называются (n, k )-кодами, а соответствующие им матрицы порождающими (образующими, производящими). Порождающая матрица G состоит из информационной Ikk и проверочной Rkm матриц. Она является сжатым описанием линейного кода и может быть представлена в канонической (типовой) форме

. (7)

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

. (8)

Строки единичной матрицы представляют собой линейно-незави-симые комбинации (базисные вектора), т. е. их по парное суммирование по модулю два не приводит к нулевой строке.

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

Столбцы добавочной матрицыRkm определяют правила формирования проверок. Число единиц в каждой строке добавочной матрицы должно удовлетворять условию r1 ³ d0 -1 , но число единиц определяет число сумматоров по модулю 2 в шифраторе и дешифраторе, и чем их больше, тем сложнее аппаратура.

Производящая матрица кода G(7,4) может иметь вид

и т.д.

Процесс кодирования состоит во взаимно — однозначном соответствии k -разрядных информационных слов — I и n- разрядных кодовых слов — с

c=IG. (9)

Например: информационному слову I =[1 0 1 0] соответствует следующее кодовое слово

. (10)

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

Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному. Это осуществляется с помощью проверочной матрицы H(n, k) .

, (11)

где RmkT -транспонированная проверочная матрица (поменять строки на столбцы); Imm — единичная матрица.

Для (7, 4)- кода проверочная матрица имеет вид

. (12)


Способы борьбы с ошибками

Методы повышения достоверности передачи. Обнаруживающие и исправляющие коды.

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

В процессе передачи информации по сетям связи неизбежно возникают ошибки.

Обнаружение и исправление ошибок

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

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

· обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;

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

· исправление ошибок применяется на физическом уровне.

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

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

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

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

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

Линейный блоковый код, код Хемминга, циклический код, циклический избыточный код CRC, код Рида-Соломона.

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

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование.

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

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.


Дата добавления: 2014-01-06; Просмотров: 1638; Нарушение авторских прав?;




Читайте также:

Кодовое расстояние и корректирующая способность кода

 

Под корректирующей способностью кодапонимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q. Корректирующая способность кода связана с его кодовым расстоянием.

Расстояниемdijмежду кодами(кодовыми комбинациями) i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

 

Кодовым расстояниемd для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.е.

,

где i≠j, i=1,m; j=1,m.

 

Пусть есть кодовая таблица:

 

Исходные символы Двоичные коды
a
b
c
d

 

Тогда расстояния между кодовыми комбинациями имеют значения:

dab = 1; dad = 2; dbd= 1; dac = 1; dbc = 2; dcd = 1.

Отсюда следует:

d = min{1, 2, 1, 1, 2, 1} = 1.

 

Это означает, что всякая ошибка кратности 1 (и более) переводит исходную кодовую комбинацию в другую кодовую комбинацию, которая также принадлежит коду.

 

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

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

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

Исходные символы Информационные разряды кода Проверочный разряд кода Результирующий код
a
b
c
d

 

Таким образом, полученный код является трехразрядным.

 

Определим кодовое расстояние полученного кода. Для этого вначале выясним расстояния между кодовыми комбинациями:

dab = 2; dad = 2; dbd= 2; dac = 2; dbc = 2; dcd = 2.

 

Тогда d = min{2, 2, 2, 2, 2, 2} = 2.

 

Пусть передается кодовая комбинация, соответствующая символу c, – 101. Пусть на нее накладывается ошибка кратности 1. Возможные результаты искажения приведены в таблице:

 

Передаваемая кодовая комбинация Ошибка Принимаемая кодовая комбинация Результат декодирования
Невозможно декодировать
То же
"-"

 

В результате данной ошибки получаемые кодовые комбинации невозможно декодировать, так как они отсутствуют в результирующем коде (см. таблицу выше).

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

 

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

 

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

 

Исходные символы Информационные разряды кода Проверочный разряд кода Результирующий код
a
b
c
d

 

то кодовые комбинации из графы Результирующий код являются разрешенными кодовыми комбинациями. Их количество равно числу исходных символов (m).

Запрещенные кодовые комбинации – это те, которые отсутствуют в исходной кодовой таблице. Их количество определяется по формуле: 2r – m, где r – общее число двоичных разрядов (информационные плюс проверочные) в коде.

 

Сформируем все разрешенные и запрещенные кодовые комбинации для кода из приведенной выше таблицы, при этом используем схему формирования кода Грея:

 

 
a  
  b
d  
  c

 

Здесь обозначения строк – значения графы Информационные разряды кода, обозначения столбцов – значения проверочных разрядов.

65. Классификация корректирующих кодов. Коды обнаруживающие и исправляющие ошибки.

Пустые ячейки означают запрещенные кодовые комбинации.

Как видно из последней таблицы, отстояние кодовых комбинаций для исходных символов a, b, c, d равно двум разрядам:

· символы, находящиеся в одном столбце (a и d, b и c), имеют одинаковый проверочный разряд, но находятся в несмежных строках, которые различаются двумя разрядами;

· символы, находящиеся в смежных строках (a и b, b и d, d и c), которые различаются одним разрядом, расположены попарно в разных столбцах, имеющих различное обозначение.

 

Поэтому при наличии ошибки кратности 1 кодовая комбинация переходит в соседнюю запрещенную.

 

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

 

Существует связь между кодовым расстоянием d и минимальной кратностью ошибки q, которую код может обнаруживать:

d ≥ q + 1.

 

Пример 1.

На базе кода из таблицы построить код, обнаруживающий ошибки кратности 2.

Для решения задачи воспользуемся схемой формирования кода Грея с некоторыми модификациями.

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

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

С учетом сделанных замечаний схема имеет 4 столбца и 4 строки и представлена ниже:

 

 
a      
  b    
    d  
      c

 

Таким образом, построен следующий код:

00000 → a, 01101 → b, 11011 → d, 10110 → c.

 

Определим кодовое расстояние d построенного кода. Поскольку dab = 3; dad = 4; dbd = 3; dac = 3; dbc = 4; dcd = 3, dmin = {3, 4, 3, 3, 4, 3} = 3.

 

Проверим, обнаруживает ли построенный код ошибку кратности 2.

Для этого зададимся произвольной кодовой комбинацией, например, 01101 (символ b). Результат проверок приведен в таблице:

 

Передаваемая кодовая комбинация Ошибка Принимаемая кодовая комбинация Результат декодирования
Невозможно декодировать
То же
"-"
"-"
"-"
"-"
"-"
"-"
"-"
"-"

 

Таким образом, задача решена.

Предыдущая14151617181920212223242526272829Следующая


Дата добавления: 2015-03-03; просмотров: 732;


ПОСМОТРЕТЬ ЕЩЕ:

Добавить комментарий

Закрыть меню