Книги по разным темам Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 24 |

dim x = m, dimu = 1, dim A =(m m), dim B =(m 1). В зависимости от задачи помехозащитного кодопреобразования u(k) принимает смысл помехонезащищенного информационного кода u(k)= a(k) при формировании помехозащищенного кода y(k) и смысл принятого из канала связи искаженного кода f (k)= y(k)+ (k) так, что u(k)= f (k) в задаче декодирования. Характерной особенностью модельных представлений (1.224) и (1.225) является то, что матрица Aку состояния кодирующего устройства и матрица Aдку состояния декодирующего устройства совпадают так, что выполняется равенство Aку = Aдку = A. (1.226) Матрица A состояния КУ и ДКУ задается в одном базисе, при этом чаще всего в сопровождающей характеристический полином (ХП) форме, причем ХП D()= det(I + A) совпадает с образующим ПЗК модулярным многочленом g( x) так, что выполняется соотношение D()= g( x) (1.227) x= Матрицы входа для устройств кодирования и декодирования чаще всего не совпадают так что для КУ и ДКУ модель (1.224) соответственно получает представление x(k + 1)= A x(k)+ Bку u(k); x(k + 1)= A x(k)+ Bдку u(k). (1.228) Если при формировании ПЗК предполагается возможность перехода от их матричного задания, не параметризованного дискретным временем k, с помощью образующей матрицы G и проверочной матрицы H, то следует иметь в виду следующее. Необходимое условие реализуемости матричного представления ПЗК (1.144), (1.146) дивидендным способом, осуществляемым средствами ЛДДС (1.228), является однозначное соответствие строк проверочной матрицы H ПЗК с точностью до процедуры транспонирования с матрицей входа Bдку устройства де~ кодирования и строк матрицы G при представлении образующей матрицы ПЗК в форме (1.158) с матрицей входа Bку (1.228) устройства кодирования.

Высказанные соображения подтвердим следующими утверждениями.

Утверждение 1.42 (У1.42). Матрица Bку ЛДДС дивидендного кодирующего устройства с точностью до операции транспонирова~ ния совпадает с последней строкой ( k -ой) строкой Gk образующей матрицы G так, что выполняется соотношение ~k T Bку = G = {g( x)+ xm}, (1.229) где {(Х)} - код модулярного многочлена (Х).

Доказательство. Рассмотрим процесс кодирования для случая u(k)= a( x)= 1, то есть для случая k -элементной входной последовательности u(k)= [u(0)= 0, u(1)= 0,, u(k - 2)= 0, u(k - 1)= 1]. (1.230) В течение первых (k - 1)-тактов ЛДДС КУ будет находится в нулевом неподвижном состоянии. При приеме элемента u( k - 1) = 1 ЛДДС КУ (1.228) перейдет в состояние x(k)= Bку u(k - 1) = Bку. (1.231) u ( k-1)=Состояние (1.231) определяет код остатка, выводимый из КУ, для ~ a( x)= 1, задаваемый последней строкой матрицы G кодов остатков так, что выполняется цепочка равенств ~k T xT (k)= Bку = G = {g( x)+ xm}. (1.232) Утверждение 1.43 (У1.43). Матрица Bдку входа ЛДДС (1.228) дивидендного декодирующего устройства с точностью до процедуры транспонирования совпадает с последней строкой проверочной матрицы H ПЗК так, что выполняется равенство T n Bдку = H. (1.233) Доказательство. В силу идентичности результатов процедур формирования синдрома E при декодировании в форме (1.146), (1.151) с целью анализа процессов в ЛДДС (1.228) при декодировании рассмотрим последний при входной последовательности u(k)= (k). Как и выше, ограничимся ситуацией, когда последовательность (k) содержит единицу только в младшем разряде u(k)= (k)= [u(0)= 0, u(1)= 0,, u(k - 2)= 0, u(k - 1)= 1]. (1.234) При входной последовательности вида (1.234) ЛДДС (1.228) устройства декодирования в течение первых ( n - 1)-тактов, характеризующихся u(k)= 0 остается в нулевом неподвижном состоянии, а на последнем n -м такте перейдет в состояние, совпадающее с матрицей Bдку. Однако в силу правил декодирования это состояние представляет собой синдром ошибки в младшем разряде, который в силу правил формирования проверочной матрицы H ПЗК является ее последней строкой, что приводит к цепочке равенств T n E = xT (n)= Bдку = H. (1.235) Поставим задачу: матрица A ЛДДС устройств кодирования и декодирования (1.228) фиксирована, матрица входа ЛДДС кодирующего устройства фиксирована в форме (1.232), модифицируема ли матрица входа ЛДДС устройства декодирования при сохранении матричного характеристического свойства ПЗК (1.146) GH = O С целью решения поставленной задачи сформулируем утверждение, предварив его следующим определением.

Определение 1.14 (О1.14). Матрицей циклического сдвига на один шаг вниз строк произвольной (n m)-матрицы H называется (n n)-матрица Pc вида O1 ( n-1) I1 Pc =. (1.236) I(n-1) (n-1) O( n-1) Определение 1.15 (О1.15). Матрицей циклического сдвига на один шаг вверх произвольной (n m)-матрицы H называется (n n)матрица Pc-1 вида O( n-1)1 I(n-1) (n-1) Pc-1 =. (1.237) I1 1 O1 ( n-1) Из (1.236) и (1.237) видно, что матрицы циклического сдвига вниз и вверх строк произвольной (n m)-матрицы H связаны соотношениями Pc-1 = PcT, Pc PcT = PcT Pc = I. (1.238) Определение 1.16 (О1.16). Матрицей циклического сдвига на шагов вниз строк произвольной (n m)-матрицы H называется (n n)-матрица Pc вида O ( n- ) I Pc =. (1.239) I(n- ) (n- ) O( n-v)v Определение 1.17 (О1.17). Матрицей H( ) размерности (n m), полученной из (n m)-матрицы H путем сдвига на шагов ее строк вниз, называется матрица, вычисленная в силу матричного соотношения H( ) = Pc H. (1.240) Утверждение 1.44 (У1.44). Характеристическое свойство (1.147) матриц (G,H) помехозащищенного кода сохраняется для матриц (G,H( )) так, что GH( )= GPc H. (1.241) Доказательство утверждения строится на использовании матрицы G, записанной в каноническом виде (1.158) ~ G =[Ikk G], и матрицы H, записанной в форме T H =[An-1Bдку An-2Bдку ABдку Bдку]. (1.242) При этом используются свойства (m m)-матрицы A принадлежности показателю n = 2m - 1, в силу чего выполняется равенство An = I, (1.243) а также справедливости теоремы Гамильтона-Кэли позволяющей записать D() = D( A)= O. (1.244) =A Если записать (1.241) в транспонированной форме T T H (Pc ) GT, (1.245) подставить в нее матрицу H в форме (1.242), Pc в форме (1.239) и матрицу G в форме (1.158), учесть (1.243) и (1.244), тогда получим матричное соотношение T T i H (Pc ) GT = row{A D( A)Bдку ; i = 1,k, i = 0,1,2,,m}= O. (1.246) Пример 1.12 (Пр1.12).

Проиллюстрируем положения У1.44 на примере циклического ПЗК с образующим ММ g( x)= x3 + x + 1, который характеризуется матрицами G и H 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 T G = ; H = 0 1 1 1 0 1 0 (1.247) 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 Матрица Pc циклического сдвига вниз строк матрицы H на один шаг (1.236) имеет вид O1 7 Pc =. (1.248) I7 7 O7 Тогда для матриц (1.245) для = 0, = 3, = 6 получим 1 0 0 0 1 0 0 0 1 T 0 0 0 1 ;

H GT =[A6 Bдку A5Bдку A4Bдку A3Bдку A2Bдку ABдку Bдку] 1 1 1 0 1 1 1 1 0 (1.249) T H (Pc3)GT = 1 0 0 0 1 0 0 0 1 ;

=[A2Bдку ABдку Bдку A6 Bдку A5Bдку A4Bдку A3Bдку] 0 0 0 1 1 1 0 1 1 1 1 0 (1.250) T H (Pc6 )GT = 1 0 0 0 1 0 0 0 1.

=[A5Bдку A4Bдку A3Bдку A2Bдку ABдку Bдку A6 Bдку] 0 0 0 1 1 1 0 1 1 1 1 0 (1.251) Раскрытие произведений матриц позволяет для (1.248) - (1.250) записать T H GT =[(A6 + A2 + I)Bдку (A5 + A2 + A + I)Bдку (1.252) (A4 + A2 + A)Bдку (A3 + A + I)Bдку] T H (Pc3)GT = [(A5 + A3 + A2)Bдку (A5 + A4 + A3 + A)Bдку (1.253) (A5 + A4 + I)Bдку (A6 + A4 + A3)Bдку] T H (Pc6 )GT = [(A6 + A5 + A)Bдку (A6 + A4 + A + I)Bдку (1.254) (A3 + A + I)Bдку (A6 + A2 + I)Bдку] Если в (1.252) - (1.254) учесть (1.243) и (1.244), записываемые для рассматриваемого примера в форме A7 = I, D( A)= A3 + A + I = O, (1.255) то (1.252) - (1.254) примут вид T H GT = [A-1D( A)Bдку A2D( A)Bдку (1.256) AD( A)Bдку D( A)Bдку]= O T H (Pc3)GT = [A2D( A)Bдку AD( A)Bдку (1.257) A-3D( A)Bдку A3D( A)Bдку]= O T H (Pc6 )GT = [A-2D( A)Bдку A3D( A)Bдку (1.258) D( A)Bдку A-1D( A)Bдку]= O Общее представление результатов (1.256) - (1.258) имеет вид (1.246).

Утверждение (У1.44) и Пр1.11 по существу содержат доказательство следующего утверждения.

Утверждение 1.45 (У1.45). В качестве матрицы входа устBдку ройства дивидендного декодирования, реализованного в форме линейной ДДС (1.228), может быть принята любая строка проверочной матрицы H помехозащищенного кода в транспонированном виде так, что Bдку = HiT, i = n,1 (1.259), при этом образующая и проверочная матрицы ПЗК, сформированного средствами ЛДДС (1.228) с матрицей входа (1.259) устройства декодирования сохраняют свое характеристическое свойство (1.147).

Таким образом пользователь аппаратуры дивидендного помехозащитного кодирования - декодирования без изменения ее кодирующей части может модифицировать декодирующую часть путем изменения матрицы входа декодирующего устройства. Количество вариантов Bдку модификации матрицы составляет Nв = n, где n - полное число Bдку разрядов помехозащищенного (n,k)-кода. При этом опасность получения неуправляемой пары матриц ( A,Bдку) на указанном наборе отсутствует, так как матрица при всех ее версиях не является собственBдку ным вектором матрицы A. Последнее объясняется тем, что матрица A состояния ЛДДС кодирующих и декодирующих устройств (1.228) имеет своим характеристическим полиномом неприводимый модулярный многочлен, который не имеет корней в простом поле Галуа GF(2), что гарантирует и отсутствие собственных векторов.

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

Алгоритм 1.11 (А1.11) синтеза ЛДДС дивидендного помехозащитного кодирования и декодирования 18. По заданному информационному массиву Q мощности [Q]= Nи определить размерность k помехозащищенного кода в силу соотношения k = arg{2k Nи = [Q]}.

19. По заданной корректирующей способности помехозащищенного (n,k)-кода определить степень m = n - k его образующего модулярного многочлена g( x) в силу соотношения s i m = arg Nc = 2m - 1 Nош = C, (k+m) i=где Nc - число синдромов, Nош - число ошибок, s - кратность исправляемой ошибки. Выбрать или сформировать реализацию образующего ММ g( x) степени m в классе неприводимых, гарантирующих минимальное кодовое расстояние dmin на используемых кодовых комбинациях ПЗК dmin 2s + 1.

20. Вычислить D-образ ММ g( x) в форме ~ g(d)=D{g( x)}= g(x-1), x-1=d ~ ~ где g(x-1): g( x)= xm g(x-1).

21. Сконструировать передаточную функцию устройства деления модулярных многочленов в форме (d)=.

g(d) 22. Пользуясь правилом Мейсона некасающихся контуров построить структурную реализацию (d ) на элементах памяти (ЭП) с передаточной функцией ЭП (d)= d.

23. Произвести отметку входов и выходов ЭП переменными xi(k + 1) на входе и xi(k) на выходе и сформировать векторноматричное описание автономной версии УДММ x(k + 1)= Ax(k).

24. Сформировать матрицу входа Bку дивидендного кодирующего устройства (1.228) в силу соотношения (1.229).

25. Сформировать проверочную матрицу H ПЗК и матрицу Bдку входа дивидендного декодирующего устройства (1.228) в силу соотношения (1.259).

26. Проверить правильность функционирования устройств кодирования и декодирования (1.228) сформированными парами матриц (A,Bку ) и (A,Bдку ).

27. Построить техническую реализацию устройств дивидендного кодирования и декодирования:

a. в схемотехнической форме на базе структурных представлений;

b. в программной форме на базе рекуррентных процедур (1.228).

2. НЕЛИНЕЙНЫЕ ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ (НДДС) ДИСКРЕТНОЙ АВТОМАТИКИ Рассматриваются проблемы, связанные с использованием нелинейных двоичных динамических систем (НДДС) в составе устройств дискретной автоматики. Причем первоочередной проблемой является разработка методологии и алгоритмического обеспечения конструирования нелинейных модельных представлений ДДС. В связи с тем, что нелинейность в общесистемной постановке суть разновидность статической памяти, то следует ожидать при использовании НДДС в составе устройств дискретной автоматики для решения задач кодопреобразования заметного сокращения размерности кода состояния ДДС, что влечет за собой системологическую проблему кодового пространства на классе ЛДДСЦНДДС реализаций проектируемых двоичных систем. При этом разработчик УДА должен помнить, что априорным преимуществом НДДС перед ЛДДС является возможность использования всего банка существующей триггерной логики, что существенно расширяет класс схемотехнических реализаций ДДС.

2.1. Построение модельного представления НДДС с использованием средств автоматной логики В настоящем параграфе в развитие положений параграфа 1.2, в котором в классе моделей входЦсостояниеЦвыход (ВСВ) (1.20) построены линейные представления правил (функций) перехода и выхода в форме (1.23) и (1.24), ставится задача конструирования их нелинейных аналогов. Для целей построения нелинейных модельных представлений правил и при описании ДДС используются возможности автоматной логики [6, 7, 8, 14, 39] в двух ее реализациях.

Одна из этих реализаций опирается на процедуру канонического автоматного синтеза ДДС, а другая - на процедуру автоматного синтеза ДДС с использованием граф-схем алгоритмов (ГСА) ее функционирования.

Первая из отмеченных процедур конструирования нелинейного модельного представления в форме НДДС реализуется в виде следующего алгоритма.

Алгоритм 2.1 (А2.1) конструирования модельного ВСВ представления НДДС на основе канонического автоматного синтеза 1. Сформулировать постановку задачи кодопреобразования, решаемой конструируемой ДДС.

2. Формализовать задачу кодопреобразования в виде абстрактного автомата (АА), задаваемого в виде пятиэлементного макровектора AА:{ Z,S,W,, }, (2.1) где Z - алфавит высокого уровня (с возможным использованием вербальных описаний) входов абстрактного автомата мощности [Z]= rZ, S - алфавит высокого уровня его состояния мощности [S]= nS, W - алфавит высокого уровня выходов АА мощности [W]= mW, - правило (функция) перехода АА s(k + 1)= [s(k), z(k)], s(0); (2.2) - правило (функция) выхода, задаваемое функциональными соотношениями соответственно W(k)= [s(k)] (2.3) в логике абстрактного автомата Мура и W( k)= [s(k), z(k)] (2.4) в логике абстрактного автомата Мили. В (2.2) - (2.4) s(0), s(k), s(k + 1) - соответственно начальное состояние, исходное состояние и состояние перехода АА, k - дискретное время, выраженное в числе тактов длительностью t. При этом основным математическим средством описания правил (функций), на первом этапе конструирования являются графы переходов и выходов, на втором - таблицы переходов и выходов.

Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 24 |    Книги по разным темам