vopros-otvet (519806), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Вектор двойных ошибок можно записать:

,

где λ = i – j > 0, а i > j.

Для того, чтобы обнаруживать двойные ошибки, необходимо, чтобы при делении e_i+j(x) на g(x) мы имели остаток.

Но это условие всегда выполняется, если в качестве g(x) взять многочлен, предназначенный для исправления одиночных ошибок, так как он не кратен X ^j и не входит в разложение (x^λ Е 1), если λ < n.

Это тем более объяснимо, что для обнаружения двойных ошибок (R = 2), необходимо, чтобы минимальная дистанция между Р.К.К. была d ≥ R + 1 = 2 + 1 = 3, что соответствует исправлению одиночной ошибки d ≥ 2S + 1 = 2 · 1 + 1 = 3.

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

36.Методы построения циклического кода.

6.4.1. Методом умножения

Информационный многочлен a_i(x) умножается на образующий многочлен g(x), то есть .

Достоинство метода – простота реализации при кодировании.

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

Пусть имеем код (7; 4), то есть код исправляющий одиночные ошибки. Пусть g(x) = x³ Е x Е 1. Необходимо передать a_i(x) = 1011.

Для получения Р.К.К. – ƒ_i(x) умножим и получим:

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

На приемной стороне, чтобы судить есть ошибка или нет, необходимо принятую кодовую комбинацию (К.К.) поделить на g(x). Если ошибок нет, то остаток от деления r(x) должен быть равен нулю. Делим:

Получили остаток, отличный от нуля. По нему мы должны определить, в каком разряде имеет место ошибка. Для этого необходимо определить, какой остаток r_i(x) даст единичная ошибка в i-том разряде.

До ошибки в четвертом разряде остаток соответствует самой ошибке, а начиная с ошибки в 4-ом разряде происходит деление. В примере остаток , то есть ошибка в пятом разряде. Исправим ошибку:

Но, получив ƒ_i(x), мы не получили a_i(x), то есть снова приходится делить ƒ_i(x) на g(x), то есть

6.4.2. Методом деления

Чтобы получить разделимый код поступают следующим образом: a_i(x) умножают на x^m, что эквивалентно дописыванию к a_i(x) справа m нулей. Полученный многочлен делится на g(x). В результате получается частное от деления g(x) и остаток r(x).

Разрешенная кодовая комбинация ƒ_i(x) получается путем сложения и r(x), то есть

.

Степень многочлена g(x) – m, а степень остатка – (m – 1). Поэтому сложение эквивалентно приписыванию остатка r(x) к a_i(x), так как m разрядов в – нулевые. В то же время ƒ_i(x) делится на g(x) без остатка, так как

Данная методика используется при k > m.

Рассмотрим тот же пример:

a_i(x) = 1011; g(x) = 1011.

.

Так получилось потому, что a_i(x) совпало с g(x).

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

.

Поделим на g(x) и получим остаток r(x):

Исправим принятую К.К.:

И сразу получаем a_i(x) как первые k символов, то есть 1011.

6.4.3. По методу группового кода

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

,

где

,

а n = 2^m – 1.

Зная значения информационных разрядов a₀ (старший разряд); a₁; a₂;... a_k–1 можно получить значения проверочных разрядов a_k; a_k+1;... a_n–1. Получается код, полностью совпадающий с кодом, полученным делением.

Метод применяется при m > k и k = n – m, если n = 2^m – 1.

Рассмотрим пример.

Циклический код, исправляющий одиночные ошибки (7; 4); g(x) = 1101.

Найдем Р.К.К. для a_i(x) = 0110.

1. Найдем функцию h(x).

Для этого поделим (xⁿ Е 1) на g(x), то есть (x⁷ Е 1) / g(x):

1. Определим проверочные символы Р.К.К., то есть a₄; a₅; a₆.

Используя формулу

,

найдем:

,

где (i = 0);

,

где (i = 1);

,

где (i = 2).

В итоге имеем Р.К.К.: 0110100.

По методу деления мы имеем ту же кодовую комбинацию: делим на g(x) и получаем r(x) = 100.

тогда Р.К.К. равна 0110100.

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

В 6.4.1 нами был рассмотрен пример получения Р.К.К. методом умножения. Покажем, как это можно реализовать технически на том же примере:

.

Нарисуем схему умножения образующего многочлена g(x) на любой многочлен a_i(x).

Рис. 6.1. Получение разрешенной кодовой комбинации по методу умножения

В схеме умножения имеется m ячеек памяти в соответствии со степенью многочлена g(x).

Ячейка x⁰ не нужна, а потому показана пунктиром. Входной сигнал подается в ячейки памяти слева, начиная со старших разрядов. Входной сигнал по тактам продвигается по ячейкам памяти в соответствии с частотой генератора тактовых импульсов (ГТИ). За один такт продвигается вправо содержание всех ячеек памяти одновременно. На выходной сумматор по модулю два поступают синхронно те нули и единицы, которые идут в соответствующие ячейки памяти. В нашем случае это x³; x¹ и x⁰, то есть ячейки, соответствующие наличию единицы в записи g(x) = 1011 = x³ Е x Е 1. Сигнал, поступающий в ячейку x², на сумматор не идет.

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

Рис. 6.2

Таблица 6.2

№/№ тактов	Вход	Ячейки			Выход		Примечание
		x3	x2	x1
0	0	0	0	0		0		начальное состояние
1	1	1	0	0		1		потактовое передвижение информации в схеме умножения
2	0	0	1	0		0
3	1	1	0	1		0
4	1	1	1	0		0
5	0	0	1	1		1
6	0	0	0	1		0
7	0	0	0	0		1
8	0	0	0	0		0		начальное состояние

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

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

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

Снова рассмотрим все на примере.

Пусть a_i(x) = 1001 = x³ Е 1; g(x) = 1101 = x³ Е x² Е 1.

Получим Р.К.К._i путем

Схема деления строится следующим образом:

• сначала необходимо набрать m разрядов из делимого a_i(x), начиная с первой единицы;

• из полученного m-разрядного числа вычитаем g(x); в нашем случае это равносильно сложению по модулю два в тех старших разрядах, в которых стоят единицы за исключением старшего разряда x³, так как у него в результате сложения всегда получаем ноль;

• делитель строим начиная с младшего разряда, то есть x⁰.

Рис. 6.3

Характеристики

Список файлов ответов (шпаргалок)