Книги по разным темам Pages:     | 1 |   ...   | 6 | 7 | 8 | 9 | 10 |   ...   | 24 |

Доказательство утверждения в первой части состоит в непосредственной подстановке матриц G и H вида (1.158) в (1.147), которая приводит к ~ ~ ~ ~ GH =[Ik G] G = G + G = O.

Im Доказательство второй части утверждения строится на подстановке матрицы G вида (1.158) в (1.144) ~ ~ (1.160) y = aG = a[I G]= [a aG], что обнаруживает полную блоковую систематику ПЗК y.

Алгоритмы формирования матриц G и H ПЗК различаются последовательностью этой процедуры. Сначала рассмотрим процедуры формирования матриц помехозащищенного кода, в которых сперва конструируется проверочная матрица H, а затем на основе сформулированных утверждений вычисляется образующая матрица G ПЗК.

Вторую группу алгоритмов составляют процедуры, в которые на первом этапе формируется матрица G кода, а затем формируется проверочная матрица H ПЗК.

1.6.1 Формирование матриц ПЗК с помощью проверочных равенств при декодировании и кодировании Процедура формирования матриц H и G ПЗК, основанная на использовании проверочных равенств при декодировании и кодировании, инвариантна относительно требований к блоковой систематике кода.

По существу уровень блоковой систематики в структуре проверочной матрицы H кода закладывается в силу (1.146) и У1.31 на первом шаге процедуры, состоящем в кодировке векторов-строк ошибок вектоj рами-строками синдромов E. Следует заметить, что на этапе кодироj вок ошибок синдромами E может быть так же заложен [42, 51] j j способ технической реализации исправления ошибки(ок) в принятой кодовой комбинации. Так кодировкой ошибок синдромами E по j j схеме Р. Хэмминга [42, 51] закладывается возможность технической реализации исправления однократных ошибок с использованием стандартных дешифраторов [27, 51].

Алгоритм 1.6 (А1.6) формирования матриц ПЗК с помощью проверочных равенств при кодировании и декодировании 14. Составить таблицу кодировок векторов-строк однократных ошибок векторами-строками синдромов E, начиная с ошибj j ки в старшем разряде n = [1 On-1] и заканчивая ошибкой в младшем разряде 1 = [On-1 1], где On-1 - (n - 1)-мерная нулевая вектор-строка, так, что E удовлетворяют условиям У1.31 и j принятым техническим соображениям относительно процедуры коррекции искаженного кода.

15. Сформировать проверочную матрицу H на основании составленной таблицы кодировок и соотношения (1.151), которая построчно должна удовлетворять условию j H = En+1- j ; j = 1,n. (1.161) 16. На основании составленной проверочной матрицы H кода и соотношения (1.146), описывающего процесс формирования синдрома в аппаратурной среде ДКУ, составить аналитические выражения для каждого разряда E,= m, 1 синдрома как функции принятой из КС искаженной кодовой комбинации f = row{fn+1- j ; j =1,n} в силу соотношения E = f Hm+1-,=1,m, (1.162) где Hm+1- - (m + 1 - )-ый столбец матрицы H.

17. Сформировать аналитические выражения для помехозащитного кодирования помехонезащищенного кода a = row{ai,i = k,1}, для чего записать соотношения (1.162) в предположении, что в КС отсутствует помеха ( = 0 ), положив, тем самым, справедливость выполнения условий E = 0, fn+1- j = yn+1- j, j =1,n, (1.163) порождающих систему равенств 0 = y Hm+1- = yn+1- j,=1,m, (1.164) допускающих явное разрешение относительно разрядов y ПЗК j как функций разрядов ai помехонезащищенного кода в форме y = y (ai, i =1,k ), j =1,n. (1.165) j j 18. Сформировать образующую матрицу G = row{G, j = 1,n} кода j на основании соотношения (1.144) в силу условия G = arg{y = aG = y (ai, i =1,k ); j =1,n}, (1.166) j j j j в котором известны вектор-строка помехонезащищенного кода a, а также линейная связь y и ai в форме (1.165).

j 1.6.2 Формирование матриц ПЗК с использованием матричного уравнения Сильвестра На возможность использования матричного уравнения Сильвестра для формирования проверочной матрицы циклического помехозащищенного кода (ЦПЗК) указано в параграфе 1.4. Эти возможности в систематизированном виде являются основой алгоритма 1.7 формирования указанной матрицы ЦПЗК.

Алгоритм 1.7 (А1.7) формирования проверочной матрицы ЦПЗК на основе использования матричного уравнения Сильвестра 1. Сформировать k -разрядный ПНЗК на основе мощности [Q]= Nи заданного массива Q передаваемой или хранимой информации так, что k = arg{2k Nи = [Q]} (1.167) 2. Сформировать число m проверочных разрядов, удовлетворяющих требованием к достоверности передачи или хранения информации и к способу реализации корректирующей способности синтезируемого ПЗК.

3. Выбрать неприводимый модулярный многочлен g() степени deg g()= m, удовлетворяющий всем требованиям к корректирующей способности кода [28, 42, 51].

4. Задать m m-матрицу в произвольном базисе (1.168) = arg{det(I + ) = g()}, так, чтобы она обладала характеристическим полиномом g().

5. Выбрать матрицу L размерности m 1, образующую с матрицей полностью управляемую пару (,L).

6. Задать матрицу A размерности n n, где n = k + m, с индексом нильпотентности равным = n в канонической Жордановой [12, 13] форме A = J{ = 0 }. (1.169) 7. Выбрать матрицу P размерности 1 n, образующую с матрицей A полностью наблюдаемую пару ( A,P) матриц.

8. Найти решение матричного уравнения Сильвестра T A + T = L P (1.170) относительно матрицы T.

9. Сформировать проверочную матрицу H помехозащищенного (n, k)-кода в силу соотношения T H =. (1.171) Примечание 1.3 (ПМ.1.3). Множество формируемых матриц H с помощью приведенного алгоритма (А1.7) может быть существенно расширено, если в матрицах L и P допустить отличное от единицы соответственно число столбцов и строк, но при этом они всякий раз должны быть согласованы с тем, чтобы существовало их произведение L P.

1.6.3 Использование сингулярного разложения матриц в задаче формирования матриц ПЗК Рассмотрим теперь алгоритм конструирования образующей матрицы G ПЗК по известной проверочной матрице H, который основан на положениях У1.32 и использующий возможности сингулярного разложения (SVD-процедуры) матриц [12, 16]. С этой целью сделаем некоторые пояснения.

Определение 1.11 (О1.11). Сингулярным разложением [12, 16] матрицы N над произвольным полем называется ее представление в форме T N = UV, (1.172) где U - -матрица левого сингулярного базиса, V - -матрица правого сингулярного базиса, обладающие свойством над этим полем T T T T UU = U U = I, VV =V V = I, (1.173) - -квазидиагональная матрица сингулярных чисел, размещаемых на главной диагонали, при этом их число равно min{, }.

T T Если с помощью (1.172) сконструировать матрицы NN и N N, то в силу (1.173 получим T T T T T NN = U U ; N N =VT V, (1.174) при этом оказывается, что сингулярные числа совпадают с арифметиT ческими значениями корней из собственных значений матриц NN и T N N. Элементы левого сингулярного базиса U являются нормироT ванными собственными векторами матрицы NN, а элементы правого сингулярного базиса V являются нормированными собственными векT торами матрицы N N.

Выделим случай реализации -матрицы N, которая характеризуется выполнением условия <, (1.175) тогда [12, 16] - последних столбцов матрицы V правого сингулярного базиса будут принадлежать ядру матрицы N, что записывается в форме Vi ker N, i = + 1,. (1.176) Для построения алгоритма формирования образующей матрицы G ПЗК по известной проверочной матрице H, необходимо положить T N = H.

T T Если с помощью (1.172) сконструировать матрицы NN и N N, то в силу (1.173 получим T T T T T T NN = U U ; N N =V V, (1.174) при этом оказывается, что сингулярные числа совпадают с арифметиT ческими значениями корней из собственных значений матриц NN и T N N. Элементы левого сингулярного базиса U являются нормироT ванными собственными векторами матрицы NN, а элементы правого сингулярного базиса V являются нормированными собственными векT торами матрицы N N.

Выделим случай реализации -матрицы N, которая характеризуется выполнением условия <, (1.175) тогда [12, 16] - последних столбцов матрицы V правого сингулярного базиса будут принадлежать ядру матрицы N, что записывается в форме Vi ker N, i = + 1,. (1.176) Для построения алгоритма формирования образующей матрицы G ПЗК по известной проверочной матрице H, необходимо положить T N = H.

Алгоритм 1.8 (А1.8) формирования образующей матрицы G ПЗК по известной проверочной матрице H с использованием SVD-процедуры 1. Сформировать проверочную n m-матрицу H помехозащищенного (n,k)-кода с помощью приведенных А1.6 и А1.7.

T 2. Построить сингулярное разложение m n-матрицы H в форме T T H = Uн нVн, (1.177) где dimUн = m m, dim н = m n, dimVн = n n.

T 3. Сконструировать ядро матрицы H в форме T T ker H = row{i (ker H ), i = m + 1,n}. (1.178) 4. В силу соотношений (1.156) сформировать образующую матрицу G помехозащищенного (n,k)-кода в форме T T G = (ker H ). (1.179) 1.6.4 Формирование матриц ПЗК с полной блоковой систематикой Рассмотрим проблемы формирования матриц G и H ПЗК с полной блоковой систематикой. Если формирование матриц кода осуществляется с помощью алгоритма 1.6, то блоковая систематика закладывается на этапе кодировке вектор-строк однократных ошибок в m j младших разрядах помехозащищенного (n,k)-кода векторамистроками синдромов E так, чтобы последние m синдромов в таблице j кодировок образовывали m m-единичную матрицу Im. При этом проверочная матрица H (n,k)-кода примет вид (1.158), который в силу положений утверждения У.1.33 является основой для формирования образующей матрицы G ПЗК в форме (1.158).

Завершим рассмотрение поставленной проблемы формирования матриц (G,H) помехозащищенного (n,k)-кода случаем циклических ПЗК, матрицы которых обладают полной блоковой систематикой.

Приводимый ниже алгоритм строится на базе работ [42, 44].

Алгоритм 1.9 (А1.9) конструирования матриц циклического ПЗК с полной блоковой систематикой 1. Выполнить п.п. 1 - 3 алгоритма 1.7.

2. Вычислить остаток ri( x) от деления ММ, производимого на образующий ММ g( x) в силу соотношения xn-i ri( x)= rest ; i = 1,k. (1.180) g( x ) 3. Сформировать кодовые аналоги остатков ri( x) в форме m разрядных вектор-строк ~ xn-i Gi = кri( x)= rest ; i = 1,k, (1.181) g( x ) где к{(Х)} - код ММ (Х).

~ 4. Сформировать k m -матрицу G кодов остатков в силу соотношения ~ ~ G = col {Gi ; i = 1,k }. (1.182) 5. С использованием соотношения (1.158) сформировать образующую G и проверочную H матрицы циклического ПЗК с полной блоковой систематикой.

Пример 1.8 (Пр1.8) Решается задача формирования матриц G и H ПЗК (15,7), исправляющего ошибки кратности s = 2 и обладающего синдромами однократных ошибок, удовлетворяющих условиям У1.31.

Формирование матриц требуется осуществлять с помощью проверочных равенств при декодировании и кодировании. Тогда, следуя алгоритму 1.6:

1. Составим таблицу 1.2 однократных ошибок, используя синдромы группового кода [50], исправляющие ошибки кратности s = 2.

2. Составим проверочную матрицу H, используя соотношение (1.158), в результате чего получим 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 j H = col{ H = En+1- j ; j = 1,15}= 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Таблица 1.Синдром Синдром Номер искаженного раз- Номер искаженного разE = [E8 E7 E6 E5 E4 E3 E2 E1] E = [E8 E7 E6 E5 E4 E3 E2 E1] ряда ряда 15 1 1 0 1 1 0 1 1 7 0 0 1 0 0 0 0 14 1 0 1 1 0 1 0 1 6 0 0 0 1 0 0 0 13 1 0 0 1 0 1 1 0 5 0 0 0 0 1 1 1 12 1 0 0 0 0 0 0 0 4 0 0 0 0 1 0 0 11 0 1 1 0 1 0 1 0 3 0 0 0 0 0 1 0 10 0 1 0 1 0 1 0 1 2 0 0 0 0 0 0 1 9 0 1 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 1 1 0 0 1 3. Составим аналитические выражения для каждого разряда E,= m,1 синдрома в силу соотношения (1.162), которые примут вид E8 = f15 + f14 + f13 + fE7 = f15 + f11 + f10 + fE6 = f14 + f11 + f8 + fE5 = f15 + f14 + f13 + f9 + f8 + fE4 = f15 + f11 + f5 + fE3 = f14 + f13 + f10 + f5 + fE2 = f15 + f13 + f11 + f8 + f5 + fE1 = f15 + f14 + f10 + f8 + f5 + f4. Сформируем аналитические выражения для помехозащитного кодирования, используя соотношения (1.163), в результате чего получим y12 = y15 + y14 + yy9 = y15 + y11 + yy7 = y14 + y11 + yy6 = y15 + y14 + y13 + y10 + yy4 = y15 + y11 + yy3 = y14 + y13 + y10 + yy2 = y13 + y15 + y11 + y8 + yy1 = y15 + y14 + y10 + y8 + y5. Сформируем образующую матрицу G ПЗК (15,7), используя соотношение (1.166). Для этого заметим, что соотношения, полученные в п.4 алгоритма, обнаруживают, что проверочными разрядами ПЗК являются 12, 9, 7, 6, 4, 3, 2, 1, а информационными - 15, 14, 13, 11, 10, 8, 5-й разряды. Если теперь процесс (1.144) формирования ПЗК записать в развернутой форме, [ y15 y14 y13 y12 y11 y10 y9 y8 y7 y6 y5 y4 y3 y2 y1 ]=, = [a7 a6 a5 a4 a3 a2 a1 ]G где y15 = ay14 = ay13 = ay12 = ay11 = ay10 = ay9 = ay8 = a7 + a6 + ay7 = a7 + a4 + ay6 = a6 + a4 + ay5 = a7 + a6 + a5 + a3 + ay4 = a7 + a4 + ay3 = a6 + a5 + a3 + ay2 = a7 + a5 + a4 + a2 + ay1 = a7 + a6 + a3 + a2 + aто образующая матрица кода (15,7) принимает вид G = Примечание 1.4 (ПМ1.4). Рассмотренный ПЗК (15,7), исправляющий ошибки кратности s = 2 имеет избыточное число проверочных разрядов. Действительно, число синдромов Nc = 2m - 1 = 28 - 1 = 255, а число ошибок первой и второй кратности 1 Nош = Сn + Сn = n(n + 1)/ 2 = 120. Складывается впечатление, что соотношение Nc > Nош сохранится, если число m проверочных разрядов сократить с 8 до 7. Действительно, в этом случае код (15,7) трансформировался бы в код (14,7), для которого было бы справедливо неравенство 1 Nc = 2m - 1 = 27 - 1 = 127 Nош = Сn + Сn = 105.

Но в этом случае необходимо было бы приведенные в таблице 1.1 синдромы укоротить на один старший разряд. Однако при этом нарушается условие [42, 51] и корректирующая способность ПЗК, исправляющего ошибки кратности s = 2, что вызывается появлением нулевого синдрома (для ошибки в двенадцатом разряде в рамках рассмотренного примера) и сокращением кодового расстояния между синдромами до dmin = 3.

Пример 1.9 (Пр1.9) Иллюстрируется процедура формирования проверочной матрицы H ПЗК (7,4), исправляющего ошибки кратности s = 1.

Читателю предлагается убедиться, что проверочная матрица H вида 1 0 ~ G ~ 1 1 H =, где G =, 1 1 I 0 1 получена решением уравнения Сильвестра (1.170) относительно матT рицы = H с матричными компонентами 0 1 0 I T = 1 0 1 ; L = 0 ; A = ].

T O7 O6 ; P =[1 O 1 0 0 Матрица H обнаруживает полную блоковую систематику ПЗК ~ (7,4), поэтому образующая матрица кода принимает вид G =[I4 G].

Пример 1.9 (Пр1.9) Иллюстрируется процедура формирования проверочной матрицы H ПЗК (7,4), исправляющего ошибки кратности s = 1.

Pages:     | 1 |   ...   | 6 | 7 | 8 | 9 | 10 |   ...   | 24 |    Книги по разным темам