ФОРМИРОВАНИЕ РЕКУРРЕНТНОЙ АЛГОРИТМИЧЕСКОЙ СРЕДЫ КОРРЕКЦИИ МНОГОКРАТНЫХ ИСКАЖЕНИЙ СИСТЕМАТИЧЕСКИХ КОДОВ НА ОСНОВЕ КВАЗИСИНДРОМОВ В ТЕМПЕ АППАРАТНОГО ВРЕМЕНИ
А.В. Ушаков, Е.С. Яицкая
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)
xc (k 1) A xc (k), k 1, m ; xc (0) xc (h) ; y(k) Cxc (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 , xc – вектор состояния кодирующего устройства
(КУ) до и после коммутации его структуры, размерности dim xc dim xc m ; Bc – (m 1) – матрица
входа КУ; L 1 , C 1 O1(m1) – матрицы выхода КУ; 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 argdet( I A) g() .
2. Выбрать матрицу Bd входа ДКУ (2) из множества матриц вида Al O1(m1) 1 T для l 0, n 1 .
3. Сформировать конъюнктор вида
38 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
А.В. Ушаков, Е.С. Яицкая
E0 η0 (k) &xd (k ) xd (k )Bd ,
(4)
реализующий матрицы-столбцы Bd для получения квазисиндрома E0 однократной ошибки. Если
заданная кратность 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 конъюнкторов вида
Er, ηr, (k ) &xd (k) xd (k)(ArBd AvBd Bd ) , r 2, n 1, 1, n 2, r ,
реализующих матрицу-столбец (ArBd A Bd Bd ) для получения квазисиндромов Er, троекрат-
ных ошибок.
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)} m8 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 j1Bd )T (Ai1Bd )T i1 (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)
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)
xc (k 1) A xc (k), k 1, m ; xc (0) xc (h) ; y(k) Cxc (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 , xc – вектор состояния кодирующего устройства
(КУ) до и после коммутации его структуры, размерности dim xc dim xc m ; Bc – (m 1) – матрица
входа КУ; L 1 , C 1 O1(m1) – матрицы выхода КУ; 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 argdet( I A) g() .
2. Выбрать матрицу Bd входа ДКУ (2) из множества матриц вида Al O1(m1) 1 T для l 0, n 1 .
3. Сформировать конъюнктор вида
38 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
А.В. Ушаков, Е.С. Яицкая
E0 η0 (k) &xd (k ) xd (k )Bd ,
(4)
реализующий матрицы-столбцы Bd для получения квазисиндрома E0 однократной ошибки. Если
заданная кратность 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 конъюнкторов вида
Er, ηr, (k ) &xd (k) xd (k)(ArBd AvBd Bd ) , r 2, n 1, 1, n 2, r ,
реализующих матрицу-столбец (ArBd A Bd Bd ) для получения квазисиндромов Er, троекрат-
ных ошибок.
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)} m8 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 j1Bd )T (Ai1Bd )T i1 (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)