Курс: Теорияинформации и кодирования
Тема: КОРРЕКТИРУЮЩИЕКОДЫ
Содержание
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 n 7 10 15 31 63 127 255
k 4 6 11 26 57 120 247
m 3 4 4 5 6 7 8
/> 0,57 0,6 0,75 0,84 0,9 0,95 0,97
Как видно из таблицы 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)
Между G(n ,k) и H(n, k)существует однозначная связь, т. к. они определяются в соответствии с правиламипроверки, при этом для любого кодового слова должно выполняться равенство cHT= 0.
Строкипроверочной матрицы определяют правила формирования проверок. Для (7,4)-кода
p1Å+a1Å+a2Åa4 = S1 ;
p2Å+a1Å+a2Åa3 = S2; (13)
p3Å+a1Å+a3Åa4= S3.
Полученный синдром сравниваем со столбцамиматрицы и определяем разряд, в котором произошла ошибка, номер столбца равенномеру ошибочного разряда. Для исправления ошибки ошибочный бит необходимопроинвертировать.
Пример 1. Построить групповой код способный передавать 16 символовпервичного алфавита с исправлением одиночной ошибки. Показать процесскодирования, декодирования и исправления ошибки для передаваемогоинформационного слова 1001.
Решение:
1. Построим производящую матрицу G(n,k).
Если объем кода N = 2k = 16,то количество информационных разрядов к = 4. Минимальное кодовоерасстояние для исправления одиночной ошибки d0=2s+1=3. Позаданной длине информационного слова, используя соотношения:
n = k+m, 2n³(n+1)2k и 2m³n+1
вычислим основные параметры кода nи m.
m=[log2 {(k+1)+[log2(k+1)]}]=[log2 {(4+1)+ [log2(4+1)]}]=3.
Откуда n = 7, т. е. необходимопостроить (7, 4)-код.
В качестве информационной матрицы Ik(7,4) — выбираем единичную матрицу (4´4), а вкачестве проверочной матрицы Rkm(7 ,4) — выбираем матрицу (4´3), каждая строка которой содержит число единиц большеили равно двум (r1£d0-1).
Таким образом, в качестве производящейможно принять матрицу
/>.
2. Определим комбинации корректирующегокода.
Для заданного числа информационныхразрядов k = 4,число кодовых комбинаций равно N = 2k = 24= 16.
1) 0000 5) 0010 9) 0001 13) 0011
2) 1000 6) 1010 10) 1001 14) 1011
3) 0100 7) 0110 11) 0101 15) 0111
4) 1100 8) 1110 12) 1101 16) 1111
Старшинство разрядов принимаем слева направо, в соответствии с их поступлением на вход декодера.
Находим корректирующие разряды для каждогоинформационного слова, как результат суммирования по модулю два строкпроверочной матрицы номера, которых совпадают с номерами единиц винформационных разрядах кода.
Например, для информационного слова I=[1001] кодовое слово имеет вид
/>.
Передаваемые в канал кодовые комбинацииимеют вид:
1) 0000 000 5) 0010 110 9) 0001 101 13)0011 011
2) 1000 111 6) 1010 001 10) 1001 010 14)1011 100
3) 0100 011 7) 0110 101 11) 0101 110 15)0111 000
4) 1100 100 8) 1110 010 12) 1101 101 16)1111 111
Процесс декодирования состоит вопределении соответствия принятого кодового слова, переданному информационномуи осуществляется с помощью проверочной матрицы H(7, 4).
Для построенного (7, 4)-кода проверочнаяматрица имеет вид
/>.
Строки проверочной матрицы определяютправила формирования проверок, позволяющие определить синдром ошибки.
Пусть в процессе передачи произошла ошибкаво 2-м информационном разряде 1 1 0 1 1 0 0 1
В соответствии с проверочной матрицейсоставляем проверочные векторы
p1Åa1Åa2Åa4 =S1 = 0Å1Å1Å0 = 0;
p2Åa1Åa2Åa3 =S2 = 0Å1Å1Å1 = 1;
p3Åa1Åa3Åa4 =S3 = 1Å1ÅÅ1 = 1.
Синдром 011 показывает, что ошибкапроизошла во 2-м информационном разряде, который необходимо проинвертировать.
Пример 2. Построить образующую матрицу группового кода, дляпередачи 100 различных сообщений и способную исправлять возмож-но большее числоошибок.
Решение: Объем кода равен N = 2k. При 100сообщениях: 100 £N £2k, откуда k = 7. По заданной длинеинформационного слова, используя соотношения:
n = k+m, 2n³(n+1)2k и 2m³n+1
вычислим основные параметры кода nи m.
m=[log2 {(k+1)+[log2(k+1)]}]=[log2 {(7+1)+ [log2(7+1)]}]=4.
Откуда n = 11, т. е. получили (11,7)-код.
В качестве информационной матрицы выбираемединичную матрицу I(7x7).Проверочная матрица содержит 4 столбца и 7строк, которые содержат r1£d0-1 единиц в четырехразрядном коде (2, 3, 4-единицы).
/>.
3. КОД ХЭММИНГА
Код Хэмминга относится к классу линейныхкодов и представляет собой систематический код – код, в котором информационныеи контрольные биты расположены на строго определенных местах в кодовой комбинации.
Код Хэмминга, как и любой (n, k)-код, содержит к информационных и m = n-k избыточных (проверочных)бит.
Избыточная частькода строится т. о. чтобы можно было при декодировании не только установитьналичие ошибки но, и указать номер позиции в которой произошла ошибка, азначит и исправить ее, инвертировав значение соответствующего бита.
Существуют различные методы реализациикода Хэмминга и кодов которые являются модификацией кода Хэмминга. Рассмотрим алгоритмпостроения кода для исправления одиночной ошибки.
1. По заданному количеству информационныхсимволов — k, либо информационных комбинаций N = 2k,используя соотношения:
n = k+m, 2n³(n+1)2kи 2m³n+1 (14)
m= [log2 {(k+1)+ [log2(k+1)]}]
вычисляют основные параметры кода nи m.
2. Определяем рабочие и контрольныепозиции кодовой комбинации. Номера контрольных позиций определяются по закону 2i,где i=1, 2, 3,… т.е. они равны 1, 2, 4, 8, 16,… а остальныепозиции являются рабочими.
3. Определяем значения контрольныхразрядов (0 или 1 ) при помощи многократных проверок кодовой комбинации начетность. Количество проверок равно m = n-k. В каждую проверкувключается один контро-льный и определенные проверочные биты. Если результатпроверки дает четное число, то контрольному биту присваивается значение -0, впротивном случае — 1. Номера информационных бит, включаемых в каждую проверку,определяются по двоичному коду натуральных n –чисел разрядностью – m (табл.1, для m = 4) или при помощи проверочной матрицы H(m´n), столбцы которой представляютзапись в двоичной системе всех целых чисел от 1 до 2k–1перечисленных в возрастающем порядке. Дляm = 3 проверочная матрицаимеет вид
/>. (15 )
Количество разрядов m — определяетколичество проверок.
В первую проверку включают коэффициенты,содержащие 1 в младшем (первом) разряде, т. е. b1, b3, b5 и т. д.
Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде,т. е. b2, b3, b6 и т. д.
В третью проверку — коэффициенты которые содержат 1 в третьем разряде ит. д.
Таблица 1
Десятичные числа
(номера разрядов
кодовой комбинации) Двоичные числа и их разряды 3 2 1
1
2
3
4
5
6
7
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
Для обнаружения и исправления ошибкисоставляются аналогичные проверки на четность контрольных сумм, результатомкоторых является двоичное (n-k) -разрядное число, называемое синдромом иуказывающим на положение ошибки, т. е. номер ошибочной позиции, которыйопределяется по двоичной записи числа, либо по проверочной матрице.
Для исправления ошибки необходимопроинвертировать бит в ошибочной позиции. Для исправления одиночной ошибки иобнаружения двойной используют дополнительную проверку на четность. Если приисправлении ошибки контроль на четность фиксирует ошибку, то значит в кодовойкомбинации две ошибки.
Схема кодера и декодера для кода Хэммингаприведена на рис. 1.
Пример1. Построить код Хемминга для передачи сообщений в видепоследовательности десятичных цифр, представленных в виде 4 –х разрярныхдвоичных слов. Показать процесс кодирования, декодирования и исправленияодиночной ошибки на примере информационного слова 0101.
Решение:
1. По заданной длине информационного слова(k = 4), определим количество контрольных разрядов m, используя соотношение:
m = [log2 {(k+1)+[log2(k+1)]}]=[log2 {(4+1)+ [log2(4+1)]}]=3,
при этом n = k+m = 7, т. е.получили (7, 4) -код.
2. Определяем номера рабочих и контрольныхпозиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i.
Для рассматриваемой задачи (при n = 7)номера контрольных позиций равны 1, 2, 4. При этом кодовая комбинация имеетвид:
b1 b2b3 b4 b5 b6 b7
к1 к2 0 к3 10 1
3. Определяем значения контрольныхразрядов (0 или 1), используя проверочную матрицу (5).
Первая проверка:
k1 Å b3Å b5Å b7 = k1Å0Å1Å1 будет четной при k1 = 0.
Вторая проверка:
k2 Å b3Å b6Å b7 = k2Å0Å0Å1 будет четной при k2 = 1.
Третья проверка:
k3 Å b5Å b6Å b7 = k3Å1Å0Å1 будет четной при k3 = 0.
1 2 3 4 5 6 7
Передаваемая кодовая комбинация: 0 1 0 0 10 1
Допустим принято: 0 1 1 0 1 0 1
Для обнаружения и исправления ошибкисоставим аналогичные про-верки на четность контрольных сумм, в соответствии спроверочной матрицей результатом которых является двоичное (n-k)-разрядное число, называемое синдромом и указывающим на положение ошибки, т. е,номер ошибочной позиции.
1) k1 Å b3Å b5Å b7 = 0Å1Å1Å1 = 1.
2) k2 Å b3Å b6Å b7 = 1Å1Å0Å1 = 1.
3) k3 Å b5Å b6Å b7 = 0Å1Å0Å1 = 0.
Сравнивая синдром ошибки со столбцамипроверочной матрицы, определяем номер ошибочного бита. Синдрому 011соответствует третий столбец, т. е. ошибка в третьем разряде кодовойкомбинации. Символ в 3 -й позиции необходимо изменить на обратный.
Пример 2. Построить код Хэмминга для передачи кодовой комбинации1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующемразряде кодовой комбинации.
Решение: Рассмотрим алгоритм построения кода для исправления одиночнойошибки.
1. По заданной длине информационного слова(k = 8), используя соотношения вычислим основные параметры кода nи m.
m = [log2 {(k+1)+[log2(k+1)]}]=[log2 {(9+1)+ [log2(9+1)]}]=4,
при этом n = k+m = 12, т. е.получили (12, 8)-код.
2. Определяем номера рабочих и контрольныхпозиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i.
Для рассматриваемой задачи (при n = 12)номера контрольных позиций равны 1, 4, 8.
При этом кодовая комбинация имеет вид:
b1 b2 b3b4 b5 b6 b7 b8 b9b10 b11 b12
к1 к2 1 к3 10 1 к4 1 0 1 1
3. Определяем значения контрольных разрядов(0 или 1) путем много-кратных проверок кодовой комбинации на четность. Количествопроверок равно m = n-k. В каждую проверку включается один контрольный иопределенные проверочные биты.
Номера информационных бит, включаемых вкаждую проверку определяется по двоичному коду натуральных n-чиселразрядностью — m.
0001 b1 Количество разрядов m — определяет количество прове-
0010 b2 верок.
0011 b3 1) к1Å b3 Å b5Å b7Å b9Å а11 = к1Å1Å1Å1Å1Å1 =>
0100 b4 четная при к1=1
0101 b5 2) к2Å b3Å b6Å b7Å b10Å b11= к2Å1Å0Å1Å0Å1 =>
0110 b6 четная при к2=1
0111 b7 3)к3Å b5Å b6Å b7Å b12= к3Å1Å0Å1Å1=>
1000 b8 четная при к3=1
1001 b9 4) к4Å b9Å b10Å b11Å b12 = к1Å1Å0Å1Å1 =>
1010 b10 четная при к4=1
1011 b11
1100 b12
Передаваемая кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1 1 0 1 1 1 0 1 1
Допустим, принято: 1 1 1 1 0 0 1 1 1 0 1 1
Для обнаружения и исправления ошибкисоставим аналогичные про-верки на четность контрольных сумм, результатомкоторых является двоичное (n-k) -разрядное число, называемое синдромом иуказывающим на положение ошибки, т. е. номер ошибочной позиции.
1) к1Å b3Å b5Å b7Å b9Å b11 = 1Å1Å0Å1Å1Å1 =1
2) к2Å b3Å b6Å b7Å b10Å b11 = 1Å1Å0Å1Å0Å1 =0
3)к3Å b5Å b6Å b7Å b12= 1Å0Å0Å1Å1 =1
4) к4Å b9Å b10Å b11Å b12= 1Å1Å0Å1Å1 =0
Обнаружена ошибка в разряде кодовойкомбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибкинеобходимо проинвертировать 5 -й разряд в кодовой комбинации.
/>