По курсу Теория информационных процессов и систем

Таким образом все множество {U} кодовых слов разбивается на два множества: разрешенные и запрещенные или ошибочные слова.

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

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

3.2. Циклические коды

Код называется циклическим, если из того, что кодовое слово

U={ u_n-1, … , u₁, u₀}ÎM_разр

принадлежит множеству разрешенных слов следует, что слово

={ u_n-2, … , u₀, u_n-1,}ÎM_разр,

, полученное сдвигом cлова U влево по кругу тоже принадлежит множеству разрешенных слов.

Циклический код является частным случаем полиномиальных кодов, в которых кодовое слово U={u₀, u₁, … ,u_n-1} представляется в виде полинома от фиктивной переменной x с коэффициентами, равными числам кода. Если код построен над полем GF(2)={0,1}, то коэффициенты многочлена - числа 0 или 1:

.

Замечание. Степени фиктивной переменной x используются только для обозначения места соответствующей компоненты кодового вектора в регистре сдвига и никакой иной смысловой нагрузки не несут.

Например для кодового слова U=[1010101] значности n=7 полином имеет вид

.

Над полиномами определены все арифметические операции по обычным правилам, в том числе и умножение в столбик и деление углом. При этом сложение и вычитание коэффициентов выполняется как суммирование по модулю два. Если степень результата превышает (n-1), то результат приводится по модулю полинома (хⁿ+1).

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

Циклическая перестановка соответствует умножению u(x) на x. В нашем случае:

,

после приведения результата по модулю (хⁿ+1) (то есть деления u(x) на (х⁷+1)), получаем

u` (x) =x<sup>5</sup>+ x<sup>3</sup>+ x+1 и u`=[0101011],

что соответствует сдвигу битов кодового слова влево по кругу на один разряд.

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

Если не приводить полином, то при умножении полинома степени k на полином степени m степени полиномов складываются, и полином-результат имеет степень n=k+m. Исходное кодовое слово длины k при этом приобретает m новых разрядов, которые могут играть роль проверочных символов.

Циклический код это также блочный (n, k)-код, с длиной блока n, содержащий k информационных символов и m = n – k проверочных символов.

Операция кодирования для циклического кода состоит в умножении любого полинома p(x) степени k-1, соответствующего информационному подблоку на один и тот же полином g(x) степени (n-k), называемый образующим или порождающим или кодирующим полиномом (многочленом).

При этом число разрешенных кодовых слов остается прежним 2^k, а общее число возможных кодовых слов становится равным 2ⁿ.

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

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

Синдромный многочлен, определяемый как остаток от деления на порождающий многочлен g(x) зависит только от вектора ошибок:

, так как .

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

u(x) =+ e(x).

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

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

1. Вычисление синдрома

2. Определение ошибочных компонент принятого слова (вектора ошибки)

3. Исправление ошибки или выдача сообщения о наличии неисправимой ошиб­ки

3.3. Циклические коды Хемминга

Циклические коды Хемминга образуют подмножество циклических (n, k) – кодов. Они обладают всеми свойствами кодов Хемминга и еще дополнительными полезными свойствами.

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

Определение. Многочлен g(х) степени m называется неприводимым в поле GF(2)={0, 1}, если он не делится ни на какой многочлен с коэффициентами из GF(2) степени меньшей m, но большей нуля.

Определение. Неприводимый многочлен g(х) степени m называется примитив­ным, если наименьшая степень n, при которой многочлен хⁿ+ 1 делится на g(х) без остатка, равна n=2^m-1.

Другими словами, многочлен g(х), степени m называется примитивным, если

делится на g(х) без остатка,

а не делится на g(х) ни для какого значения .

Например, многочлен 1 + х² + х³ примитивен:

он делит х⁷ + 1, но не делит x^j+1 при j < 7.

Примитивен также многочлен 1 + х³ + х⁴ :

он делит х¹⁵ + 1, но не делит x^j+1 при j < 15.

С помощью порождающих многочленов g(х) можно строить порождающие и проверочные матрицы и таблицы синдромов для декодирования.

Утверждение. Для любого целого положительного числа m существует совершенный (n,k)-код Хэмминга, в котором n=2^m-1 или k =2^m-m-1.

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

1. Длины кодов увеличиваются с 2^n-1 до 2ⁿ, что удобно с точки зрения хранения и передачи информации,

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

3.4. Критерии оценки помехоустойчивости.

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

1. Помехоустойчивость кода

- собственное количество информации в факте необнаружения ошибки.

2. Коэффициент обнаружения

,

где M – ожидаемое общее число искаженных кодовых слов,

L - ожидаемое число исправленных кодовых слов,

N – число всех кодовых слов,

р_ош. – число вероятность появления ошибки,

р_обн.ош. – вероятность обнаружения и исправления ошибки.

Если R - ожидаемое число неисправленных искаженных кодовых слов, то R=M-L и .

Пусть вероятность искажения одного символа кода равна р.Найдем вероятности передачи без ошибки р₍₀₎ и однократной ошибки р₍₁₎ при которых гарантируется правильная передача простым кодом Хемминга.

.

(Для расширенного кода Хемминга выявляется и двухкратная ошибка с вероятностью ).

Вероятность ошибочной передачи – все остальное. С учетом того, что при больших n: (по разложению (1-р)ⁿ в ряд Тейлора):

Если исправляется одна ошибка, то по теоремам Хемминга можно одновременно обнаружить 2 ошибки. Расширенный код Хемминга позволяет дополнительно обнаружить еще одну ошибку. Вероятность появления необ­наруживаемых 3-х и 4-х кратных ошибок

и , где .

При малых значениях вероятности р при вычислении р_{необн.ош.} ошибки большей кратности можно не учитывать в силу их малой вероятности.

3.5. Определение значности кода.

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

Для заданного образующего полинома степени m количество добавляемых при кодировании проверочных символов равно m. Коды Хемминга исправляют одиночную ошибку в блоке. Это коды с . Соотношения для параметров кода n, k и m для них имеют вид:

и .

Отсюда длина блока выбирается из неравенства

n ≤ 2^m – 1,

а количество информационных символов в блоке k = n - m.

Коды, удовлетворяющие этому условию являются квазисовершенны­ми. Решить это уравнение относительно n здесь сложно, поэтому определим из него m=n-k:

(*).

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

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

3.6. Матричное задание циклических кодов.

Циклический код может быть задан порождающей и проверочной матрицами. Для их построения достаточно знать порождающий g(x) и проверочный h(x) многочлены. При этом проверочный многочлен вычислякется по порождающему:

Для несистематического циклического кода матрицы строятся цик­лическим сдви­гом порождающего и проверочного многочленов, т.е. путем их умножения на x.

При построении матрицы H_(n,k) старший коэффициент многочлена h(x) располагается справа.

и

Например представим в матричном виде. циклический (7,4)-код с порожда­ющим многочленом g(x)=x³+x+1 и проверочным многочленом

.

Порождающая G_(7,4) и проверочная H_(7,4) матрицы (n=7,k=4)-кода имеют вид:

,

Построенные таким образом матрицы не имеют систематического вида. Для получения матрицы G_(n,k) циклического кода в систематическом виде, то есть в виде , где I_k - единичная матрица; R_k,m - прямоугольная матрица, необходимо найти матрицу R_k,m. Ее строки r_i(x) (i=1, … ,.k) определяются следующими полиномами:

,

где R_g(x)[ ] – обозначает операцию получения остатка от деления на g(x), и a_i(x) – полином, соответствующий значению i-й строки матрицы I_k. Так как a_i(x)=x^k-i, то получаем, что a_i(x)x^m = x^m+k-i = x^n-i, то есть .

Для нашего примера. Матрица G_(n,k) для (7,4)-кода на основе порождающего многочлена g(x)=x³+x+1 в систематическом виде , строится так:

Поскольку ,

определим R_4,3, используя формулу . Первую строку получаем делением

или

Þ (101).

Для получения второй строки не надо снова делить углом, так как делимое совпадет с предыдущим случаем с точностью до последнего нуля. Поэтому для получения остатка от деления на х⁵ достаточно взять предпоследний остаток в предыдущем делении на х⁶ не снося очередной нуль. Таким способом определяется (111), (110) и (011). Последние две строки получаются из одного и того же остатка, убирая последовательно по одному нулю (добавляя при необходимости слева нули до трех символов), так как в этой строке были при делении снесены два нуля.

В результате получаем

Количество исправляемых ошибок в блоке определяется минимальным рассстоянием Хемминга d_min между разрешенными кодовыми словами. Минимальное расстояние для (n,k)-кода равно наименьшему числу линейно зависимых столбцов проверочной матрицы. Для нашего примера d_min (5,3)=2.

Проверочная матрица в систематическом виде строится на основе матрицы G_(n,k), а именно: .

Для нашего примера. Для нашего кода матрица H_(n,k) будет иметь вид:

.

Между порождающей и проверочной матрицами в систематическом виде существует однозначное соответствие, а именно , где 0 – матрица размерности kxm, у которой все элементы равны нулю.

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

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

Для нашего примера кодирование блока информационных символов Р=[110] дает блок помехоустойчивого кода U =11010]:

Произведение любого разрешенного кодового слова U на транспонированную проверочную матрицу дает вектор длины (n-k) с нулевыми координатами

.

Для нашего кода это произведение дает .

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

Произведение неразрешенного, т.е. с ошибкой, кодового слова на транспонирован­ную проверочную матрицу называется синдромным вектором и обозначается S.

Появление отличного от нулевого синдромного вектора является признаком ошибки. В этом случае декодирование предполагает исправление ошибки или выдачу сообщения о неисправимой ошибке.

Например. Пусть при передаче ко­дового слова, полученного в предыдущем примере, допущена одна ошибка и принято = [11000], то есть во втором символе ошибка. Соответствующий полином: =x⁴+x³.

Вычисляем синдром делением его на образующий полином g(x)=x³+x+1. Если нас интересует только остаток от деления, то мож­но вычис­лять его в столбик.

e(x)
x0=1
x	x
x2	x2
x3	x+1
x4	x2+ x
x5	x2+x+1
x6	x2+1

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

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

В нашем случае находим по таблице, что e(x) = x и исправляем ошибку:

u(x)=+e(x)=x⁴+x²+x+1.

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