Главная Помехоустойчивое кодирование



Кодовое СЛОВО v

n-точечное ФМС-преобраэование (ФМСП)

3 f

Коррекция

Нахождение

Рекуррентное

полинома

продопжение

локаторов

синдрома S

Сообщение О

Контроль О невозможен (сбои в бпоке ФМСП не выявпяемы)

Кодовое слово v

m-точечное ФМС-преобразование



Нахождение попинома покаторов

о (г)

Рекуррентное продопжение синдрома S

Обратное ФМС-преобразование

Коррекция

Сообщение 0

Кон тропы

S-V -0

Рйс. 6.4. Временная {а), частотная {б) и гибридная (частотно-временная) структуры декодеров 5 = {SS, .. ., 5 ,); С = (С, С,, .. C;t • • •> Q -е - (о> е, . . ., . . .у Efi - \ )jCk -Sq =Ejcy Cjt +1 -Si =Efc +1> - у ~

~Sfri - i ~Efj -i

1); 1 ~

синдрома (ганкелевой матрицы). Недостаток данной структуры -

невозможность косвенного контроля вьщеленного сообщения Q, так

как ошибка в блоке ФМС-преобразования не может быть обнаружена

и исправлена без повторных ФМС-преобразований аналогичными блоками.

Гибридная структура на рис. 6.4, в согласуется с временным кодером. Рекуррентное продолжение характерно для частотного декодирования. Далее осуществляется обратное ФМС-преобразование синдрома 5, удлиненного его продолжением Е, что дает временной вектор е ошибок.



Исследования [10, И, 20, 29] показали, что наиболее перспективна именно смешанная реализация кодека: временной кодер - гибридный декодер; причем для прямого и обратного ФМС-преобразования могут бьггь использованы быстрые алгоритмы.

бЛ. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ КОДОВ РИДА ~ СОЛОМОНА ВО ВРЕМЕННОЙ ОБЛАСТИ

Определение кода Рида - Соломона над конечными полями. Код

Рида-Соломона (РС-код) [8, 11, 15, 22, 36, 40, 43] является циклическим кодом и, следовательно, может быть задан с помощью порождающей или проверочной матриц (как всякий линейный код) либо с помощью порождающего или проверочного полиномов (см. § 1.3). В принципе при кодировании и декодировании РСчсода можно использовать как порождающие, так и проверочные матрицы или полиномы. Мы же здесь для кодирования будем использовать порождающий полином g{z), а для декодирования - проверочную матрицу Н. (Кодирование и декодирование с помощью ФМС-преобразования рассмотрено в § 6.3.)

По определению полином (z) и матрица Н для РС-кода над полем GF ((? = р ) имеют вид;

i = m + и - 1

(z-a), т - п-к; n-q-\\

(6.1)

(1 + 1) (« -1)

v{n - 2)

(i + l) {п-2)

у + 1

(т + у - 1) (и - 1)

(6.2)

где а - примитивный элемент поля GF(q); с? = (m + 1) - минимальное кодовое расстояние; п - длина кода; к - число информационных, am- проверочных символов, причем m - четно; обычно v - или

в матрице Н (6.2) нумерация строк осуществляется сверху вниз с помощью переменной / i+l,.,.,m + j - 1,а столбцов - справа налево с помощью переменной / = 0,1,- 1. При этом также справа налево должны нумероваться и символы кодового вектора. Конечно, нумеровать строки и столбцы матрицы Н (6.2) можно и по-другому, например начиная с / е [ О, l] . Но в любом случае необходимо



следить за тем, чтобы переменные / в соотношениях (6.1) и (6,2) были выбраны одинаково, т. е. показатели степени во втором (справа) столбце у матрицы Н (6.2) совпадали со значениями,пробегаемыми г,в формуле (6.1). В частности, если / = О, то у полинома g{z) появляется сомножитель z - 1, а у матрицы Я - единичная строка.

За счет отбрасьшания ряда информационных символов код может быть сокращен до длины п < - 1, а при добавлении одного или двух проверочных символов - расширен до n+j = q или w+j = + 1. Однако эти варианты кодов далее не рассматриваются.

Если поле GF (q) имеет характеристику 2, т. е. = 2, то знак минус в скобках вьфажения (6.1) заменяется на плюс:

g{z) = (г +a*)(z+a**) ... (2 +а"+-*), GF(20.

Минимальное кодовое расстояние РС-кода определяется точным равенством d = и - /: + 1, т.е, он является МДР-кодом (см. § 1.3) и способен исправлять до Umax - 0,5 m ошибок.

Кодирование РСкодом. Полином U{z) и, следовательно, кодовое

слово и = ("п 1» "п 2> • • "ь "о) РСчсодав несистематической форме находится из соотношения (1.47): U{z) ~Q{z)g(z),TjifiQ{z) - информационный полином. Для того чтобы получить кодовое слово U(z) в систематической форме, достаточно найти остаток R{z) от деления полинома Q{z) Hag(z) и принять

U{z) =Q(z)z-Riz). (6.3)

Пример 6.1. Пусть, например, над полем GF(2*), д: = х + 1, задан рс4с0д с параметрами (и, к) = (15,9). Данный код имеет кодовое расстояние d = п - к + 1 =7, а потому способен исправлять до трех ошибок.

Порождаюнщи полином и находится по формуле при / = 1, 2,..., 6

п - к

i = 6

g(z)= П (z + а) = (z + 2) (z + 3) (z + 4) (z + 5) (z + 6) (z + 7) =

/ = 1

= z + llz + 152 +5z +7z +10z +7; (6.4a)

при / = 0,1,..., 5

/ = 5 .

(z) = П (z + ) = (z + 1) (z + 2) (z + 3) (z + 4) (z + 5) (z + 6) =

/ = 0

= z + lOz + Uz" +2z +3z +5z + 1, (6.46)

где a = 2 - примитивный элемент поля GF(2) и все вычисления проведены по правилам этого поля - см. § 3.3.



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 [80] 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0131