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

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

Пример 9

1.6 Декодеры ЦСК

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

1. Алгебраические:

   1. Синдромное декодирование

   2. Мажоритарное декодирование

   3. Пороговое декодирование

2. Неалгебраические:

   1. Алгоритм Питерсона

   2. Алгоритм Берлекемпа с процедурой Чень.

К наиболее простым способам декодирования относятся синдромное и мажоритарное.

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

Декодеры Меггита реализуют алгоритм синдромного декодирования. Декодирование с целью обнаружения и исправления ошибок состоит в делении на g`(x) полинома, соответствующего принятому сообщению. При отсутствии ошибок деление будет выполнено без остатка; в противном случае наличие ненулевого остатка укажет на то, что произошли ошибки. Для обеспечения возможности исправления ошибки каждому виду ошибки должен соответствовать свой, отличный от других, остаток, по которому селектор (декомбинатор - k входовой конъюнктор) ошибки мог бы выработать необходимые сигналы исправления. На рис.3 приведена обобщенная схема декодера Меггита. Сложность при реализации данного способа декодирования заключается в правильной настройке селектора.

Рис.3. Обобщенная структурная схема декодера Меггита

Обработка циклического кода в декодирующем устройстве рис.3, осуществляется в два этапа:

1. В течении первых n тактов производиться деление принятой кодовой комбинации на g(x) (формируется синдром в генераторе синдрома) и одновременно эта комбинация записывается в приемный регистр.

2. В течении следующих n тактов осуществляется исправление ошибок.

На n+1-ом такте открывается селектор и начинает выталкиваться код из буферного регистра. При появлении ошибки селектор вырабатывает истинное значение ошибочного символа с помощью сумматора по mod 2: , т.к. мы внесли коррекцию в вектор, то должны внести в генератор синдрома единицу (осуществляется с помощью обратной связи, на рис.3 обозначена пунктирной стрелкой).

Использование многотактовой коррекции позволяет сократить объем

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

---

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

Существует два алгоритма решения.

1. Частный алгоритм.

Данный алгоритм имеет место только для модифицированного кода Хэмминга. В основе лежит деление полинома, соответствующего принятому сообщению на каждый сомножитель полинома g`(x).

Проанализируем синдром:

синдром, r0…rk-1	общая проверка на четность, rk	кратность ошибки	действия
0	0	0	правильная передача
0	1	1	исправление
0	0	2	стирание (n+1 такт)

Частный алгоритм выделяется, т.к. дает возможность выработать сигнал стирания на n+1 такте, т.е. обладает минимальной задержкой при стирании сообщения. На рис.4 приведена обобщенная структурная схема декодера Меггита для модифицированного кода Хэмминга, построенная по частному алгоритму.

Рис.4 Обобщенная структурная схема декодера Меггита

для кода Хэмминга в режиме исправления и

обнаружения ошибок ( частный случай)

Работа. В течении первых n тактов производиться деление принятой кодовой комбинации на g`(x) (формируется синдром в генераторе синдрома), одновременно принятая кодовая комбинация записывается в приемный буферный регистр, а также формируется значение в ячейке памяти D_k ( на элементах m₂ и D_k реализован счетчик по mod 2 – осуществляет общую проверку на четность прямой комбинации).

На n+1-ом такте открывается ключ K₂, если хоть один разряд селектора равен 1 и на D_kноль, то в соответствии с 3-ей строкой таблицы анализа синдрома срабатывает сигнал сброса буферного регистра R_БР, т.е. происходит стирание информации из него и на выход сигнал не поступает. В остальных случаях R_БР не срабатывает. На n+1-ом такте открывается селектор (через ключ K₁) и начинает выталкивать код из буферного регистра. При появлении ошибки селектор вырабатывает истинное значение ошибочного символа с помощью сумматора по mod 2: , т.к. мы внесли коррекцию в вектор, то должны внести в генератор синдрома единицу (осуществляется с помощью обратной связи, на рис.4 обозначена пунктирной стрелкой, направленной влево).

Пример 10

2.Общий алгоритм

В основе общего алгоритма лежит деление полинома, соответствующего принятому сообщению на единый полином g`(x). На рис.5 приведена обобщенная структурная схема декодера Меггита, построенная по общему алгоритму.

рис.5 Обобщенная структурная схема декодера Меггита

в режиме исправления и обнаружения ошибок (общий случай)

Работа. В течении первых n тактов производится деление принятой кодовой комбинации на g(x) (формируется синдром в генераторе синдрома) и одновременно эта кодовая комбинация записывается в приемный регистр. На n +1 такте открывается селектор (через ключ К₁ ) и начинает выталкивать код из буферного регистра. При появлении ошибки селектор вырабатывает истинное значение ошибочного символа с помощью сумматора по mod 2: , т.к. мы внесли коррекцию в вектор, то должны внести в генератор синдрома единицу (осуществляется с помощью обратной связи, на рис.5обозначена пунктирной стрелкой). Если на 2n такте синдром не обнулился, то на 2n+1 такте (через элемент «ИЛИ» и открывшийся ключ К₂) произойдет стирание сообщения.

---

Пример 11

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

Режим обнаружения ошибок не чувствителен к различным реакция (к различным параметрам кода). Обобщенная структура схема декодера Меггита для данного режима приведена на рис.6.

рис.6. Обобщенная структурная схема декодера Меггита

в режиме обнаружения ошибок

Работа. В течении первых n тактов производится деление принятой кодовой комбинации на g(x) (формируется синдром в генераторе синдрома) и одновременно эта кодовая комбинация записывается в приемный регистр. На n+1-ом такте, то сообщение передано безо ошибок (выталкивается из буферного регистра). Если в выработанном синдроме есть хоть одна единица, то через элемент «ИЛИ» она подается на ключ и срабатывает сигнал сброса буферного регистра.

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

1.7 Примеры

Пример 1: представление кодовых комбинаций в виде полиномов.

Пример 2: алгебраические операции по модулю два.

Пример 3: вычисление полинома h(x) по g(x)

Пример 4: расчет параметров БЧХ кодов по m₁,s,r.

Пример 5: расчет параметров БЧХ кодов c нечетным d_min по вероятности.

Пример 6: расчет параметров БЧХ кодов с четными d_min по вероятности.

Пример 7: построение кодера для кода (7,4,3) по полиному h(x).

Пример 8: построение кодера для кода (7,4,3) по полиному g(x).

Пример 9: построение кодера для кода (7,3,4) по полиному g(x).

Пример 10: построение декодера для кода (7,3,4) частный случай.

Пример 11: построение декодера для кода (7,3,4) общий случай.

1.7.1 Пример 1

Кодовой комбинации двоичного кода 100101 соответствует полином вида:

1.7.2 Пример 2

Суммирование по модулю 2 многочленов:

Умножение многочленов:

Деление многочленов:

Деление многочленов в векторной форме:

1.7.3 Пример 3

Пусть циклический код задается порождающим полиномом:

т.е. k=3(см.выше)

Тогда:

и следовательно:

Данному порождающему полиному соответствует циклический код Хэмминга (7,4). Полином имеет вид:

Используя (1), найдем h(x):

Таким образом:

Данному полиному соответствует двоичное число вида 10111. Действия над полиномами можно заменить такими же действиями над соответствующими двоичными последовательностями (для удобства и упрощения записи). Тогда рассмотренный пример деления может быть представлен в виде:

1.7.4 Пример 4

Ищем параметры БЧХ-кода с s=3,r=4,m₁=4.

Найдем минимальное кодовое расстояние:

Сделаем пересчет числа исправляемых ошибок, исходя из условия:

Методом тотального перебора выбираем наименьшие h и , удовлетворяющее условию (4):

не выполняется

не выполняется

не выполняется

не выполняется

выполняется

Выбираем h=5.

Находим длину кода:

Из (4) находим число информационных символов:

Получаем код: (31,16,7).

Вид порождающего полинома, исходя из (5):

,

где m_i(x) выбираем из таблицы неприводимых полиномов:

---

Окончательно g(x):

Переходим к четному минимальному кодовому расстоянию, согласно (6): (31,15,8).

Находим g`(x) по (7):

1.7.5 Пример 5

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

Допустимая вероятность трансформации передаваемого сообщения , вероятность искажения на символ число p=0,0001; информационных символов m₁=19.

Методом тотального перебора найдем такое s, при котором выполниться неравенство:

(*)

Примем s=1 и выберем наименьшее h, пользуясь (4):

не выполняется

не выполняется

не выполняется

не выполняется

выполняется

Выбираем h=5.

Находим длину кода:

где k-число избыточных символов, вычисляется согласно (3).

Тогда:

Вычислим вероятность трансформации, подставив (8) в (9):

У нас s=1, n=24 и p=0,0001, тогда:

Проверяем выполнение неравенства (*):

выполняется,

значит, выбираем s=1, тогда n=24,

Искомый код (24,19,3)

Примечание: если неравенство (*) не выполняется, то увеличиваем число исправляемых ошибок на 1 и повторяем расчет.

1.7.6 Пример 6

Рассчитаем параметры БЧХ-кода, исправляющего s и менее ошибок и обнаруживающего r=s+1 ошибок , в канале с независимыми ошибками. Исходные данные: допустимая вероятность трансформации передаваемого сообщения ; вероятность искажения на символ p=0,0001; информационных символов m₁=19.

Методом тотального перебора найдем такое s, при котором выполняется неравенство:

(*)

Примем s=1 и выберем наименьшее h, используясь (4):

не выполняется

не выполняется

не выполняется

не выполняется

выполняется

Выбираем h=5.

Находим длину кода:

где k-число избыточных символов, вычисляется согласно (3).

Тогда:

Вычислим вероятность трансформации (расчет производится в программе Mathcad), подставив s=1, n=24,k=5 и р=0,0001 в (10):

Проверяем выполнение неравенства (*):

выполняется,

значит, выбираем s=1, тогда n=24,

d_min=s+r+1=1+2+1=4,

Искомый код (24,19,4).

Примечание: если неравенство (*) не выполняется, то увеличиваем число исправляемых и обнаруживаемых ошибок на 1 и повторяем расчет.

1.7.7 Пример 7

Требуется построить кодер по полиному h(x) имеет вид:

h(x)=1+x²+x³+x⁴.

Выберем произвольно m=4 информационных символов:

В нашем случае кодовый вектор, в соответствии с (12), имеет вид:

Информационными являются символы: a₀,a₁,a₂,a₃

Контрольными – a₄,a₅,a₆.

По формуле (11`), найдем:

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

а6 а5 а4 а3 а2 а1 а0

0 1 1 0 0 0 1

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

---

рис.1а. Кодирующий регистр кода (7,4,3) на основе

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

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

(i=– номер такта).

Таблица переходов:

№ такта	Разряд регистра				Выход
	D3	D2	D1	D0
0	0	0	0	1	-
1	1	0	0	0	1	m=4
2	1	1	0	0	0
3	0	1	1	0	0
4	1	0	1	1	0
5	0	1	0	1	1	k=3
6	0	0	1	0	1
7	0	0	0	1	0

Временная диаграмма:

1.7.8 Пример 8

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

Данному полиному соответствует код (7,4), т.е. m=4, k=3.

Пусть:

Тогда:

Найдем r(x):

Итак,

Тогда кодовый вектор:

,

где первые четыре символа – произвольно выбранные информационные символы, а последние три – соответствующие им проверочные символы (счет справа налево).

При реализации данного способа кодирования требуется регистр сдвига с логическими обратными связями, содержащий k=3 ячеек памяти. Необходимое число сумматоров по mod 2 определяется, как количество плюсов в полиноме g(x) (У нас 2).

Вид обратной связи полностью определятся полиномом g(x) =1+x²+x³. (Пояснение: D₃ соответствует x² в полиноме g(x), значит в кодере должен присутствовать сумматор, который ставиться переда данной ячейкой памяти и осуществляет суммирование по mod 2 значения предыдущей памяти на предыдущем такте и обратной связи на данном такте). Структура кодера (кодопреобразователя), приведена на рис.2а, в ней регистр выполняет деление вектора на полином g(x) (построен с помощью обобщенной структурной схемы кодера по полиному g(x). см. рис.2).

рис.2а. Кодирующий регистр кода (7,4) на основе

с предварительным умножением

В таблице переходов приведена последовательность смены состояний регистра (см.рис.2а) с обратными связями (ОС) при подаче на его вход последовательности 0001, начиная с крайней правой единицы.

Таблица переходов:

Состояние ключей	№ такта	Вход	Разряд регистра			Выход
			D1	D2	D3
	0	0	0	0	0	-
	1	1	1	0	1	1	m=4
	2	0	1	1	1	0
	3	0	1	1	0	0
	4	0	0	1	1	0
	5	0	1	0	1	1	k=3
	6	0	0	1	0	1
	7	0	0	0	1	0

Рассмотрим потактно работу схемы.

---

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

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

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

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

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

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