Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

– Нарисовать структурную схему кодера и декодера, исправляющего ошибку.

– Исправить ошибку, допущенную в четвертом элементе принятой кодовой комбинации.

Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока. Поясним идею проверки на чётность на примере простейшего корректи-рующего кода, который так и называется кодом с проверкой на чётность иликодом с проверкой по паритету (равенству).В таком коде к кодовым комбинациям безизбыточного первичного двоич-ного k – разрядного кода добавляется один дополнительный разряд (символпроверки на чётность, называемый проверочным, или контрольным). Если чис-ло символов “1” исходной кодовой комбинации чётное, то в дополнительномразряде формируют контрольный символ 0, а если число символов “1” нечёт-ное, то в дополнительном разряде формируют символ 1. В результате общеечисло символов “1” в любой передаваемой кодовой комбинации всегда будет чётным.Таким образом, правило формирования проверочного символа сводится кследующему:

где i – соответствующий информационный символ (0 или 1), k – общее их числоа под операцией “⊕” здесь и далее понимается сложение по mod2. Очевидно,что добавление дополнительного разряда увеличивает общее число возмож-ных комбинаций вдвое по сравнению с числом комбинаций исходного первич-ного кода, а условие чётности разделяет все комбинации на разрешённые инеразрешённые. Код с проверкой на чётность позволяет обнаруживать одиноч-ную ошибку при приёме кодовой комбинации, так как такая ошибка нарушаетусловие чётности, переводя разрешённую комбинацию в запрещённую.Критерием правильности принятой комбинации является равенство нулюрезультата S суммирования по mod 2 всех n символов кода, включая провероч-ный символ r1. При наличии одиночной ошибки S принимает значение 1:

S = r1 ⊕ i1 ⊕ i2 ⊕ . . . ⊕ ik =  0 – ошибки нет

1444424443 =  1 – однократная ошибка. n

r1 = i1 ⊕ i2 ⊕ i3;

r2 = i2 ⊕ i3 ⊕ i4;

r3 = i1 ⊕ i2 ⊕ i4,

В соответствии с этим алгоритмом определения значений проверочныхсимволов ri ниже выписаны все возможные 16 кодовых слов (7,4) – кода Хем-минга.

На рис. 3.3 приведена схема декодера для (7,4) – кода Хемминга, на входкоторого поступает кодовое слово

V = ( i1′, i2′, i3′, i4′, r1′, r2′, r3′)

Апостроф означает, что любой символ слова может быть искажён помехой вканале передачи.

В декодере в режиме исправления ошибок строится последовательность:

s1 = r1′ ⊕ i1′ ⊕ i2′ ⊕ i3′;

s2 = r2′ ⊕ i2′ ⊕ i3′ ⊕ i4′;

s3 = r3′ ⊕ i1′ ⊕ i2′ ⊕ i4′. Трёхсимвольная последовательность ( s1, s2, s3 ) называется синдромом.

Термин “синдром” используется и в медицине, где он обозначает сочетаниепризнаков, характерных для определённого заболевания. В данном случаесиндром S = (s1, s2, s3 ) представляет собой сочетание результатов проверкина чётность соответствующих символов кодовой группы и характеризует опре-делённую конфигурацию ошибок (шумовой вектор).

Кодовые слова (7,4) – кода Хемминга.

к = 4 r = 3

i1 i2 i3 i4 r1 r2 r3

0 0 0 0 0 0 0

0 0 0 1 0 1 1

0 0 1 0 1 1 0

0 0 1 1 1 0 1

0 1 0 0 1 1 1

0 1 0 1 1 0 0

0 1 1 0 0 0 1

0 1 1 1 0 1 0

1 0 0 0 1 0 1

1 0 0 1 1 1 0

1 0 1 0 0 1 1

1 0 1 1 0 0 0

1 1 0 0 0 1 0

1 1 0 1 0 0 1

1 1 1 0 1 0 0

1 1 1 0 1 1 1

Число возможных синдромов определяется выражением S = 2r. (3.21)

При числе проверочных символов r = 3 имеется восемь возможных син-дромов (23 = 8). Нулевой синдром (000) указывает на то, что ошибки при приёмеотсутствуют или не обнаружены. Всякому ненулевому синдрому соответствуетопределённая конфигурация ошибок, которая и исправляется. Классическиекоды Хемминга (3.20) имеют число синдромов, точно равное их необходимомучислу, позволяют исправить все однократные ошибки в любом информативноми проверочном символах и включают один нулевой синдром. Такие коды назы-ваются плотноупакованными.Усечённые коды являются неплотноупакованными, так как число синдро-мов у них превышает необходимое. Так, в коде (9,5) при четырёх проверочныхсимволах число синдромов будет равно 24 =16, в то время как необходимо все-го 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).

Для рассматриваемого кода (7,4) в таблице 1 представлены ненулевыесиндромы и соответствующие конфигурации ошибок.

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Методы помехоустойчивого кодирования и классификация

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

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

Блочные коды подразделяются на разделимые и неразделимые. К разделимым относятся коды, кодовые комбинации которых состоят из двух частей: информационной и проверочной. Обычно проверочные символы получаются посредством некоторых операций над информационными символами. Разделимые коды условно обозначают в виде (n , k), где n – число символов в кодовой комбинации, k – число информационных символов. Тогда число проверочных символов в разделимых блочных кодах равно r = n – r.

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

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

Пример простейшего кодера (5,4) для формирования систематического кода приведен на рис.5.6. Здесь всего лишь один проверочный символ формируется из информационных символов путем их суммирования по модулю 2. Этот код называют кодом с проверкой на четность. Так как новую разрешенную комбинацию систематического кода можно получить линейными преобразованиями двух разрешенных, то такие коды часто называют также линейными или групповыми.

К несистематическим (нелинейным) относятся коды, в которых проверочные символы формируются за счет некоторых нелинейных операций над информационными символами. Примером нелинейного кода является код Бергера.

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

Примеры простейших помехоустойчивых кодов и их корректирующие возможности будут приведены ниже.

Мы поможем в написании ваших работ!

Основные характеристики помехоустойчивых кодов

Основными характеристиками помехоустойчивых кодов являются: длина кода n, его основание m, общее число кодовых комбинаций N, число разрешенных кодовых комбинаций Nр, избыточность кода Ки и минимальное кодовое расстояние dmin.

Основание кода m – это число различных символов в коде. Для двоичных кодов символами являются 1 и 0, поэтому m=2.

Число кодовых комбинаций  для равномерного кода равно N = mn. Например, для равномерного двоичного кода, имеющего длину n =6, число различных кодовых комбинаций равно N =26=64.

Число разрешенных кодовых комбинаций Nр – это количество кодовых комбинаций кода, используемых для передачи сообщений. Для помехоустойчивых кодов Nр<N. Оставшиеся кодовые комбинации N – Nр называют запрещенными. Если Nр=N, то код является безызбыточным. Для разделимых кодов Nр=2 k.

Избыточность кода Ки в общем случае определяется выражением

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

где величина k / n называется относительной скоростью кода.

Кодовое расстояние d (А,В) – это число позиций, в которых две кодовые комбинации А и В отличаются друг от друга. Например, если А=01101, В=10111,то d (А,В)=3. Кодовое расстояние между комбинациями А и В может быть найдено в результате сложения по модулю 2 одноименных разрядов комбинаций, а именно

где ai и bi – i-е разряды кодовых комбинаций A и B; символ Å обозначает сложение по модулю 2. Например, чтобы получить кодовое расстояние между комбинациями 1101011 и 0111101 достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2:

Кодовое расстояние между различными комбинациями конкретного кода может быть различным. Так, для первичных кодов (приложения 1, 2) это расстояние для различных пар кодовых комбинаций может принимать значения от единицы до величины длины кода.

Минимальное кодовое расстояние dmin – это минимальное расстояние между разрешенными кодовыми комбинациями данного кода. Минимальное кодовое расстояние является основной характеристикой корректирующей способности кода. В первичных (безызбыточных) кодах все комбинации являются разрешенными, поэтому минимальное кодовое расстояние для них равно единице (dmin =1). Такие коды не способны обнаруживать и исправлять ошибки. Для того чтобы код обладал корректирующими способностями, его минимальное кодовое расстояние должно быть не менее двух (dmin ³2).

dmin ³ s +1 .                                                 (5.4)

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

dmin ³2t +1 .                                               (5.5)

Например, из (5.4) и (5.5) следует, что для обнаружения однократных ошибок (s = 1) требуется код с dmin = 2, а для того чтобы исправить такие ошибки, требуется код с кодовым расстоянием dmin = 3.

Для обнаружения s ошибок и исправления t ошибок должно выполняться условие

dmin ³ s + t +1 .                                            (5.6)

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

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

,
(8.57)

При других значениях
числа информационных символов т
получаются
так называемые усеченные
(или
укороченные)
коды Хэмминга.
Так, для
международ­ного телеграфного кода
МТК-2, имеющего 5 информационных символов,
по­требуется использование
корректирующего кода (9,5), являющегося
усеченным от классического кода Хэмминга
(15,11), так как число символов в этом коде
уменьшается (укорачивается) на 6. Для
примера рассмотрим код Хэмминга (7,4).

В простейшем
варианте при заданных четырех (т=4)
информационных символах

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Читайте также:  Что означает отсутствие модуля Ci cam и код ошибки 18?

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

В соответствии с
этим алгоритмом определения значений
проверочных символов

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

в табл. 8.13 приведены все возможные 16
кодовых слов кода Хэмминга (7,4).

Таблица 8.13. Кодовые
комбинации кода Хэмминга (7,4)

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Таблица 8.14.
Производящая матрица

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

в канонической форме

Транспонированная
проверочная матрица будет иметь вид

Предположим, что
на вход декодера для (7,4)-кода Хэмминга
поступает кодовое слово

Апостроф означает,
что любой символ слова может быть искажен
помехой в канале связи и возникает
ошибка

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

В декодере в режиме
исправления ошибок строится
последовательность:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

– результат декодирования (синдром),
который в данном случае является
трехсимвольным.

Символы синдрома
можно так же получить с использованием
следующей процедуры

В данном случае
синдром

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Число возможных
синдромов определяется выражением

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

При числе проверочных
символов

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

имеется восемь возможных синдромов (23
= 8). Нулевой синдром (000) указывает на то,
что ошибки при приеме от­сутствуют
или не обнаружены. Всякому ненулевому
синдрому соответствует определенная
конфигурация ошибок, которая и
исправляется. Классические кодыХэмминга
имеют число синдромов, точно равное их
необходимому числу, позволяют исправить
все однократные ошибки в любом
информативном и проверочном символах
и включают один нулевой синдром. Такие
коды называются плотноупакованными.

Для рассматриваемого
кода (7,4) в табл. 8.15 представлены ненулевые
синд­ромы и соответствующие конфигурации
ошибок.

Таблица 8.15. Ненулевые
синд­ромы и соответствующие конфигурации
ошибок для кода (7,4)

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

,
к которой приписывается транспонированная
проверочная матрица.

При определении
синдрома в проверочной матрице находится
комбинация синдрома. Искаженный разряд
– это разряд в данной строке, в которой
стоит «1». Искаженный разряд исправляем
посредством сложения строки в матрице
ошибок полученной комбинации.

Пример. Для кода
(7,4) задана комбинация

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Составляется
матрица одиночных ошибок

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Под воздействием
помех принята комбинация

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Идея построения
подобного корректирующего кода,
естественно, не меня­ется при
перестановке позиций символов в кодовых
словах. Все такие варианты также
называются кодами Хэмминга (7,4). Часто
проверочные разряды располагают не в
начале или конце информационных разрядов,
а в определенных местах. Рассмотрим
методику построения такого кода на
примере кода (7,4). Переведем
номера разрядов в двоичную систему
счисления и поставим им в соответствие
проверочные и информационные разряды
(табл.8.16).

Таблица 8.16.
Места расположения информационных и
проверочных разрядов и формирование
проверочных разрядов для кода Хэмминга
(7,4)

Т.е. 1-й проверочный
разряд

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

расположен там, где номер разряда имеет
только одну 1 и к тому же на 1-м месте. Ему
соответствует разряд под номером 1.
Второй проверочный разряд

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

расположен там, где номер разряда имеет
так же только одну 1 и к тому же на 2-м
месте. Ему соответствует разряд под
номером 2. Третий проверочный разряд

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

расположен там, где номер разряда имеет
так же только одну 1 и к тому же на 3-м
месте. Ему соответствует разряд под
номером 4. Оставшиеся разряды 3-й, 5-й, 6-й
и 7-й заполняем информациоными разрядами.

Выпишем разряды,
у которых
первый разряд равен 1:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

= 1, 3, 5, 7.

Выпишем разряды,
у которых
второй разряд равен 1:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

= 2, 3, 6, 7.

Выпишем разряды,
у которых
третий разряд равен 1:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Для
получения первого проверочного разряда
суммируем все разряды первой строки

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Для
получения второго проверочного разряда
суммируем все разряды второй строки

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Для
получения третьего проверочного разряда
суммируем все разряды третьей строки

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

При этом синдром
укажет номер искаженного разряда. Так,
если синдром равен

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

0
1 1, то искажен третий разряд. Ему
соответствует 1-й информационный символ.

Усеченные коды
являются неплотно
упакованными,
так как число
синдромов у них превышает необходимое.
Так, в коде (9,5) при четырех проверочных
символах число синдромов будет равно
24
=16, в то время как необходимо всего 10.
Лишние 6 синдромов свидетельствуют о
неполной упаковке кода (9,5).

Рассмотрим методику
формирования проверочных разрядов на
примере усеченного кода (9,5). В коде (9,5)
имеется 9 разрядов, 5 из которых являются
информационными. Пронумеруем разряды
в десятичной и двоичной системе счисления
(табл.8.17). Номерам разрядов в двоичной
системе будут соответствовать синдромы.

Таблица 8.17. Места
расположения информационных и проверочных
разрядов и формирование проверочных
разрядов для кода Хэмминга (9,5)

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

расположим на 1-м месте (№ разряда в
двоичной системе – 0001),

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

на 2-м (0010),

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

на 4-м (0100) и

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

на 8-м (1000). Информационные разряды
расположим на оставшихся местах.
Проверочный разряд

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

получим суммированием информационных
разрядов, которым соответствует номер
с единицей в 1- разряде двоичной системы
счисления

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

получим суммированием информационных
разрядов, которым соответствует номер
с единицей во 2- разряде двоичной системы

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

.
Для формирования разряда

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

остался один информационный разряд

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

возьмем еще какой-нибудь разряд, например,

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

,
который также можно исключить из
формирования

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

.
Если же мы исключили

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

и ввели в

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

,
то его номер также должен быть изменен.
Поэтому теперь

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Имеется 5
информационных разрядов

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Рассчитаем
количество проверочных разрядов

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Необходимо, чтобы
выполнялось условие:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

15-5=10.
210
≥ 15+1

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

1
1 0 1 0

Закодированное
сообщение будет иметь вид:

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

.
Им соответствуют номера разрядов 0 0 1
1, 0 1 0 1 и 1 1 1 0 соответственно. Просуммируем
эти номера и получим проверочные разряды
(табл. 8.18).

Таблица 8.18. Правило
формирования проверочных разрядов

Пусть под воздействием
помех в данной комбинации исказился
7=й разряд, т.е.

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

1
1 1 0.

Смотрим
в таблицу 8.17 и ищем синдром 1 1 1 0 и
определяем, что ему соответствует 7-й
разряд. Исправляем 7-й разряд 0 0 1 0 1 0 1
1 0. Сообщение исправлено. Исключаем
проверочные символы: 1 1 0 1 0.

Расширенные коды
Хэммингаполучают в
результате дополнения кодов с

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

За показатель
помехоустойчивости кода Хэмминга примем
вероятность приёма кодовой комбинации
с ошибками.

Расчёт вероятности
ошибки произведём для семиэлементного
кода, считая искажения символов в кодовых
комбинациях равновероятными и
независимыми.

Приём с ошибкой
при применении кода Хемминга с исправлением
одиночной ошибки будет в том случае,
если искажено более одного символа. В
соответствии с этим вероятность искажения
кодовой комбинации равна

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код


вероятность возникновения одной ошибки.

Соседние файлы в папке Пособие ТЕЗ_рус12

Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей

столбцов, причем столбцами H(n,k) являются все различные ненулевые двоичные последовательности длины m (m – разрядные двоичные числа от 1 до

Длина кодовой комбинации кода Хэмминга равна

Число информационных элементов определяется как

Итак, код Хэмминга полностью задается числом m – количеством проверочных элементов в кодовой комбинации.

Зная вид матрицы H(n,k), можно определить корректирующие свойства (n, k) – кода Хэмминга. Так как все столбцы матрицы проверок различны, то никакие два столбца H(n,k) не являются линейно зависимыми. Наряду с этим, для любого числа m всегда можно указать три столбца матрицы H(n,k), которые линейно зависимы, например, столбцы, соответствующие числам 1, 2, 3. Следовательно, для любого (n, k) – кода Хэмминга dmin=3.

Код Хэмминга является одним из немногочисленных примеров совершенного кода.

Действительно, поскольку (n, k) – код Хэмминга исправляет все одиночные ошибки, то все образцы одиночных ошибок (а их всего насчитывается

вариантов) должны разместиться в различных смежных классах, число которых также равно

При фиксированном числе

можно построить код Хэмминга любой длины (

) путем укорочения (n, k) – кода. Укорочение не уменьшает минимальное кодовое расстояние. В силу того, что для любого числа n существует код Хэмминга, любой групповой код с исправлением одиночных ошибок принято называть кодом Хэмминга.

Пример 5.13. Определим параметры кодов Хэмминга естественной длины для различных значений m. Результаты представим в виде таблицы.

Очевидно, что минимальная длина кода Хэмминга, имеющего практическое значение, есть 3. При увеличении n отношение

Пример 5.14. Рассмотрим код Хэмминга (7,4). Матрица проверок этого кода состоит из 7 трехразрядных двоичных чисел от 1 до 7:

Из рассмотрения этой матрицы видно, что минимальное число линейно зависимых столбцов равно 3( к примеру 1, 2 и 3), следовательно, dmin=3.

В том случае, когда столбцы матрицы H(n,k) – кода Хэмминга есть упорядоченная запись m – разрядных двоичных чисел, декодирование осуществляется оригинальным образом. В результате вычисления проверочного соотношения для кодовой комбинации

, имеющей одиночную ошибку, получается синдром

в точности равный номеру элемента, в котором произошла ошибка.

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

Пример 5.15. Пусть приемник УЗО системы передачи данных зарегистрировал комбинацию

т.е. ошибка в четвертом элементе и кодовая комбинация кода (7,4), которая была передана, имеет вид:

Путем несложных преобразований из (n, k) – кода Хэмминга с dmin=3 можно получить (n+1, k) – код Хэмминга с dmin=4.

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

Матрица проверок для (n+1, k) – кода Хэмминга с dmin=4 получается из матрицы проверок (n, k) – кода с dmin=3 путем введения дополнительной строки из (n+1)-ой единицы.

Так как размерность матрицы проверок кода с dmin=4 должна быть равна

, то к каждой строке матрицы проверок кода с dmin=3, необходимо добавить один нулевой элемент для того, чтобы не нарушить введенные ранее проверки. Матрица проверок для (n+1, k) – кода dmin=4 имеет вид:

Рассмотренная процедура, приведшая к удлинению кодовой комбинации на один разряд при увеличении dmin на 1 единицу, получила название удлинения кода (1- удлинение).Удлинению могут быть подвергнуты и другие коды, например, коды Рида-Соломона.

Читайте также:  Код ошибки 80070422 брандмауэр

Пример 5.16. Построить код Хэмминга (8,4) с dmin=4 на основе матрицы проверок кода (7,4).

По виду матрицы

можно сделать вывод о том, что в коде (7,4) осуществляется 3 независимые проверки на четность.

Каждая из строк определяет элементы кодовой комбинации, охваченные одной проверкой.

Таким образом, матрице

Для того, чтобы получить код (8,4) с dmin=4 вводим еще одну проверку по всем элементам кодовой комбинации, а результат этой проверки записывается в виде дополнительного 8-го элемента:

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

Определим известным способом dmin (8,4) – кода. Из рассмотрения тех столбцов, сумма которых давала нулевой столбец в (7,4) – коде, видно, что с добавлением 4-ой строки они перестали быть линейно зависимыми. Теперь уже число линейно зависимых столбцов должно быть четным и минимум 4, например, 3 первые столбца и последний. Таким образом, для полученного кода Хэмминга (8,4) dmin=4.

До сих пор мы еще не разделили элементы кодовой комбинации на информационные и проверочные. Наиболее рационально, по-видимому, это можно сделать следующим образом. Желательно, чтобы каждое проверочное соотношение однозначно определяло проверочный элемент как результат проверки на четность некоторой совокупности информационных элементов. В таком случае мы получили бы возможность определять значение проверочного элемента наиболее простым образом – решением одного линейного уравнения с одним неизвестным. Для этого при упорядоченной записи столбцов матрицы H(n,k) в качестве проверочных элементов необходимо брать элементы с номерами 2i, где i изменяется от 0 до m-1, так как именно эти столбцы содержат только по одной единице. Последнее свидетельствует о том, что элементы с номерами 2i входят только в одну проверку и, следовательно, они могут быть взяты в качестве проверочных.

Пример 5.17. Определить местоположение проверочных элементов к коде Хэмминга (7,4).

Зная места проверочных элементов, легко привести матрицу H(n,k) кода Хэмминга к канонической форме.

Для этого необходимо столбцы с номерами 2i, где

Пример 5.18. Преобразовать матрицу

Переставим столбцы: 4-ый на место 1-го, 1-ый на место 3-го, а 3-ий на место 4-го:

Это и есть каноническая форма матрицы

. Сравнение ее с исходной матрицей

показывает, что местам информационных элементов в канонической форме соответствуют столбцы с номерами 3, 5, 6, 7, а местам проверочных элементов – столбцы 4, 2, 1.

При этом связи между информационными и избыточными элементами сохранились с учётом их перестановки:

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

Оценим эффективность кодов Хэмминга.

Такие коды используются либо для исправления ошибки кратности t=1, либо для гарантийного обнаружения ошибок кратности S=2. Соответственно, вероятность ошибки для этих случаев в канале с группированием ошибок равна:

Выигрыш по достоверности по сравнению с простыми кодами той же длины составляет:

Для таких кодов возможны два режима – исправление однократных ошибок и обнаружение ошибок и только обнаружение ошибок. Вероятность ошибки для этих режимов в случае группирования ошибок равна:

Выигрыш по достоверности по сравнению с простым кодом той же длины составляет:

На основе (n, n-1) – кодов с dmin=2 или кодов Хэмминга с dmin=3 и dmin=4 можно построить коды с более высокими корректирующими свойствами. Для этой цели, наряду с защитой каждой передаваемой комбинации описанным выше способом, осуществляют помехоустойчивое кодирование одноименных разрядов групп передаваемых комбинаций. Процесс кодирования можно пояснить при помощи рис. 5.6.

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

5 эл. комбинация

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

Теорема 5.3. Минимальное кодовое расстояние итеративного кода равно произведению минимальных кодовых расстояний, кодов, его составляющих.

Действительно, если в случае двух проверок минимальный вес одного кода равен

, а другого

, то вектор итеративного кода имеет, по крайней мере,

единиц в каждой строке и

элементов в каждом столбце и, следовательно, не менее

Аналогичные рассуждения можно продолжить и на случай большего числа проверок.

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

Пусть GA – порождающая матрица кода, используемого для проверки по строкам, а GВ – порождающая матрица кода, используемого для проверки по столбцам, тогда порождающая матрица итеративного кода (GAВ) имеет вид:

означает, что на местах “1” в матрице GA записывается матрица GВ, а вместо “0” записывается матрица из одних нулей, размеры которой равны размерам GВ. Так, например, если для проверки по строкам и столбцам используется (6, 5) – код с проверкой на четность, то

  • Исправление ошибок в помехоустойчивом кодировании
  • Параметры помехоустойчивого кодирования
  • Контроль чётности
  • Классификация помехоустойчивых кодов
  • Код Хэмминга
  • Помехоустойчивые коды

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Рассмотрим пример CD диска. Там информация хранится прямо на поверхности диска, в углублениях, из-за того, что все дорожки на поверхности, часто диск хватаем пальцами, елозим по столу и из-за этого без помехоустойчивого кодирования, информацию извлечь не получится.

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Использование кодирования позволяет извлекать информацию без потерь даже с поврежденного CD/DVD диска, когда какая либо область становится недоступной для считывания.

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

  • запрос повторной передачи (Automatic Repeat reQuest, ARQ): с помощью помехоустойчивого кода выполняется только обнаружение ошибок, при их наличии производится запрос на повторную передачу пакета данных;
  • прямое исправление ошибок (Forward Error Correction, FEC): производится декодирование помехоустойчивого кода, т. е. исправление ошибок с его помощью.

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

Исправление ошибок в помехоустойчивом кодировании

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

Простейший пример – мажоритарный метод, он же многократная передача, в котором один символ передается многократно, а на приемной стороне принимается решение о том символе, количество которых больше.

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Необходимо найти ошибку с помощью голосования, каких символов больше, символов В или символов С? Явно символов В больше, чем символов С, соответственно принимаем решение, что передавался символ В, а символ С ошибочный.

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

Параметры помехоустойчивого кодирования

скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

  • где n – количество символов закодированного сообщения (результата кодирования);
  • m – количество проверочных символов, добавляемых при кодировании;
  • k – количество информационных символов.

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов,  Рида-Соломона (15, 11) и т.д.

кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

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

Контроль чётности

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

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

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

Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности.

Прямоугольный код – код с контролем четности, позволяющий исправить одну ошибку:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Классификация помехоустойчивых кодов

  • Непрерывные — процесс кодирования и декодирования носит непрерывный характер. Сверточный код является частным случаем непрерывного кода. На вход кодера поступил один символ, соответственно, появилось несколько на выходе, т.е. на каждый входной символ формируется несколько выходных, так как добавляется избыточность.
  • Блочные (Блоковые) — процесс кодирования и декодирования осуществляется по блокам. С точки зрения понимания работы, блочный код проще, разбиваем код на блоки и каждый блок кодируется в отдельности.
Читайте также:  Код ошибки матиз р0404

По используемому алфавиту:

  • Двоичные. Оперируют битами.
  • Не двоичные (код Рида-Соломона). Оперируют более размерными символами. Если изначально информация двоичная, нужно эти биты превратить в символы. Например, есть последовательность 110 110 010 100 и нужно их преобразовать из двоичных символов в не двоичные, берем группы по 3 бита — это будет один символ, 6, 6, 2, 4 — с этими не двоичными символами работают не двоичные помехоустойчивые коды.

Блочные коды делятся на

  • Систематические  — отдельно не измененные информационные символы, отдельно проверочные символы. Если на входе кодера присутствует блок из k символов, и в процессе кодирования сформировали еще какое-то количество проверочных символов и проверочные символы ставим рядом к информационным в конец или в начало. Выходной блок на выходе кодера будет состоять из информационных символов и проверочных.
  • Несистематические — символы исходного сообщения в явном виде не присутствуют. На вход пришел блок k, на выходе получили блок размером n, блок на выходе кодера не будет содержать в себе исходных данных.

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Код Хэмминга

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности.

Декодирование кода Хэмминга

Декодирование происходит через вычисление синдрома по выражениям:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Синдром это сложение бит по модулю два. Если синдром не нулевой, то исправление ошибки происходит по таблице декодирования:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

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

Помехоустойчивые коды

Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.

  • n — количество символов на входе.
  • k — количество символов на выходе.
  • t — кратность исправляемых ошибок.
  • Отношение k/n — скорость кода.
  • G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

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

Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость.

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель.

Компромиссы при использовании помехоустойчивых кодов

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

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

  • Достоверность vs полоса пропускания.
  • Мощность vs полоса пропускания.
  • Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

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

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

Пример блочного перемежения:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.

Корректирующие коды Хемминга.

Построение кодов Хемминга базируется
на принципе проверки на чётность веса
W(числа единичных
символов) в информационной группе
кодового блока.

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

В таком коде к кодовым комбинациям
безизбыточного первичного двоичного
m- разрядного кода
добавляется один дополнительный разряд
(символ проверки на чётность, называемый
проверочным, или контрольным). Если
число символов “1” исходной кодовой
комбинации чётное, то в дополнительном
разряде формируют контрольный символ
0, а если число символов “1” нечётное,
то в дополнительном разряде формируют
символ 1. В результате общее число
символов “1” в любой передаваемой
кодовой комбинации всегда будет чётным.

Таким образом, правило формирования
проверочного символа сводится к
следующему:

где i- соответствующий
информационный символ (0 или 1),m- общее их число а под операцией “”
здесь и далее понимается сложение поmod2. Очевидно, что добавление
дополнительного разряда увеличивает
общее число возможных комбинаций вдвое
по сравнению с числом комбинаций
исходного первичного кода, а условие
чётности разделяет все комбинации на
разрешённые и неразрешённые. Код с
проверкой на чётность позволяет
обнаруживать одиночную ошибку при
приёме кодовой комбинации, так как такая
ошибка нарушает условие чётности,
переводя разрешённую комбинацию в
запрещённую.

Критерием правильности принятой
комбинации является равенство нулю
результата Sсуммирования
поmod2 всехnсимволов
кода, включая проверочный символk1.
При наличии одиночной ошибкиSпринимает значение 1:

Этот код является (m+1,m) – кодом, или (n,n-1) – кодом. Минимальное
расстояние кода равно двум (dmin= 2), и, следовательно, никакие ошибки не
могут быть исправлены. Простой код с
проверкой на чётность может использоваться
только для обнаружения (но не исправления)
однократных ошибок.

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

При других значениях числа информационных
символов mполучаются
так называемые усечённые (укороченные)
коды Хемминга. Так, для международного
телеграфного кода МТК-2 , имеющего 5
информационных символов, потребуется
использование корректирующего кода
(9,5), являющегося усечённым от классического
кода Хемминга (15,11), так как число символов
в этом коде уменьшается (укорачивается)
на 6. Для примера рассмотрим код Хемминга
(7,4), который можно сформировать и описать
с помощью кодера, представленного на
рис.13.1. В
простейшем варианте при заданных четырёх
(m = 4)
информационных символах (i1,i2,i3,i4) будем полагать,
что они сгруппированы в начале кодового
слова, хотя это и не обязательно. Дополним
эти информационные символы тремя
проверочными символами (k= 3), задавая их следующими равенствами
проверки на чётность, которые определяются
соответствующими алгоритмами. Известно,
что кодовое расстояние равно минимальному
числу проверок, в которые входит
информационный символ плюс один. В
рассматриваемом кодеdmin.
Следовательно каждый информационный
символ должен входить минимум в две
проверки. Определим правило формирования
проверочных символов следующий образом:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

В соответствии с этим алгоритмом
определения значений проверочных
символов kiна рис.13.3 приведены все возможные 16
кодовых слов (7,4) – кода Хемминга.

На рис. 13.2приведена схема декодера для (7,4) – кода
Хемминга, на вход которого поступает
кодовое слово

Апостроф означает, что любой символ
слова может быть искажён помехой в
канале передачи.

В декодере в режиме исправления ошибок
строится последовательность:

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Трёхсимвольная последовательность
(s1, s2, s3)
называется синдромом. Термин “синдром”
используется и в медицине, где он
обозначает сочетание признаков,
характерных для определённого заболевания.
В данном случае синдромS= (s1, s2,s3)
представляет собой сочетание результатов
проверки на чётность соответствующих
символов кодовой группы и характеризует
определённую конфигурацию ошибок
(вектор ошибок).

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Рис.13.1. Кодер для простого (7,4) – кода
Хемминга

Помехоустойчивый код имеет dmin 4 сколько ошибок позволяет гарантированно исправить такой код

Рис.13.2. Декодер для простого (7,4) – кода
Хемминга

Рис.13.3. Кодовые слова код (7,4) – кода
Хемминга

Число возможных синдромов определяется
выражением

S = 2k. (13.20)

При числе проверочных символов k= 3 имеется восемь возможных синдромов
(23= 8). Нулевой синдром (000) указывает
на то, что ошибки при приёме отсутствуют
или не обнаружены. Всякому ненулевому
синдрому соответствует определённая
конфигурация ошибок, которая и
исправляется. Классические коды Хемминга
(13.19) имеют число синдромов, точно равное
их необходимому числу, позволяют
исправить все однократные ошибки в
любом информативном и проверочном
символах и включают один нулевой синдром.
Такие коды называются плотноупакованными.

Усечённые коды являются неплотноупакованными,
так как число синдромов у них превышает
необходимое. Так, в коде (9,5) при четырёх
проверочных символах число синдромов
будет равно 24=16, в то время как
необходимо всего 10. Лишние 6 синдромов
свидетельствуют о неполной упаковке
кода (9,5).

Для рассматриваемого кода (7,4) в табл.13.1
представлены ненулевые синдромы и
соответствующие конфигурации ошибок.

Таким образом, код (7,4) позволяет исправить
все одиночные ошибки. Простая проверка
показывает, что каждая из ошибок имеет
свой единственный синдром. При этом
возможно создание такого цифрового
корректора ошибок (дешифратора синдрома),
который по соответствующему синдрому
исправляет соответствующий символ в
принятой кодовой группе. После внесения
исправления проверочные символы kiможно на выход декодера (рис.13.2) не
выводить. Две или более ошибки превышают
возможности корректирующего кода
Хемминга, и декодер будет ошибаться.
Это означает, что он будет вносить
неправильные исправления и выдавать
искажённые информационные символы.

Идея построения подобного корректирующего
кода, естественно, не меняется при
перестановке позиций символов в кодовых
словах. Все такие варианты также
называются (7,4) – кодами Хемминга.

Расширенные коды Хеммингастроятся
в результате дополнения кодов сdmin= 3 общей проверкой каждой из кодовых
комбинаций на чётность, т.е. ещё одним
проверочным символом. Это позволяет
увеличить минимальное кодовое расстояние
доdmin= 4.

Соседние файлы в папке ЛБ_3

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *