Королёв А.И. Коды и устройства помехоустойчивого кодирования

Подождите немного. Документ загружается.

увеличивается количество строк в новой матрице (процедура выполнения пред-

ставлена на схеме рис.4.1).

4.2.5. Общий принцип построения кодов с использованием процедуры

“пополнение кода”

С использованием данной процедуры новый код формируется (строится)

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

изменения длины кодовых последовательностей исходного кода путем умень-

шения количества проверочных символов и, следовательно, уменьшения мини-

мального кодового расстояния.

При использовании проверочной матрицы исходного кода для построения

нового кода при использовании процедуры “пополнения кода”, необходимо

уменьшить количество столбцов проверочной части этой матрицы и соответст-

венно уменьшить количество строк этой матрицы, но при этом увеличивается

количество столбцов информационной части (процедура пополнения кода ил-

люстрируется схемой рис.4.1); такая процедура формирования кода сохраняет

постоянной длину кодовой последовательности, но уменьшает d

Таким образом, можно отметить следующее: ЦК сформированный обра-

зующим полиномом P(x), может быть пополнен до кода той же длины, обра-

зующий полином которого является некоторым множителем P(x). Если, напри-

мер, P(x) содержит сомножитель (x-1), то пополненный код будет формиро-

ваться (порождаться) полиномом P(x)/(x-1); при выполнении операции деления

знак вычитания “-” заменяется знаком сложения “+”.

4.2.6. Общий принцип построения кодов с использованием процедуры

“удлинение кодов”

Новый помехоустойчивый код может быть получен из исходного (n,k) –

кода путем добавления дополнительных информационных символов, что при-

водит одновременно к увеличению количества строк и столбцов порождающей

α =⊕⊕⊕⊕ K

матрицы исходного кода, а в проверочной матрице это приводит к увеличению

количества строк матрицы и количества столбцов информационной части (ин-

формационные подматрицы); это будет обеспечивать то, что минимальное ко-

довое расстояние нового кода будет равно минимальному кодовому расстоя-

нию исходного кода (смотри схему рис.4.1).

Если данную процедуру рассматривать применительно к ЦК, для которого

P(x) делится на (x-1), то удлинение этого кода проводится в два этапа, т.е. как

при расширении кода. Первоначально следует пополнить до кода, порожденно-

го как P(x)/(x-1), что соответствует добавлению к коду кодовой последователь-

ности состоящей целиком из единиц (верхняя строка проверочной матрицы

4,8

(x) схемы рис.4.1). Далее полученный код расширить, добавив общую про-

верку на четность, т.е. В большинстве случаев такая

процедура формирования нового кода может быть выполнена с сохранением

величены d

исходного кода.

Контрольные вопросы и задачи

1. Назначение и классификация простых преобразований групповых

линейных блоковых кодов.

2. По заданной преподавателем порождающей матрице и шагу укорачива-

ния кода “L” построить укороченный код. Определить основные свойства дан-

ных кодов.

3. Используя заданную преподавателем проверочную матрицу и шаг

укорачивания кода “L” построить укороченный код. Определить параметры

кода.

4. Сущность процедуры (принципа) “расширения кода”. Привести пример

на построение расширенного кода.

5. Сущность принципа построения кода с использованием процедуры

“выкалывания кодовых координат”. Привести пример на построение кода.

6. Построить новый код с использованием процедуры “удлинения кода”,

если исходный код имеет параметры (n,k,d

)=(10,5,4). Определить параметры

нового кода и указать его основные свойства.

7. Для исходных данных пункта 6 построить новый код с использованием

процедуры “пополнения кода”. Определить параметры нового кода .

8. Построить новый код с использованием процедуры “выбрасывания ко-

довых последовательностей”, если исходный код имеет следующие параметры:

(n,k,d

)=(7,3,4) и P(x)=x

+x+1. Определить параметры полученного кода.

5. ОБЩИЕ ПРИНЦИПЫ ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ

КОДЕКОВ ГРУППОВЫХ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ

5.1. Общие требования, предъявленные к реализации кодеков помехо-

устойчивых кодов

Аппаратурная реализация кодеков помехоустойчивых кодов обеспечивает

высокую скорость обработки (декодирования) информации и, следовательно,

данный способ реализации кодеков помехоустойчивых кодов наиболее целесооб-

разно использовать в современных высокоскоростных (В>100 Мбит/с) системах

связи. С целью минимизации габаритов, веса и объема оборудования кодеков

принципиальные электрические схемы кодеков выполняются с использованием

современных цифровых интегральных микросхем (ИМС).

Выбор элементной базы, т.е. конкретной серии и типа ИМС, для разработки

принципиальных электрических схем кодеков производится по следующим пра-

вилам[8]:

– верхняя граничная частота (частота переключения) ИМС должна быть в два-

три раза больше максимальной тактовой частоты проектируемого кодека. Данный

частотный “запас” обеспечит надежную работу кодека;

– минимальное потребление кодеком электроэнергии;

– большой набор функциональных элементов в выбираемой серии ИМС;

– большая (высокая) степень интеграции микросхем, т.е. использование для

проектирования и реализации кодеков БИС, СБИС, проектируемых логических

матриц (ПЛМ) и т.д. выполнение данного правила обеспечивает минимальный

объем оборудования кодеков;

– минимальная стоимость ИМС и др.

При разработке принципиальных электрических схем функциональных

блоков кодека необходимо соблюдать выполнение следующих требований [2,8]:

– простота схемотехнических решений;

– оригинальность схемотехнических решений (патентная чистота данных ре-

шений);

– минимальный объем оборудования кодека;

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

персоналу, обслуживающему данные устройства связи;

– наличие встроенных автоматизированных систем технического контроля и

диагностики кодека.

Выполнение вышеперечисленных правил-требований обеспечит разработ-

чику систем связи технически грамотное проектирование кодеков помехоустой-

чивых кодов. Далее рассматриваются общие принципы проектирования (разра-

ботки) кодеков двоичных групповых линейных блоковых кодов, имеющих широ-

кое практическое применение в современных цифровых системах связи. К таким

кодам относятся следующие циклические коды (ЦК): Хэмминга, Рида-Соломона,

БЧХ-коды, Файра и др. Проектирование кодеков помехоустойчивых кодов может

производится по разным методикам. Рассмотрим проектирование кодеков важ-

нейших ЦК по следующей методике:

1) приводятся краткие теоретические сведения о коде;

2) рассматриваются конкретные параметры кода;

3) разрабатываются алгоритмы кодирования и декодирования кодов;

4) разрабатываются структурные и функциональные схемы, а принципи-

альные схемы разрабатываются для коротких кодов с кратким описанием прин-

ципов их работы.

Кроме того, с целью минимизации сложности проектирования рассматри-

ваются коды с малой длиной кодового ограничения (n<100 двоичных символов) и

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

либо синдромный алгоритмы декодирования.

5.2. Синтез кодеков циклических кодов Хэмминга

В соответствии с [1,3,6,7] параметры кодов Хэмминга определяются равен-

ством: n=2

-1 двоичных символов, k=2

-1-l двоичных символов, l–количество про-

верочных символов. В общем виде код Хэмминга может быть записан так:

(n,k)=(2

-1-l).

Из двоичных циклических кодов Хэмминга наибольшее применение полу-

чим следующие коды: (n,k,d

)=(7,4,3), (n,k,d

)=(7,3,4), (n,k,d

)=(15,11,4),

(n,k,d

)=(31,26,5) и др. Коды Хэмминга, исправляющие одиночные ошибки (t

исп

двоичный символ или разряд), имеют d

=3, а коды, исправляющие одиночные

ошибки и обнаруживающие двухкратные ошибки, имеют d

=4; для некоторых ли-

нейных кодов Хэмминга с d

=4 возможно только обнаружение двухкратных оши-

бок, т.е. без коррекции одиночных ошибок. Для циклических кодов Хэмминга с

=3 и d

=4 для реализации их корректирующей способности необходимо иметь

l=d

проверочных символов.

Циклические коды Хэмминга могут быть построены с использованием как

порождающей G

k,n

(x), так и проверочной H

l,n

(x) матриц. Характерной особенно-

стью проверочных матриц кодов Хэмминга с d

=3 и d

=4 является то, что столбцы

матриц представляют собой различные ненулевые комбинации (последовательно-

сти или кодовые слова) содержащие l двоичных символов (разрядов). Провероч-

ные матрицы кодов Хэмминга обладают следующими свойствами:

1) ненулевые символы строк H

l,n

(x) определяют позиции информационных

символов, участвующие в формировании проверочных символов;

2) число логических “1” в каждом столбце H

l,n

(x), т.е. вес столбца

столбца

), должно быть больше или равно d

-1;

3) при перестановке столбцов H

l,n

(x) корректирующие свойства кода не ме-

няются: код имеет минимальный вес (w

) не менее d

, т.е. w

≥d

, тогда и только

тогда, когда каждое множество из (w

-1) столбцов матрицы H

l,n

(x) линейно неза-

висимы;

4) сумма по модулю два любых двух столбцов матрицы H

l,n

(x), соответст-

вующие информационным символам, должны давать вес (w

) не менее d

-1, т.е.

≥ d

-1;

5) при сложении строк матрицы H

l,n

(x) и при умножении строк матрицы

l,n

(x) на ненулевые элементы, корректирующие свойства кода не меняются.

Циклические коды Хэмминга могут быть декодированы с использованием

как мажоритарного, так и синдромного алгоритмов декодирования. В свою оче-

редь мажоритарный алгоритм декодирования может быть реализован с формиро-

ванием системы как раздельных ортогональных (согласованных) проверок (орто-

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

проверок. Далее рассмотрим сущность данных алгоритмов декодирования и вы-

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

пользовании коротких кодов Хэмминга, а именно кодов с параметрами

(n,k,d

)=(7,4,3) и (n,k,d

)=(7,3,4).

5.2.1. Синтез кодека циклического кода с формированием системы раз-

дельных проверок

Название алгоритма мажоритарного декодирования вытекает из самой сущ-

ности реализации алгоритма декодирования, а точнее от способа принятия реше-

ния о полярности (знаке) декодируемого информационного символа. При мажо-

ритарном алгоритме декодирования решение о полярности декодируемого ин-

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

решения проверочных уравнений (проверок); реализуется принцип “голосова-

ния”. Это означает, что если более 50% результатов решения проверочных урав-

нений имеют значения логической “1” или логического “0”, то декодер формиру-

ет соответственно информационные символы равные “1” или “0”. При равном ко-

личестве результатов решения проверочных уравнений условно принято, что де-

кодер формирует нулевой информационный символ, т.е. решение принимается в

пользу”0”.

В разделе 2 отмечалось следующее свойство систематических линейных ко-

дов: если принятую кодовую последовательность F'(x) на транспонированную

проверочную матрицу кода H

l,n

(x), то можно получить следующие два результа-

та:

F'(x)·H

l,n

(x)=0,

F'(x)·H

l,n

(x)≠0. (5.1)

Результат решения первого уравнения означает, что в принятой кодовой по-

следовательности ошибок нет или ошибки не обнаруживаются кодом. Результат

решения второго уравнения противоположен первому.

Так как любой ЦК имеет l проверочных символов, то можно составить 2

проверочных уравнений вида (5.1). В общем виде проверочное уравнение для не-

которой j-ой строки транспонированной проверочной матрицы H

l,n

(x) можно за-

писать так:

∑

−

=∗

ij,i

0)x(F)x(H

Используя же свойство цикличности кода, то можно построить и все 2

про-

верочных уравнений, что можно записать так [3,4,6,7]:

Главной задачей алгоритма мажоритарного декодирования является выбор

или составление “хорошего” или “оптимального” (в плане обеспечения макси-

мальной корректирующей способности кода) подмножества проверочных уравне-

ний; при условии, если оно существует.

Наиболее “просто” составляются проверочные уравнения в основе которых

лежит следующая идея: если декодируемый информационный символ входит во

все проверочные уравнения, а остальные символы, входящие в эти проверочные

уравнения, входят только по одному разу. Данную идею можно записать в виде

следующей системы проверочных уравнений относительно некоторого информа-

ционного символа, например, а

.0(x)F(x)H

1nji,

∑

−

=∗

,0(x)F(x)H

1nji,

∑

−

=∗

(5.2)

Записанная система проверочных уравнений носит название “системы раз-

дельных проверочных уравнений (проверок)” – СРП. Исходя из вышеизложенно-

го следует: если множество µ (µ ≥ 2) проверочных уравнений (n,k)-кода ортого-

нальны относительно некоторого символа и данный символ входит во все прове-

рочные уравнения, а все остальные символы, входящие в эти проверочные урав-

нения, входят только в одно проверочное уравнение, то к данному (n,k)-коду воз-

можно применение алгоритма мажоритарного декодирования и при этом будет

гарантировано обеспечиваться коррекция ошибок кратностью t

исп

≤ µ /2 двоичных

символов.

Таким образом, при требуемой или заданной корректирующей способности

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

включает выполнение следующих операций (процедур):

1) определение минимально необходимого количества ортогональных про-

верочных уравнений, используя равенство µ=2* t

исп

+1; последний член данного

равенства характеризует, так называемое, тривиальное уравнение относительно

декодируемого информационного символа, например, a

=a'

;

2) построение проверочной матрицы H(x) либо в канонической форме, либо

в транспонированной форме;

3) формирование по построенной проверочной матрице системы раздель-

ных проверок;

4) разработка структурных, функциональных и принципиальных электри-

ческих схем кодека;

5) проверка коррекции кодеком ошибок заданной кратности.

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

Хэмминга, реализующего алгоритм мажоритарного декодирования при следую-

щих параметрах кода: (n,k,d

)=(7,3,4), P(х)=x

+1.

.... CGNFa

⊕⊕⊕⊕=

,... ξγ ⊕⊕⊕⊕= mka

(5.3)

1. Построим проверочную матрицу в канонической форме для чего нахо-

дим проверочный полином по формуле

h(x)=(x

+1)/P(x)=(x

+1)/(x

+1)=x

+1=1101.

2. Строим проверочную матрицу H

l,n

(x)= H

4,7

(x) по следующему правилу:

первый столбец матрицы записываем с использованием проверочного полинома,

представленного в двоичной форме и дополним его снизу нулевыми символами

до n=7, второй, третий и четвертый столбцы записываем путем последовательного

циклического сдвига вниз двоичных символов первого столбца. Построенная про-

верочная матрица будет иметь следующий вид:













1000

0100

1010

1101

0110

0011

0001

)(

7,4

. (5.4)

3. Определяем необходимое количество ортогональных проверочных

уравнений, исходя из корректирующей способности кода, а именно

исп

≤(d

-1)/2=(3-1)/2=1 двоичный символ. Так как код корректирует одиночные

ошибки, то достаточно сформировать µ=2·t

исп

+l=2·1+1=3 проверочных уравнения

и дополнительно ввести тривиальное проверочное уравнение. Таким образом, не-

обходимо сформировать четыре проверочных уравнения; µ'=µ+1.

4. Определяем необходимое количество раздельных проверочных подмат-

риц, используя следующее равенство N=µ'-1=4-1=3.

5. Строим подматрицы раздельных проверок, которые обозначим как

1.1

(x), q

2.1

(x), q

3.1

(x). Первые (левые) столбцы данных подматриц записываются

соответственно с использованием трех столбцов проверочной матрицы (5.4). Вто-

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

на один такт двоичных символов первых столбцов. Двоичные символы третьих

столбцов данных подматриц формируются следующим образом: