определить в каком разряде принятого кодового вектора циклического кода имеется однократная ошибка

Определение места ошибки в КК циклического кода

Выбор образующего полинома

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

Непроводимыми называются такие полиномы, которые делятся без остатка только на 1 и сами на себя.

Кроме того, среди непроводимых полиномов, отбирают так называемые примитивные.

Примитивные полиномы выбираются из специальных таблиц.

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

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

Остаток при этом представляет собой разницу между искаженным и исправленным разрядами. Единицы в остатке стоят на местах искаженных разрядов в «подогнанной» циклическими сдвигами КК.

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

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

Алгоритм оптимального декодирования на основе анализа веса

1. Принятая КК делится на образующий полином

2. Если остаток нулевой, то КК выдается получателю. Если не нулевой, то выполняют п.3

4. Производим циклический сдвиг КК влево на один разряд. Делим полученную в результате сдвига КК на образующий полином. Если вес остатка w≤ t_u, то складываем остаток с КК и полученную КК сдвигаем вправо на один разряд – будет исправленная КК. Если w> t_u, то выполняется п.5

5. Повторяем п.4 до тех пор, пока не будет w≤ t_u. КК, полученная в результате последнего циклического сдвига влево, суммируется с последним остатком. Далее выполняется п.6

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

Пусть передаем КК 1001110 кода (7,4), образующий полином Р(х)=1011 (х 3 +х+1). Пусть в принятой КК искажен 4 разряд. d₀=3, т.е. код исправляет однократную ошибку t_u=1, т.е. приняли мы КК →1000110. Попытаемся обнаружить и исправить эту ошибку

1. Делим принятую КК на Р(х):

1000110 1011

1011 101

1111

1000

1011

Получим остаток 11, его вес равен 2> t_u=1

2. Производим сдвиг полученной КК влево на 1 разряд

0001101 1011

1011

3. Еще сдвигаем влево КК

0001101→0011010 делим на Р(х)

0011010

1011 1011

1100

4. Еще сдвигаем влево КК

0011010→0110100 делим на Р(х)

0110100 1011

1011

1100

1011

1110

5. Еще сдвигаем влево КК

0110100→1101000, делим на Р(х)

1101000 1011

1011

1100

1011

1110

1011

1010

1011

6. Складываем последнее делимое с остатком

1101000

1101001

7. Сдвинем эту КК вправо на 4 разряда, т.к. мы сдвигаем исходную КК влево на 4 разряда:

Получим исправленную КК – сравним с переданной: 1001110

Источник

Нахождение ошибок в циклическом коде

нахождение ошибок в коде, наследование
#include «stdafx.h» #include «conio.h» #include using namespace std; class.

Изменить порядок в циклическом коде
Добрый день! Написали примитивно программу, нужно исправить, так как при нажатии на кнопку.

Нахождение кратчайшего пути в «циклическом» массиве
Добрый вечер! Я пишу простую игру (на Java). Персонаж должен убегать от гангстера. Поле это.

Нахождение ошибок
Помогите найти ошибки и переделать код (Сложение чисел) using System.Collections.Generic;.

Решение

На хабре всё неплохо разжёвано, однако, основные термины считаются сами собой разумеющимися. Типа, «Это происходит вот так, а по какой причине именно так, Вам знать не обязательно».

[7, 4] означает, что в векторе всего 7 символов, 4 из которых информационные.

Код Хэмминга может быть классическим и усечённым.

Количество символов в классическом коде Хэмминга определяется количеством проверочных символов «r». Маркировка какого-либо кода Хэмминга определяется как

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

На Хабре в примере использован усечённый код Хэмминга [21, 16], который получается из классического кода Хэмминга [31, 26] отсечением десяти символов.

На хабре не объясняется, по какому принципу определяется номер ошибочного символа: собственно, а почему «N через N начиная с N», а не как-то ещё?

Не мудрено, что Вы запутались. Тем не менее, ещё раз перечитайте хабр.

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

Ваш вектор, проверочные символы обозначены красным цветом: 11 0 1 011.

Посимвольно, в виде таблицы:

Вычислим синдромы (проверочные суммы по модулю 2):

S_1=i_1\oplus i_3\oplus i_5\oplus i_7=1\oplus 0\oplus 0\oplus 1=0\\\\S_2=i_2\oplus i_3\oplus i_6\oplus i_7=1\oplus 0\oplus 1\oplus 1=1\\\\S_4=i_4\oplus i_5\oplus i_6\oplus i_7=1\oplus 0\oplus 1\oplus 1=1\\\\
» />

Синдромы удобнее нумеровать по степеням двойки (то есть, 1, 2, 4, 8, 16 и т.д., а не 1, 2, 3, 4 и т.д.), поскольку (если ошибка только одна) каждый из синдромов вычисляет один из двоичных разрядов номера ошибочного символа.

Для каждого синдрома суммируются те символы, у которых в двоичном представлении их номеров двоичный разряд с весом, равным номеру синдрома, установлен в 1 (это то самое «N через N начиная с N», но не в виде «закономерности», а какое оно есть на самом деле).

В синдром номер 2 попадают символы с номерами 2, 3, 6, 7, в двоичном представлении 0 1 0, 0 1 1, 1 1 0, 1 1 1. Обратите внимание, это все те, у которых 1 во втором разряде (пометил синим).

В синдром номер 4 попадают символы с номерами 4, 5, 6, 7, в двоичном представлении 1 00, 1 01, 1 10, 1 11. Обратите внимание, это все те, у которых 1 в третьем разряде (пометил синим).

Поэтому, если вектор содержит только одну ошибку, то двоичное число, составленное из синдромов, начиная со старшего (в данном случае S₄S₂S₁=110₍₂₎=6₍₁₀₎), и будет номером ошибочного символа, поскольку распределение символов по суммам синдромов сделано по весам разрядов двоичной системы счисления. Можно (это то же самое, но в «скрытой» форме) сложить номера синдромов, в которых произошло нарушение чётности, и получить номер символа, в котором произошла ошибка: 2+4=6.

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

Источник

Вопросы и задачи

1. Определить кодовое расстояние между комбинациями А иВ и вес каждой комбинации.

Пример. А = 0011011; В = 1000101.

Решение. Вес комбинации равен количеству единиц в слове: ш(А) = 4, ш(В) = 3. Для вычисления кодового расстояния сложим комбинации по модулю 2 и найдем вес суммы. А ® В = 1011110, ш(А ® В) = 6, d = 6.

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

Пример. А = 1011010; 6=1101111; С= 1011001.

Решение. d_min = min <4, 4, 2>= 2. Следовательно, в силу (4.2), любая однократная ошибка может быть обнаружена. Ошибки более высокой кратности могут не быть обнаружены. Гарантий исправления даже однократных ошибок в этом коде нет, так как не выполняется условие (4.3). Действительно, ошибки в 6-м или 7-м разрядах комбинаций А и С не исправляется. А вот ошибку в первом или 4-м разрядах можно обнаружить и исправить.

3. Код Хемминга (7,4) имеет порождающую матрицу:

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

Решение. Определим необходимое количество информационных разрядов из соотношения к > log 2000. к = 11.

По правилу Хемминга (г 2 log (п+ 1), для f = 1) определим, что для исправления однократных ошибок требуется 4 проверочных разряда, следовательно, надо строить (15,11)-код.

Из таблицы примитивных полиномов выбираем порождающий полином д(х) = (х 4 + х + 1), так как он проще других, обеспечивающих ту же корректирующую способность кода.

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

Определите синдром однократной ошибки в 3-м разряде принятой кодовой комбинации.

10. Помехоустойчивый декодер принял двоичную комбинацию U и вычислил вектор ошибки е. Определите переданное десятичное число.

11. Блочный код имеет порождающую матрицу G:

Определите синдром двукратной ошибки во втором и шестом разрядах принятого кодового слова.

Источник

Помехоустойчивое кодирование. Часть 1: код Хэмминга

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

Самый, пожалуй, известный код Хэмминга (7,4). Что значат эти цифры? Вторая – число бит информационного слова — то, что мы хотим передать в целости и сохранности. А первое – размер кодового слова: информация удобренная избыточностью. Кстати термины «информационное слово» и «кодовое слово», употребляются во всех 7-ми книгах по теории помехоустойчивого кодирования, которые мне довелось бегло пролистать.

Такой код исправляет 1 ошибку. И не важно где она возникла. Избыточность несёт в себе 3 бита информации, этого достаточно, чтобы указать на одно из 7 положений ошибки или показать, что её нет. То есть ровно 8 вариантов ответов мы ждём. А 8 = 2^3, вот как всё совпало.

Чтобы получить кодовое слово, нужно информационное слово представить в виде полинома и умножить его на порождающий полином g(x). Любое число, переведя в двоичный вид, можно представить в виде полинома. Это может показаться странным и у не подготовленного читателя сразу встаёт только один вопрос «да зачем же так усложнять?». Уверяю вас, он отпадёт сам собой, когда мы получим первые результаты.

К примеру информационное слово 1010, значение каждого его разряда это коэффициент в полиноме:

Во многих книгах пишут наоборот x+x^3. Не поддавайтесь на провокацию, это вносит только путаницу, ведь в записи числа 2-ичного, 16-ричного, младшие разряды идут справа, и сдвиги мы делаем влево/вправо ориентируясь на это. А теперь давайте умножим этот полином на порождающий полином. Порождающий полином специально для Хэмминга (7,4), встречайте: g(x)=x^3+x+1. Откуда он взялся? Ну пока считайте что он дан человечеству свыше, богами (объясню позже).

Если нужно складывать коэффициенты, то делаем по модулю 2: операция сложения заменяется на логическое исключающее или (XOR), то есть x^4+x^4=0. И в конечном итоге результат перемножения как видите из 4х членов. В двоичном виде это 1001110. Итак, получили кодовое слово, которое будем передавать на сторону по зашумлённому каналу. Замете, что перемножив информационное слово (1010) на порождающий полином (1011) как обычные числа – получим другой результат 1101110. Этого нам не надо, требуется именно «полиномиальное» перемножение. Программная реализация такого умножения очень простая. Нам потребуется 2 операции XOR и 2 сдвига влево (1й из которых на один разряд, второй на два, в соответствии с g(x)=1011):

Давайте теперь специально внесём ошибку в полученное кодовое слово. Например в 3-й разряд. Получиться повреждённое слово: 1000110.

Как расшифровать сообщение и исправить ошибку? Разумеется надо «полиномиально» разделить кодовое слово на g(x). Тут я уже не буду писать иксы. Помните что вычитание по модулю 2 — это то же самое что сложение, что в свою очередь, тоже самое что исключающее или. Поехали:

Нацело разделить не получилось, значит у нас есть ошибка (ну конечно же). Результат деления в таком случае нам без надобности. Остаток от деления является синдром, его размер равен размеру избыточности, поэтому мы дописали там ноль. В данном случае содержание синдрома нам никак не помогает найти местоположение повреждения. А жаль. Но если мы возьмём любое другое информационное слово, к примеру 1100. Точно так же перемножим его на g(x), получим 1110100, внесём ошибку в тот же самый разряд 1111100. Разделим на g(x) и получим в остатке тот же самый синдром 011. И я гарантирую вам, что к такому синдрому мы придём в обще для всех кодовых слов с ошибкой в 3-м разряде. Вывод напрашивается сам собой: можно составить таблицу синдромов для всех 7 ошибок, делая каждую из них специально и считая синдром.

В результате собираем список синдромов, и то на какую болезнь он указывает:

Теперь у нас всё есть. Нашли синдром, исправили ошибку, ещё раз поделили в данном случае 1001110 на 1011 и получили в частном наше долгожданное информационное слово 1010. В остатке после исправления уже будет 000. Таблица синдромов имеет право на жизнь в случае маленьких кодов. Но для кодов, исправляющих несколько ошибок – там список синдромов разрастается как чума. Поэтому рассмотрим метод «вылавливания ошибок» не имея на руках таблицы.

Внимательный читатель заметит, что первые 3 синдрома вполне однозначно указывают на положение ошибки. Это касается только тех синдромов, где одна единица. Кол-во единиц в синдроме называют его «весом». Опять вернёмся к злосчастной ошибке в 3м разряде. Там, как вы помните был синдром 011, его вес 2, нам не повезло. Сделаем финт ушами — циклический сдвиг кодового слова вправо. Остаток от деления 0100011 / 1011 будет равен 100, это «хороший синдром», указывает что ошибка во втором разряде. Но поскольку мы сделали один сдвиг, значит и ошибка сдвинулась на 1. Вот собственно и вся хитрость. Даже в случае жуткого невезения, когда ошибка в 6м разряде, вы, обливаясь потом, после 3 мучительных делений, но всё таки находите ошибку – это победа, лишь потому, что вы не использовали таблицу синдромов.

А как насчёт других кодов Хэмминга? Я бы сказал кодов Хэмминга бесконечное множество: (7,4), (15,11), (31,26),… (2^m-1, 2^m-1-m). Размер избыточности – m. Все они исправляют 1 ошибку, с ростом информационного слова растёт избыточность. Помехоустойчивость слабеет, но в случае слабых помех код весьма экономный. Ну ладно, а как мне найти порождающую функцию например для (15,11)? Резонный вопрос. Есть теорема, гласящая: порождающий многочлен циклического кода g(x) делит (x^n+1) без остатка. Где n – нашем случае размер кодового слова. Кроме того порождающий полином должен быть простым (делиться только на 1 и на самого себя без остатка), а его степень равна размеру избыточности. Можно показать, что для Хэмминга (7,4):

Этот код имеет целых 2 порождающих полинома. Не будет ошибкой использовать любой из них. Для остальных «хэммингов» используйте вот эту таблицу примитивных полиномов:

Соответственно для (15,11) порождающий многочлен g(x)=x^4+x+1. Ну а теперь переходим к десерту – к матрицам. С этого обычно начинают, но мы этим закончим. Для начала преобразую g(x) в матрицу, на которую можно умножить информационное слово, получив кодовое слово. Если g = 1011, то:

Называют её «порождающей матрицей». Дадим обозначение информационному слову d = 1010, а кодовое обозначим k, тогда:

Это довольно изящная формулировка. По быстродействию ещё быстрее, чем перемножение полиномов. Там нужно было делать сдвиги, а тут уже всё сдвинуто. Вектор d указывает нам: какие строки брать в расчёт. Самая нижняя строка матрицы – нулевая, строки нумеруются снизу вверх. Да, да, всё потому что младшие разряды располагаются справа и от этого никуда не деться. Так как d=1010, то я беру 1ю и 3ю строки, произвожу над ними операцию XOR и вуаля. Но это ещё не всё, приготовьтесь удивляться, существует ещё проверочная матрица H. Теперь перемножением вектора на матрицу мы можем получить синдром и никаких делений полиномов делать не надо.

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

Чтобы лучше понять саму природу исправления ошибок, сгенерируем в обще все 16 кодовых слов, ведь информационное слово состоит всего из 4х бит:

Посмотрите внимательно на кодовые слова, все они, отличаются друг от друга хотя бы на 3 бита. К примеру возьмёте слово 1011000, измените в нём любой бит, скажем первый, получиться 1011010. Вы не найдёте более на него похожего слова, чем 1011000. Как видите для формирования кодового слова не обязательно производить вычисления, достаточно иметь эту таблицу в памяти, если она мала. Показанное различие в 3 бита — называется минимальное «хэммингово расстояние», оно является характеристикой блокового кода, по нему судят сколько ошибок можно исправить, а именно (d-1)/2. В более общем виде код Хэмминга можно записать так (7,4,3). Отмечу только, что Хэммингово расстояние не является разностью между размерами кодового и информационного слов. Код Голея (23,12,7) исправляет 3 ошибки. Код (48, 36, 5) использовался в сотовой связи с временным разделением каналов (стандарт IS-54). Для кодов Рида-Соломона применима та же запись, но это уже недвоичные коды.

Список используемой литературы:

1. М. Вернер. Основы кодирования (Мир программирования) — 2004
2. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования (Мир связи) — 2006
3. Р. Блейхут. Теория и практика кодов, контролирующих ошибки — 1986

Источник