ФОРМИРОВАНИЕ РЕКУРРЕНТНОЙ АЛГОРИТМИЧЕСКОЙ СРЕДЫ КОРРЕКЦИИ МНОГОКРАТНЫХ ИСКАЖЕНИЙ СИСТЕМАТИЧЕСКИХ КОДОВ НА ОСНОВЕ КВАЗИСИНДРОМОВ В ТЕМПЕ АППАРАТНОГО ВРЕМЕНИ

А.В. Ушаков, Е.С. Яицкая

4 АНАЛИЗ И СИНТЕЗ СЛОЖНЫХ СИСТЕМ

УДК [517.938 + 519.713/.718]: 621.398
ФОРМИРОВАНИЕ РЕКУРРЕНТНОЙ АЛГОРИТМИЧЕСКОЙ СРЕДЫ КОРРЕКЦИИ МНОГОКРАТНЫХ ИСКАЖЕНИЙ СИСТЕМАТИЧЕСКИХ КОДОВ НА ОСНОВЕ КВАЗИСИНДРОМОВ В ТЕМПЕ АППАРАТНОГО ВРЕМЕНИ
А.В. Ушаков, Е.С. Яицкая

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

Введение. Постановка задачи. Концепция канального и аппаратного времени

В задачах помехозащитного кодопреобразования встает проблема обмена аппаратного простран-

ства на временные затраты [1]. Эта проблема возникает всякий раз, когда в составе аппаратуры

(hardware) устройств дискретной автоматики есть функциональные компоненты, в которых процесс ко-

допреобразования носит векторный характер, не параметризованный дискретным временем. При этом с

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

ный характер, параметризованный дискретным временем.

При решении поставленной проблемы постулируются следующие положения.

Постулат 1. Помехонезащищенный код (ПНЗК) может поступать на узел помехозащиты в скаляр-

ной параметризованной дискретным временем форме, т.е. в виде последовательного кода старшим раз-

рядом вперед.

□

Постулат 2. ПНЗК может подаваться на узел помехозащиты в векторной не параметризованной

дискретным временем форме, т.е. в виде параллельного кода старшим разрядом вниз.

□

Постулат 3. Двоичный канал связи (канальная среда) (КС) передачи помехозащищенного кода

(ПЗК) от узла помехозащиты к узлу декодирования и коррекции кода при всех реализациях процесса

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

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

□

Постулат 4. Процесс преобразования кода, представленного в форме двоичной кодовой последо-

вательности, характеризуется канальным временем в фазе вывода его в КС и в фазе приема из КС. □

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

средственно не связанной с приемом кода из КС, может быть организован в темпе аппаратного времени,

отличающегося от канального.

□

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

ются: помехозащитное кодирование; преобразование вектора ПЗК, сформированного матричным не па-

раметризованным дискретным временем методом, в последовательный код; помехозащитное декодиро-

вание с целью формирования синдрома ошибок; размещение искаженного ПЗК, принятого из КС, в сдви-

говом регистре хранения, и т.д.

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

ются: преобразование последовательного ПНЗК в параллельный при матричном методе формирования

ПЗК; процесс деления в декодирующем устройстве при повторных циклах деления, и т.д.

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

муникационной аппаратуры (например, телемеханическим протоколом), пропускная способность кото-

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

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

уровня. Аппаратное время, напротив, является модифицируемым. При этом выбором делителей частоты

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

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

ном методе помехозащитного кодирования можно осуществить за один такт канального времени; за один

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

нии.

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

трат при помехозащитном кодировании и декодировании.

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)

37

ФОРМИРОВАНИЕ РЕКУРРЕНТНОЙ АЛГОРИТМИЧЕСКОЙ СРЕДЫ КОРРЕКЦИИ …

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

В работах [2, 3] рассматривается способ коррекции систематических кодов на основе использования квазисиндромов. Процесс систематического помехозащитного преобразования кодов [4–7] представ-
ляется векторно-матричным описанием, параметризованным дискретным временем k , выраженным в
числе тактов длительности t в форме системы соотношений:

xc (k 1)  Axc (k)  Bca(k), k  1, h ; y(k)  La(k) ;

(1)

xc (k 1)  A xc (k), k  1, m ; xc (0)  xc (h) ; y(k)  Cxc (k) ; f (k)  y(k)  ξ(k) ;

xd (k 1)  Axd (k)  Bd f (k), k  1, n ;

(2)

E  xdT (n) ,

где a(k) – (h) -элементная информационная кодовая последовательность (код); y(k) – (n, h) -

элементная последовательность ПЗК; ξ(k) – (n) -элементная последовательность помехи в КС; f (k) –

(n) -элементная последовательность искаженного в КС ПЗК; E – код синдрома искажения (ошибки)

ПЗК; n  h  m – число проверочных разрядов ПЗК; xc , xc – вектор состояния кодирующего устройства

(КУ) до и после коммутации его структуры, размерности dim xc  dim xc  m ; Bc – (m 1) – матрица

входа КУ; L  1 , C  1 O1(m1)  – матрицы выхода КУ; A – нильпотентная матрица с индексом

ν  m ; xd – вектор состояния декодирующего устройства (ДКУ), размерности dim xd  m ; A –

(m  m) -матрица состояния КУ и ДКУ; Bd – (m 1) -матрица входа ДКУ.

Сyт(рkо) ятсfя(kп)роце(дkу)р, а и устройство коррекции, функционирующие в силу соотношения

(3)

где

 

– код (сигнал) коррекции;

y

– код, восстановленный в результате процедуры коррекции. Наличие

сигнала коррекции, параметризованного дискретным временем k, позволяет провести процедуру коррекции кода следующим образом. Синхронно с формированием сигнала коррекции в дополнительном цикле деления необходимо организовать вывод из приемного регистра искаженного ПЗК и суммирование разрядов выводимого ПЗК с сигналом коррекции, чем обеспечивается поразрядная параметризованная дис-
кретным временем коррекция принятого из КС кода f путем суммирования с вектором ошибки  , так

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

Основной результат. Минимизация временных потерь при коррекции многократных искажений в рекуррентной алгоритмической среде на основе квазисиндромов за счет перехода от канального
к аппаратному времени

Основной результат представим в виде алгоритма формирования квазисиндромов как сигналов коррекции ошибок на примере кратности не более 3 в темпе аппаратного времени.
Алгоритм 1. 1. Получить от разработчика КУ:
1.1 параметры помехозащищенного (n, h) – кода, который при кратности s исправляемой ошибки
удовлетворяет требованиям допустимой вероятности ложного приема выбранной категории системы передачи информации; 1.2 матрицу A состояния КУ (1), а также образующий многочлен g(x) кода, гарантирующий ис-
правление ошибок кратности s, для проверки правильности формирования матрицы A из ус-
ловия A  argdet( I  A)  g() .

 2. Выбрать матрицу Bd входа ДКУ (2) из множества матриц вида Al  O1(m1) 1 T для l  0, n 1 .

3. Сформировать конъюнктор вида

38 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)

А.В. Ушаков, Е.С. Яицкая

E0  η0 (k)  &xd (k ) xd (k )Bd ,

(4)

реализующий матрицы-столбцы Bd для получения квазисиндрома E0 однократной ошибки. Если

заданная кратность s исправляемой ошибки удовлетворяет равенству s  1 , то перейти к п. 6 алго-

ритма.

4. Сформировать n 1 конъюнкторов вида

E  η (k )  &xd (k ) xd (k )(AvBd Bd ) ,  1, n 1 ,

(5)

реализующих матрицы-столбцы (A Bd  Bd ) для получения квазисиндромов E двукратных оши-

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

п. 6 алгоритма.

5. Сформировать (n 1)(n  2) 2 конъюнкторов вида

Er,  ηr, (k )  &xd (k) xd (k)(ArBd AvBd Bd ) , r  2, n 1,  1, n  2, r   ,

реализующих матрицу-столбец (ArBd  A Bd  Bd ) для получения квазисиндромов Er, троекрат-

ных ошибок.

6. Модифицировать полученные в вышеизложенных пунктах алгоритма конъюнкторы за счет введе-

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

тем, чтобы сигналы коррекции, сформированные конъюнкторами, не формировались на первом

цикле деления.

7. Сформировать устройство коррекции в виде сумматора (3) выходной кодовой последовательности и

полученных сигналов с конъюнкторов.

8. Проверить на конкретном примере корректирующую способность квазисиндромов ошибок.

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

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

ние сигнала коррекции по длительности не превышали одного такта канального времени.

■

 
Пример 

 
На основе алгоритма 1 построим устройство коррекции, исправляющее ошибки второй кратности

в темпе аппаратного времени.

1. Пусть от разработчика КУ получены следующие данные:

1.1 (n, h)  (15, 7) – формат помехозащищенного кода, обладающий способностью исправлять

ошибки второй кратности; 1.2. образующий многочлен g(x)  x8  x7  x6  x4 1 и матрица A ДКУ (2)

A = col{110 00000, 10100000, 0 0 010000, 10 0 01000, : 00 000100, 0 00 00010, 00 000001, 10 000000}

det(λ I  A)  λ8  λ7  λ6  λ4 1 .

2. Выберем матрицу входа Bd = 00000 0 01 T и построим структурную реализацию ДКУ на паре ма-
риц (A, Bd ) (рис. 1).

xd8 (k 1) xd7 (k 1) xd6 (k 1) xd5 (k 1) xd 4 (k 1) xd3(k 1)

xd 2 (k 1)

xd1(k 1)

f (k)

xd8(k) xd7 (k) xd6(k) xd5(k)

xd4(k) xd3(k)

xd 2 (k )

xd1 (k)

xdT (k) k n  E Рис. 1. Структурная реализация ДКУ: D – D–триггер

 

3–7. Сформируем устройство коррекции в виде сумматора по модулю два, выводимого на втором цикле деления из регистра хранения искаженного кода fr (k) , и сигналов коррекции η0 (k), η (k) , сформированных в форме конъюнкции переменных – элементов вектора состояния ДКУ

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)

39

ФОРМИРОВАНИЕ РЕКУРРЕНТНОЙ АЛГОРИТМИЧЕСКОЙ СРЕДЫ КОРРЕКЦИИ …

 xd1(k), xd 2 (k), xd3 (k), xd 4 (k), xd5 (k), xd 6 (k), xd 7 (k), xd8 (k) и сигнала управления процессом форми-
рования квазисиндрома st (k) согласно (4)–(5). Для краткости записи воспользуемся десятичным
представлением двоичных слов из переменных xi  GF (2)  0,1,i  1, m , параметризованных дис-
кретным временем k, образующих m-мерные конъюнкции. При этом способ представления записи иллюстрируется на примере сигнала η0 (k) η0 (k)  xd1(k)xd 2 (k)xd3 (k)xd 4 (k)xd 5 (k)xd 6 (k)xd 7 (k)xd8 (k)st (k)  (1)2 (k)st (k) ; η1(k)  (3)2 (k)st (k) ; η2 (k)  (5)2 (k)st (k) ; η3 (k)  (9)2 (k)st (k) ; η4 (k)  (17)2 (k)st (k) ; η5 (k)  (33)2 (k)st (k) ; η6 (k)  (65)2 (k)st (k) ; η7 (k)  (129)2 (k)st (k) ; η8 (k)  (208)2 (k)st (k) ; η9 (k)  (114)2 (k)st (k) ; η10 (k)  (231)2 (k)st (k) ; η11(k)  (28)2 (k)st (k) ; η12 (k)  (59)2 (k)st (k) ; η13 (k)  (117)2 (k)st (k) ; η14 (k)  (233)2 (k)st (k) . 8. Проверим полученное устройство коррекции на конкретном примере. Пусть дан помехонезащищенный информационный код, который определяет входную последовательность КУ a(k) :1001011 . В силу полной блоковой систематики формируемого ПЗК информаци-
онную часть кода можно записать в виде y  a| z  1001011y8 y7 y6 y5 y4 y3 y2 y1 .
Вычисление остатка с помощью рекуррентной процедуры (1) сведем в табл. 1
(при BTc  K{xm  g(x)} m8  K{x8  x8  x7  x6  x4 1}  K{x7  x6  x4 1}  11010001 [2]).

k a(k)
xc (k)

0123456 1001011 (0)2 (209)2 (115)2 (230)2 (204)2 (73)2 (67)2

7 0 (87)2

Таблица 1. Проверка функционирования устройства кодирования помехонезащищенного
информационного кода a(k) :1001011

 
Из табл. 1 видно, что на седьмом такте деления в КУ сформировался остаток, который через замкнутый ключ вслед за информационными разрядами будет передан в КС в составе ПЗК, который примет
вид y(k) :10 0101101010111 .

Зададим искажение передаваемого ПЗК в первом и пятом разрядах с помощью помеховой последовательности ξ(k) : 0000000000 10001 . На вход ДКУ из КС поступает искаженная двоичная кодовая

последовательность f (k) :100101101000110 , она же размещается в приемном регистре хранения.

Проведем два цикла деления. Результат первого цикла деления, реализующего процедуру декодирования и получения синдрома, сведем в табл. 2.

  k

01234567

f (k) 1 0 0 1 0 1 1 0

xd (k) st (k)

(0)2 (1)2 (2)2 (4)2 (9)2 (18)2 (37)2 (75)2 00000000

k 8 9 10 11 12 13 14 15

f (k) 1 0 0 0 1 1 0 0

xd (k) st (k)

(150)2 (252)2 (41)2 000

(82)2 (164)2 (152)2 (224)2 (17)2 00000

Таблица 2. Проверка функционирования устройства декодирования искаженной двоичной кодовой
последовательности f (k) :100101101000110
 
Табл. 2 позволяет записать для синдрома ошибки
E  (A j1Bd )T  (Ai1Bd )T i1  (A4Bd )T  (A0Bd )T  00010000  00000001  00010001 , j 5
который является синдромом двукратной ошибки в пятом и первом разрядах. Второй цикл деления реализует процедуру коррекции, результат которой приведен в табл. 3.

40 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)

А.В. Ушаков, Е.С. Яицкая

k 15 16 17 18 19 20 21 22
f (k) 0 0 0 0 0 0 0 0

fr (k) xd (k)
st (k)

0 (17)2
0

1 (34)2
1

0
(68)2
1

0 (136)2
1

1 (193)2
1

0 (83)2
1

1 (166)2
1

1 (157)2
1

η0 (k)  1||;|| η (k)  1,  1,14

–

–

–

–

–

–

–

–

y(k)  fr (k)  η0(k)  14 η (k)

0

1

0

0

1

0

1

1

 1

k 23 24 25 26 27 28 29 30
f (k) 0 0 0 0 0 0 0 0

fr (k)

010 0 0 110

xd (k)  

(235)2 (7)2

(14)2 (28)2 (56)2 (112)2 (224)2 (17)2

st (k)  

1  1  1  1  1  1  1  1 

η0 (k)  1||;|| η (k)  1,  1,14   –  –  –  η 11(k)   –  –  –  η4 (k )  

y(k)  fr (k)  η0(k)  14 η (k)  

0 

1 

0 

1 

0 

1 

1 

1 

 1

Таблица 3. Проверка функционирования устройства коррекции ошибок второй кратности
Код y(k) , восстановленный в результате процедуры коррекции, совпадает с ПЗК y(k) .

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

f (k) fr(k) y(k)

fc
f
Nc fh  n fc
f Nh

xd(k)

&B
&(AB B)

η0(k) η1(k)

η2(k) &(A2B  B)

η3(k) &(A3B  B)

st (k) st (k)

η13(k) &(A13B  B) &(A14B B) η14(k)

 
Рис. 2. Устройство коррекции искажений ошибок первой и второй кратности кода на основе

использования квазисиндромов в темпе аппаратного времени: РХ – регистр хранения с выходным

сигналом fr (k) ; УУ – устройство управления формированием квазисиндрома с выходным сигналом

st (k) ; Т – триггер; G – генератор тактовых импульсов частоты f;

f Nc

– делитель частоты с выходным

сигналом частоты;

fc – частота канального времени;

f Nh

– делитель частоты с выходным сигналом

частоты; fh  n fc – частота аппаратного времени

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)

41

ИССЛЕДОВАНИЕ ФИЗИЧЕСКИХ ПРОЦЕССОВ В ИМПУЛЬСНОЙ КСЕНОНОВОЙ…

Заключение

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

Литература

1. Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной автоматики / Под ред. А.В. Ушакова. – СПб: СПбГУ ИТМО, 2005. – 214 с.
2. Ушаков А.В., Яицкая Е.С. Формирование сигнала коррекции искажений систематических кодов на основе квазисиндрома в алгоритмической среде рекуррентного декодирования в темпе канального времени: случай однократной ошибки // Международный научно-технический журнал «Проблемы управления и информатики» (на рассмотрении).
3. Ушаков А.В., Яицкая Е.С. Формирование сигналов коррекции искажений систематических кодов на основе квазисиндромов в алгоритмической среде рекуррентного декодирования в темпе канального времени: случай многократных ошибок // Международный научно-технический журнал «Проблемы управления и информатики» (на рассмотрении).
4. Ушаков А.В., Яицкая Е.С. Анализ структуры пространства состояний линейных двоичных динамических систем на основе их рекуррентного модельного представления // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 4 (74). – С. 43–49.
5. Гилл А. Линейные последовательностные машины. – М.: Наука, 1974. – 288 с. 6. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 1976. – 600 с. 7. Rosenthal J. Some interesting problems in systems theory which are of fundamental importance in coding
theory // Proc. 36 Conf. Decision Control. – San Diego, CA, 1997. – V. 5. – P. 4574–4579.

Ушаков Анатолий Владимирович Яицкая Елена Сергеевна

– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, ushakov-AVG@yandex.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, yaitskayaes@mail.ru

42 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)