Циклические коды (ЦК)

1. Циклические корректриующие коды...………………………………………………………1

2. Построение ЦК

3. Определение параметров ЦК (ЦСК) по m,s,r

4. Определение параметров ЦК, обеспечивающих заданную вероятность передачи по каналу с шумом

5. Кодеры ЦСК

   1. Кодирование с помощью полинома h(x)

   2. Кодирование с помощью полинома g(x)

6. Декодеры ЦСК

   1. Декодеры Меггита

      1. Режим исправления и обнаружения ошибок

      2. Режим обнаружения ошибок

7. Примеры

   1. Пример 1

   2. Пример 2

   3. Пример 3

   4. Пример 4

   5. Пример 5

   6. Пример 6

   7. Пример 7

   8. Пример 8

   9. Пример 9

   10. Пример 10

   11. Пример 11

8. Справочные материалы

   1. Теоремы БЧХ

   2. Таблица неприводимых многочленов

1. Циклические коды (ЦК)

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

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

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

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

---

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

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

1.1 Циклические корректирующие коды

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

Циклической перестановкой называется такая перестановка, при которой все разряды смещаются в сторону старших разрядов, причем последний разряд переходит на место первого.

1.2 Построение ЦК

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

Циклическим сдвигом называется такой сдвиг, при котором все разряды смещаются в сторону старших разрядов, причем последний разряд переходит на место первого.

Пусть

Тогда после циклического сдвига получим

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

Пример 1

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

---

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

Пример 2

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

Кодовые комбинации циклического кода строятся так, чтобы соответствующие им полиномы делились без остатка на g(x). С другой стороны, циклический код может быть полностью определен многочленом h(x) степени m, где m – число информационных символов циклического кода:

(1)

n – число разрядов (длина) циклического кода (n = m + k):

Полином, соответствующий кодовой комбинации циклического кода, имеет вид:

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

Для циклических кодов Хемминга имеет место

Пример 3

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

1.3 Определение параметров ЦК(ЦСК) по m,s,r

Рассмотрим методику выбора параметра БЧХ-кода, исправляющего s независимых ошибок при известной длине информационной части кода m₁.

Исходя из первой и второй теоремы БЧХ, для известных m₁ и s` выбираем наименьшие h и , удовлетворяющие условию:

(2)

Учитывая, что:

(3)

Получим, согласно (2):

(4)

БЧХ-код , удовлетворяющий (4), является искомым БЧХ-кодом. Отметим, что соотношение (3) является границей существования (n,m,d) линейного кода (в том числе и циклического).

Выбираем порождающий полином:

(5)

Где m_i(x) – неприводимые полиномы степени не более h, которые отыскиваются по таблице неприводимых полиномов.

Переходим к четному минимальному кодовому расстоянию:

(6)

Находим порождающий полином:

(7)

Пример 4

1.4 Определение параметров ЦК, обеспечивающих заданную вероятность передачи по каналу с шумом

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

В данном разделе рассмотрим методику определения параметров (n,m,d) ближайшего табличного кода БЧХ-кода, удовлетворяющего заданным требованиям по вероятности передачи сообщений p_доп в канале без памяти (двоичный симметричный канал с независимыми ошибками) при известной вероятности ошибки на символ p. В качестве аналитической модели данного цифрового канал используется биномиальное распределение ошибок (модель 1):

---

или пуассоновское распределение ошибок (модель 2):

,

где p(i,n) – вероятность i-кратной ошибки, среди n передаваемых символов;

p – вероятность ошибки при передаче элементарного сигнала;

I₀ – среднее число ошибок среди n передаваемых символов,

В канале с независимыми ошибками, использующими для передачи информации ЦК (ЦСК), исправляющие s и менее ошибок, вероятностные показатели определяются следующим образом:

(8)

(9)

здесь n – длина кода (n,m) с d_min=2s+1, определяемая из границы существования БЧХ.

Пример 5

Для ЦК(ЦСК) с четным кодовым расстоянием d_min=2s+2:

(10)

p_np,p_mp,p_{cm –} соответственно вероятности правильной передачи сообщения, трансформация сообщения (необнаруженной ошибки), стирания сообщения (обнаруженной ошибки).

Приведенные соотношения положены в основу алгоритма и программ автоматизированного проектирования цифровых каналов, использующих ЦК (ЦСК) для обеспечения заданной верности передачи (БЧХ-коды являются оптимальными блоковыми кодами в каналах с независимыми ошибками).

Пример 6

1.5 Кодеры ЦСК

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

Возможны два способа кодирования информации в систематическом коде: кодирование с помощью полинома h(x) и кодирование с помощью полиному g(x).

1.5.1 Кодирование с помощью полинома h(x)

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

В основе данного вида кодирования лежит рекуррентное соотношение, первые n символов которого и являются элементами искомого систематического кода:

(11)

Где h_j – коэффициент полинома;

- произвольно выбранные символы (в частности m – информационных символов) кодовой последовательности.

При использовании соотношения (11) кодовый вектор циклического кода имеет вид:

(12)

Следовательно, контрольными символами являются:

Из (11) имеем:

(11`)

Тогда:

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

Для реализации данного способа кодирования требуется регистр, сдвига с логическими обратными связями, содержащий m ячеек памяти. Вид обратной связи полностью определяется полиномом h(x) (смотри соотношение 11 и 11`). На рис.1 приведена обобщенная структурная схема, указанного кодирующего регистра (кодопреобразователя).

---

Рис.1. Обобщенная структура кодера на основе полинома h(x)

(m₂ – сумматор по модулю 2)

Работа устройства. В исходном состоянии регистр записывают m информационных разрядов. Далее на регистр от генератора тактовых (сдвиговых) импульсов поступает n импульсов. С выхода 1-й ячейки памяти (D₀) регистра в линию связи поступают кодовые элементы систематического циклического кода, начиная с информационных символов. При этом на каждом такте в m-ю ячейку регистра записывается символ, значение которого определяется на основании выражения (11`).

Пример 7

1.5.2 Кодирование с помощью полинома g(x)

В основе данного метода кодирования лежит тот факт, что кодовый вектор должен делиться без остатка на g(x), т.е. (q(x) – частное от деления A(x) на g(x)). Нужно преобразовывать кодовый вектор A(x), принадлежащий систематическому циклическому коду. Пусть V(x) – произвольно выбранный информационный вектор:

,

При рассмотрении данного метода в отличие от предыдущего кодовый вектор циклического кода имеет вид:

т.е. индексы при a_iсовпадают с показателями степени x. Согласно принятому выше определению, информационные символы располагаются при .

Тогда преобразованный вектор:

Согласно алгоритму деления:

Где r(x) – остаток от деления, причем степени r(x) меньше, чем n-m = степень многочлена g(x).

Отсюда:

Следовательно, и есть искомый вектор, у которого V(x) – информационная часть, а r(x) – избыточная часть.

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

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

Рис.2. Обобщенная структурная схема кодера на основе полинома g(x) c с предварительным умножением

Работа схемы. На вход схемы поступают m информационных символов (ключ К₁ открыт, К₂ закрыт). Чтобы автоматически выполнить умножение вектора V(x) на x^k данный вектор подается сразу же на выход k-ой ЯП регистра (D_k). Как показано на рис.2. Одновременно информационные символы поступают в канал связи. Через m тактов после начала функционирования в регистре записывается остаток r(x) от деления вектора на g(x). На (m+1)-м такте происходит изменение состояния ключей (ключ К₁ закрывается, К₂ открывается) и образовавшиеся проверочные символы выталкиваются из регистра в канал связи вслед за уже переданными информационными символами.

Пример 8

Для перехода от циклического кода с d_min(нечетным), к коду с d_min+1(четным), то есть к коду, исправляющему s ошибок и обнаруживающему r ошибок, достаточно умножить порождающий полином первого кода g(x) на (1+х), что равносильно введению общей проверки на четность.

---

Смотрите также файлы

• Как развивать креативное мышление у дошкольников и в школе.docx

• Как развить креативное мышление школьников.docx

• Креативность в массы или массовая креативность.docx

• О педагогике.docx

• О педагогике.docx