4.7.2. Описание алгоритма при исправлении  ошибок

Вновь рассмотрим код БЧХ с порождающим полиномом g(x)=7218 и значением   для нумерации кластера. Код имеет порождающую матрицу  в систематической форме, представленную выражением (4.7). Пусть на выходе кодера образовался вектор вида:

.

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

.

Приемник принимает вектор, устанавливая по какому-либо известному принципу градацию надежности для каждого символа комбинации. Пусть соответствие символов и градаций надежности символов (ИДС) имеет вид        

=	1	1	0	0	0	1	1	0	0	0	0	1	0	0	1
ИДС	6	2	7	7	1	1	1	7	7	7	7	7	5	5	7,

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

=

0

1

0

0

1

1

1

0

0

0

0

0

1

1

0.

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

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

1

0

0

0

0

1

1

0

0

0

0

1

0

0

1.

Номер восстановленного кластера получил значение 410. После этого шага декодер переходит на укороченный код (12,4,5), порождающая матрица которого имеет вид (4.8). Далее формируется корректирующий вектор  путем умножения номера кластера на первые три строки порождающей матрицы  G .

=

1

0

0

0

0

0

0

1

1

1

0

1

0

0

0

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

=

0

0

0

0

1

1

1

0

1

0

0

0.

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

Табл. 4.21 Формирование вектора укороченного кода

	0	0	1	1	0	0	0	0	1	0	0	1
	0	0	0	0	1	1	1	0	1	0	0	0
	0	0	1	1	1	1	1	0	0	0	0	1
ИДС	7	1	1	1	7	7	7	7	7	5	5	«0»

 

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

Табл. 4.22 Преобразование вектора укороченного кода по основному алгоритму

Порядковая нумерация	1	2	3	4	5	6	7	8	9	10	11	12
	0	0	1	1	1	1	1	0	0	0	0	1
Оценки	7	1	1	1	7	7	7	7	7	5	5	«0»
Новая нумерация символов	1	5	6	7	8	9	10	11	2	3	4	12
Значения переставленных символов	0	1	1	1	0	0	0	0	0	1	1	1

 

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

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

Условие    выполняется, следовательно, на основании   определяется порождающая матрица эквивалентного  кода в систематической форме.

.

Умножая вектор  0111, выделенный в таблице,  на новую порождающую матрицу декодер получает вектор эквивалентного кода 

 

Vэкв =

0

1

1

1

0

0

1

1

1

0

0

0.

 

 

Последующие преобразования по выделению условного вектора ошибок представлены в табл. 4.23, 4.24 и 4.25.

 

Табл. 4.23 Преобразование вектора укороченного кода по основному алгоритму

Комбинация эквивалентного кода Vэкв	0	1	1	1	0	0	1	1	1	0	0	0
Значения переставленных символов	0	1	1	1	0	0	0	0	0	1	1	1
Условный вектор ошибок	0	0	0	0	0	0	1	1	1	1	1	1

 

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

Табл. 4.24 Преобразование вектора укороченного кода по основному алгоритму

Комбинация укороченного кода Vук	0	0	1	1	1	1	1	0	0	0	0	1
	0	0	0	0	1	1	1	0	1	0	0	0
Вектор ошибок	0	1	1	1	0	0	0	0	0	1	1	0
Результат сложения	0	1	0	0	0	0	0	0	1	1	1	1

 

Табл. 4.25 Преобразование вектора кода по основному алгоритму

Комбинация укороченного кода Vук	Позиции разрядов кластера			0	1	0	0	0	0	0	0	1	1	1	1
Комбинация с номером кластера	1	0	0	0	1	0	0	0	0	0	0	1	1	1	1
Вектор принятый из канала связи	1	0	0	0	1	0	0	0	0	0	0	1	1	1	1

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

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