5.7.3. Критерий, основанный на использовании функции Ляпунова [32]

Пусть с — произвольное множество векторов, а с — множество, являющееся дополнением с. Пусть функция, принимающая два значения и такая, что если бес, и если . Изменение функции связанное с изменением состояния при сдвиге, обозначим через Величина тогда и только тогда, когда состояние переходит из или, наоборот, из . Следовательно, если состояние не изменяется, то Аналогом теоремы Ляпунова об асимптотической устойчивости является следующая теорема.

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

Эта теорема показывает, что регистр сдвига с нелинейной обратной связью является устойчивым, если при сдвиге любое его ненулевое внутреннее состояние переходит в состояние 0, и неустойчивым, если при сдвиге никакое состояние, кроме, быть может, нулевого, не переходит в состояние 0. Однако, как правило, в действительности часть ненулевых состояний при сдвиге переходит в состояние 0, но существуют также так называемые неопределенные состояния, которые при сдвиге в состояние 0 не переходят. Для определения устойчивости при наличии таких неопределенных состояний можно воспользоваться следующим алгоритмом:

1) Пусть множество, включающее только состояние 0.

2) Определим функцию так, как указано в теореме 5.5.

3) Пусть множество всех таких что и пусть Состояния, принадлежащие обладают тем свойством, что при сдвиге они переходят в состояние 0. Если

является пустым множеством, т. е. если то из теоремы 5.5 следует, что рассматриваемая схема устойчивая, а если то эта схема неустойчивая. Если ни одно из этих условий не выполняется, то переходим к следующему шагу:

4) Определим функцию если если

5) Пусть множество всех состояний , для которых и пусть относятся те состояния, которые переходят в состояние 0 в результате двух сдвигов.

6) Этот процесс будем продолжать до тех пор, пока одно из множеств или не окажется пустым (заметим, что для этого потребуется конечное число шагов а именно Если т. е. если все состояния после или менее сдвигов переходят в состояние 0, то схема является устойчивой. Если то существует некоторое ненулевое состояние, которое никогда в состояние 0 не переходит, что означает неустойчивость исследуемой схемы.

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

и

Тогда

и

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

Пример 5.8. Воспользуемся описанным выше алгоритмом для определения устойчивости декодирующей логической схемы ортогонализуемого кода из примера 5.6. Регистр сдвига с нелинейной обратной связью в этом случае имеет вид, показанный на фиг. 5.7. В целях упрощения внутренние состояния этого регистра будем представлять в десятичной записи, а именно состоянию сопоставим десятичное число в режиме самоконтроля всегда равно 0). Состояния ячеек регистра, которые могут принимать значения и 0 и I, будем обозначать через Основываясь на фиг. 5.7, можно установить следующее:

1) При однократном сдвиге только состояние десятичным представлением которого является число 16, переходит в состояние 0.

2) При однократном сдвиге в состояние 16 переходят лишь состояния вида состояния 8 и 24.

3) При однократном сдвиге в состояние 8 или 24 переходят лишь состояния вида т. е. состояния 4, 20, 12 и 28.

4) При однократном сдвиге в состояния 4, 20, 12 и 28 переходят лишь состояния вида и т.е. состояния 2, 18, 10, 6, 22, 24.

Фиг. 5.7. Регистр синдрома -кода,

Продолжая этот процесс дальше, построим табл. 5.4 и найдем, что Это означает, что рассматриваемая схема является неустойчивой.

Однако вывод о неустойчивости схемы, изображенной на фиг. 5.7, не означает, что эта схема имеет бесконечную глубину распространения ошибок. Декодирующая логическая схема всегда начинает работать с нулевого внутреннего состояния и в зависимости от значений символов синдрома, поступающих на ее вход, проходит те или иные внутренние состояния. Следовательно, из всех внутренних состояний регистра сдвига с нелинейной обратной связью с распространением ошибок связаны лишь так называемые достижимые состояния, т. е. состояния, в которых регистр может оказаться при всевозможных синдромах на его входе. Здесь вместо определения 5.3, которое понятие устойчивости связывало со всеми внутренними состояниями, рассмотрим следующее определение.

Определение 5.4. (Месси, Лиу.) Регистр сдвига с нелинейной обратной связью называется устойчивым по отношению к входному воздействию тогда и только тогда, когда для любого состояния 6, которое этот регистр может достичь из состояния 0

Таблица 5.4 (см. скан) Определение устойчивости схемы, изображенной на фиг. 5.7

при той или иной входной последовательности, существует такое число что

Если регистр сдвига с нелинейной обратной связью является устойчивым по отношению к входному воздействию, то глубина распространения ошибок бесконечной быть не может. Наоборот, если регистр сдвига с нелинейной обратной связью не является устойчивым по отношению к входному воздействию, то глубина распространения ошибок может оказаться и бесконечной. Заметим, что если регистр сдвига с нелинейной обратной связью является просто устойчивым, то он устойчив и по отношению к входному воздействию. Обратное утверждение неверно. Действительно, как было показано выше, регистр сдвига, изображенный на фиг. 5.7, не является устойчивым, поскольку из состояния 29 нельзя достичь состояния 0. Из состояния 29 этот регистр вновь переходит в состояние 29, т. е. это состояние является равновесным состоянием. При определенных последовательностях на входе в состояние 29 можно попасть из состояний 30 и 14. В состояние 14 можно попасть только из состояния 7, но состояние 7 является недостижимым (т. е. в него нельзя попасть из состояния 0). Кроме того, недостижимым является и состояние 30. Следовательно, регистр сдвига с нелинейной обратной связью, изображенный на фиг. 5.7, является устойчивым по отношению к входному воздействию и имеет конечную глубину распространения ошибок.