Мажоритарные методы преобразования сигналов в телекоммуникационных системах тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Рощин, Андрей Борисович

• Рощин, Андрей Борисович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Рощин, Андрей Борисович

Предисловие

1. Введение

Выводы по главе

2. Уплотнение каналов и помехоустойчивое кодирование сигналов на основе мажоритарного преобразования

2.1. Мажоритарное уплотнение каналов

2.2. Каскадное мажоритарное уплотнение и кодирование при полной загрузке системы

2.3. Повышение помехоустойчивости системы с каскадным мажоритарным уплотнением, с постоянным числом каскадов и жесткими решениями

2.3.1. Характеристики мажоритарно уплотненных сигналов при отсутствии помех в канале связи

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

2.3.3. Совместная обработка со стиранием

2.3.4. Исправление ошибок по модифицированному методу Вагнера

2.4. Словная синхронизация мажоритарно уплотненных сигналов

Выводы по главе

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

3.1. Методы обеспечения приоритета в помехоустойчивости при мажоритарном уплотнении

3.2. Сравнительная эффективность приоритетной передачи количественной информации при мажоритарном уплотнении

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

3.3.1. Классификация систем с неполной загрузкой

3.3.2. Анализ помехоустойчивости каскадного мажоритарного мультисе-лека в системах с неполной загрузкой

3.3.3. Зависимости между помехоустойчивостью, активностью и блоковой длиной канальных сигналов при мажоритарном уплотнении

3.3.4. Системы с программируемой загрузкой

3.3.5. Системы с адаптивной загрузкой

3.4. Помехоустойчивость каскадных мажоритарно уплотненных сигналов при пакетных ошибках в каналах связи

3.4.1. Количественные характеристики для типичных параметров каналов с пакетными ошибками

Выводы по главе

4. Аутентификация субъектов доступа в информационных системах с использованием интерактивных алгоритмов и мажоритарного преобразования сигналов

4.1. Общие сведения о проблеме аутентификации информации. Криптоалгоритмы шифрования и хэширования.

4.2. Использование алгоритмов хэширования для аутентификации субъектов доступа.

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

4.4. Выбор основных параметров и оценка стойкости криптозамка . лло

4.5. Возможности использования каскадного мажоритарного уплотнения и кодирования для скремблирования и криптографической защиты цифровой информации

Выводы по главе

5. Экспериментальная часть и внедрение результатов диссертационной работы

5.1. Компьютерное моделирование каскадного мажоритарного кодека-мультиселека

5.2. Макетирование двухкаскадного мажоритарного кодека-мультисе-лека

5.2.1. Описание экспериментального макета

5.2.2. Согласование источников сообщений с различной производительностью в экспериментальном макете

5.2.3. Внедрение результатов диссертационной работы

Выводы по главе

Введение диссертации (часть автореферата) на тему «Мажоритарные методы преобразования сигналов в телекоммуникационных системах»

Преобразования сигналов, осуществляемые в современных радиоэлектронных системах, являются, как правило, линейными операциями. Линейные операции — это усиление, сложение сигналов и их умножение на некоторые постоянные величины. Линейные методы преобразования сигналов базируются на строгих и глубоких методах современной дискретной математики - линейной алгебре, теории полей Галуа, векторном и комбинаторном анализе, теории матриц и др. Однако нелинейные методы преобразования сигналов во многих случаях оказываются более предпочтительными — и по большей простоте их реализации, и по эффективности конечных результатов. Нелинейные методы по-новому позволяют решать задачи уплотнения и кодирования сигналов, вопросы защиты информации от несанкционированного доступа и задачи аутентификации пользователя в информационных системах. Ряд этих вопросов исследуется в настоящей диссертационной работе.

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

Мажоритарная логическая операция относится к булевским операциям пороговой логики [5,32]. Пороговой элемент (ПЭ) - это более общая булевская операция, чем мажоритарный элемент (МЭ), поскольку реализуемая на ПЭ булевская функция будет истинна (т.е. ее значение равно 1) при любом желательном установленном пороге. В МЭ логическая функция истинна, когда более половины переменных из входного набора равны 1.

Большим вниманием пороговая логика и ПЭ, а, следовательно, и МЭ, стали пользоваться с конца 50-х годов прошлого века [5,32]. Это время было временем стремительного развития булевской алгебры как раздела дискретной математики. Эти математические результаты быстро нашли практическое применение, в частности, для декодирования линейных циклических кодов [9,27], для защиты информации от несанкционированного доступа [7,15], для помехоустойчивого кодирования и уплотнения каналов [23,25,28]. Наиболее актуальные из приложений мажоритарного преобразования сигналов рассматриваются в данной диссертационной работе. В частности, исследуются возможности повышения помехоустойчивости и эффективности многоканальных телекоммуникационных систем [31], а также рассматриваются методы защиты информации для целей аутентификации пользователя в информационных системах с использованием мажоритарного преобразования сигналов [18,19,20,21].

Основное внимание в данной диссертационной работе уделено системам и сетям передачи информации, в которых используется мажоритарное уплотнение и кодирование передаваемых сигналов. Впервые использование мажоритарной операции для уплотнения каналов предложил Р.Титсворт в 1964г. [28], который также показал, что среди всех функций булевской алгебры (логических функций) мажоритарная функция является оптимальной при решении задачи уплотнения каналов. Основной недостаток мажоритарного уплотнения, предложенного Р.Титсвортом - это очень низкая эффективность использования полосы частот, занимаемой системой передачи информации. Избыточность, которую необходимо вводить в передаваемый групповой сигнал при мажоритарном уплотнении, предложенном Р.Титсвортом, экспоненциально растет с ростом числа уплотняемых каналов. Кроме того, эта система проигрывает идеальной некодированной системе с временным разделением каналов в требуемом отношении сигнал/шум h =Eb/N0 на 2 дБ (Еь - битовая энергия на входе первой решающей схемы приемника, No - спектральная плотность мощности аддитивного белого гауссовского шума, действующего в канале связи).

Существенно повысить эффективность использования полосы частот, занимаемой системой передачи информации с мажоритарным уплотнением каналов, удалось, используя каскадное мажоритарное уплотнение [12,23,25,29,31], впервые предложенное в [29]. Суть этого метода состоит в том, что процедура уплотнения (разделения) каналов осуществляется на I > 1 каскадах (ступенях). При уплотнении выходные сигналы мажоритарных элементов первого каскада уплотнения являются входными сигналами для второго каскада уплотнения и т.д. до тех пор, пока на финальном (I -ом) каскаде не будет сформирован финальный групповой сигнал - двоичный сигнал в последовательной форме. Разделение каналов также осуществляется на I каскадах, и на финальном каскаде восстанавливаются в параллельной форме информационные символы.

На всех -1)-ом каскадах разделения мажоритарно уплотненных сигналов в [23,25] было предложено использовать "мягкие" решения, т.е. решения со стираниями, и только на финальном каскаде разделения использовать жесткие решения. Следовательно, на всех промежуточных каскадах селектора (на всех каскадах, кроме финального) используется троичный сигнал {1,0,-1}, и лишь на финальном каскаде выходным сигналом будет двоичный сигнал {±1}, поскольку получателю требуется именно двоичный сигнал. В [23,25] получены совокупности оптимальных решающих правил для селектора каналов со стиранием. Использование этих решающих правил позволило получить энергетический выигрыш кодирования (ЭВК) такого каскадного мажоритарно уплотненного сигнала по сравнению с сигналом, формируемым в некодированной системе с временным разделением каналов.

В настоящее время в большинстве систем и сетей передачи информации не все уплотняемые источники являются одновременно активными, т.е. не у всех уплотняемых источников всегда есть информация, подлежащая передаче. Такие системы называются системами с неполной загрузкой. Системы с программируемой загрузкой - это системы с неполной загрузкой, в которых определенные источники информации отключаются (подключаются) по определенной программе. Системы с адаптивной загрузкой - это системы с неполной загрузкой, в которых информация от уплотняемых источников подвергается сжатию. В результате такого сжатия некоторые данные устраняются, и поток информации от источника оказывается переменным во времени. При использовании линейных методов уплотнения каналов, в частности, временного уплотнения, получить возможности повышения полосной и энергетической эффективности системы передачи информации с адаптивной загрузкой можно используя незакрепленные каналы, а, следовательно, адресацию источников информации и последующую буферизацию передаваемых данных [22]. Однако необходимость адресации источников приводит к увеличению избыточности передаваемых сигналов, т.е. к увеличению требуемой пропускной способности системы.

В настоящей диссертации показано, что в системе с каскадным мажоритарным уплотнением, которая является системой с закрепленными каналами и, следовательно, в ней не требуется адресация источников, уменьшение числа активных источников автоматически ведет к повышению помехоустойчивости системы как при программируемой, так и адаптивной загрузке без каких-либо перестроек в алгоритмах уплотнения и разделения каналов [31]. Это может быть объяснено двумя способами: математически - при снижении числа активных источников векторы, представляющие групповые сигналы в пространстве сигналов, удаляются друг от друга на больший угол. С радиотехнической точки зрения мажоритарная операция - это операция клиппирования (жесткого ограничения) линейно уплотненного группового сигнала, что приводит к появлению междуканальных перекрестных помех. Чем меньше амплитуда выбросов линейно уплотненного группового сигнала, поступающего на жесткий ограничитель, тем ниже уровень этих перекрестных помех.

Помехоустойчивость таких систем с каскадным мажоритарным уплотнением исследуется в настоящей диссертации. Однако оказывается, что мягкие решения, предложенные в [23,25] для повышения помехоустойчивости, при этом не могут быть использованы, поскольку в троичном выходном сигнале модуля разделения {1,0,-1} символ "0" будет соответствовать случаю, когда источник сообщения является неактивным. Следовательно в системах с неполной загрузкой при каскадном мажоритарном уплотнении возможно использование в модулях разделения только жестких решений на всех каскадах разделения.

Для повышения помехоустойчивости в такой системе, а, следовательно, и для повышения ее энергетической эффективности, в диссертации предлагается использовать в каждом модуле разделения мажоритарно уплотненного сигнала дополнительный канал корреляционной обработки - (т+1)-ый канал, где т - число каналов обработки в обычном модуле разделения. Опорным сигналом в этом (т+1)-ом канале корреляционной обработки является поразрядная сумма по модулю два всех ш других канальных сигналов. Основываясь на разложении мажоритарно уплотненного сигнала в ряд Уолша-Фурье [25], можно показать, что сумма по модулю два всех (т+1) выходных сигналов модуля разделения будет всегда либо нечетной (если (т+1) кратно 4, т.е. если (т+1) =0 (mod4)), либо четной (если (т+1) некратно 4, т.е. если (m+1) (mod4)). А для совместной обработки выходных сигналов модулей разделения с дополнительным (т+1)-ым каналом в диссертационной работе предложено метод Вагнера, известный в теории и технике линейных кодов с проверкой на четность [14], в несколько модифицированном виде, с учетом особенностей системы с мажоритарным уплотнением. В диссертации показано, что использование модифицированного метода Вагнера позволяет повысить помехоустойчивость системы с каскадным мажоритарным уплотнением и модулями разделения с жесткими решениями, проведен анализ такой системы и рассчитаны количественные характеристики - битовая вероятность ошибки при приеме в функции битового отношения сигнал/шум, разработаны конкретные блок-схемы этого метода разделения мажоритарно уплотненного сигнала.

Важными вопросами при приеме цифровых сигналов являются вопросы их синхронизации. Символьная синхронизация мажоритарно уплотненных сигналов ничем не отличается от символьной синхронизации любых других двоичных сигналов [36]. Блоковая (словная) синхронизация в многоканальных цифровых системах с линейным уплотнением каналов, например временным уплотнением, обычно осуществляют, помещая при передаче на первой (последней) позиции каждого блока (слова) однотипный символ - либо 1, либо -1 [36]. Затем накопители на приемной стороне накапливают принятые символы, равноотстоящие на (п+1) позиций. Поскольку символы, находящиеся в неправильной фазе слова, будут приблизительно равновероятны по полярности (±1), то результат их накопления через N тактов будет случайной величиной и иметь математическое ожидание, равное нулю. Накопление же в правильной фазе при отсутствии ошибок в канале связи даст величину N.

Автором диссертации предложен такой же метод накопления для мажоритарно уплотненных сигналов, который, однако, не требует введения в передаваемый сигнал дополнительных символов синхронизации [31]. Это уменьшает затраты пропускной способности канала связи на синхронизацию. Метод, предложенный автором диссертации, использует указанное выше свойство четности (нечетности) выходного блока символов (т+1)-канального модуля разделения мажоритарно уплотненного сигнала [31].

Мажоритарное уплотнение, как показано в данной диссертационной работе, позволяет легко осуществить неравную защиту передаваемых символов, т.е. реализовать коды с неравной защитой символов (НЗ-коды). Целесообразность использования таких кодов при передаче количественной информации посредством ко-дово-импульсной модуляции (КИМ) очевидна. Действительно, ошибка в старшем разряде кодового слова КИМ приводит к ошибке, равной половине динамического диапазона передаваемого сообщения, а ошибка в младшем разряде — всего на один квант. В диссертационной работе предлагается [31] использовать для реализации НЗ-кода каскадное мажоритарное уплотнение, рассмотрены конкретные количественные характеристики, получаемые при подобном приоритетном по помехоустойчивости методе передачи.

Большинство реальных радиоканалов передачи цифровой информации не являются двоичными симметричными каналами без памяти (ДСКБП), а являются каналами с пакетными ошибками, в которых ошибки, допускаемые первой решающей схемой приемника, группируются в пакеты (пачки). Это объясняется многими причинами, например, многолучевым распространением радиоволн, наличием импульсных помех и др. В условиях пакетных ошибок использование помехоустойчивых кодов, предназначенных для ДСКБП, оказывается неэффективным. Когда пакета ошибок нет, то их корректирующая способность не нужна, т.к. ошибок вообще нет. Кода появляется пакет ошибок большой плотности - их корректирующей способности недостаточно для исправления этих ошибок. Были разработаны корректирующие коды для каналов с пакетными ошибками, в которых известна математическая модель канала. Однако модели с пакетными ошибками, как правило, нестационарны, т.е. его свойства меняются во времени, и коды для борьбы с пакетными ошибками, ориентированными на конкретную модель канала связи, оказываются неэффективными. Поэтому в настоящее время для борьбы с пакетными ошибками используют перемежители символов (интерливеры). В системах с перемежением ошибок символы на передающей стороне переставляются по некоторому закону - например, записываются в память - прямоугольную матрицу по ее строкам, а на приемной стороне для декодирования счи-тываются из аналогичной матрицы в обратном порядке [37]. Это позволяет превратить пакетные ошибки в псевдонезависимые, и использовать корректирующие коды, предназначенные для ДСКБП.

В данной диссертации показано, что в системе с каскадным мажоритарным уплотнением в силу рекуррентности процедуры разделения пакетные ошибки разрушаются, автоматически превращаясь в независимые, и поэтому перемежитель символов не требуется. Другими словами, помехоустойчивость разделения мажоритарно уплотненного сигнала инвариантна к модели канала связи. В диссертации проведен анализ помехоустойчивости каскадной мажоритарно уплотненной системы для каналов с пакетными ошибками и проведены количественные расчеты помехоустойчивости для тропосферной линии связи [31]. Проведенное компьютерное моделирование подтвердило правильность теоретического анализа [31].

В многоканальной системе передачи цифровой информации определенную проблему представляет согласование скоростей передачи информации от источников, имеющих неодинаковую, особенно некратную, производительность. Автором диссертации предложено для решения этой задачи в системах с каскадным мажоритарным уплотнением использовать перед мажоритарным мультиплексированием многоступенчатую коммутацию источников [31].

Система передачи информации с каскадным мажоритарным уплотнением каналов и отдельные ее элементы (подсистема синхронизации, подсистема согласования производительности уплотняемых источников информации) моделировалась

31], и некоторые результаты этого имитационного моделирования приведены в данной диссертационной работе. Эти результаты показали хорошее совпадение с теорией и экспериментом, проведенном на макете двухкаскадной системы с мажоритарным уплотнением [31].

Далее в диссертационной работе исследуется другое из возможных приложений мажоритарного преобразования - криптографическая защита информации и создание алгоритмов аутентификации пользователя. Вопросы аутентификации пользователя (т.е. установление его подлинности) в информационных системах в настоящее время приобретают все большую актуальность [3,4,15,16,18-21,33-35]. Это объясняется тем, что весь мир стремительно информатизируется, компьютеризация, Интернет и мобильная связь получают все более широкое распространение. Различные злоумышленники на этом фоне пытаются совершать различные действия, в основе которых часто лежат попытки фальсифицировать пользователя. Поэтому в различных информационных системах, использующих многочисленные методы и алгоритмы аутентификации пользователя, наблюдается значительная научно-техническая активность исследователей этой проблемы. Можно указать, что в настоящее время даже в заграничных паспортах вводится биометрическая аутентификация владельца документа.

Все многочисленные методы аутентификации пользователя имеют свои достоинства и недостатки. Главные требования к ним состоят в том, чтобы они были надежны, просты в реализации и имели бы не слишком высокую стоимость. В этой связи большой интерес представляют интерактивные алгоритмы аутентификации, получившие распространение, в частности, в системах мобильной связи [33-35]. Обычно их работа основывается на алгоритмах электронной цифровой подписи [3,4,33-35], в которых в качестве функций хэширования (криптографического сжатия информации) используются определенные криптоалгоритмы, например американский стандарт DES, или отечественный стандарт ГОСТ-28147-89, часто обозначаемый как СКЗД (стандарт криптозащиты данных), или Европейский стандарт IDEA.

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

Один из таких интерактивных алгоритмов, использующих мажоритарное преобразование сигналов при их хэшировании, разработан автором данной диссертационной работы [18,19,20,21] и рассматривается ниже в диссертации. Алгоритм надежен и прост в реализации и его характеристики подтверждены компьютерным моделированием.

1. Введение

Во многих областях современных информационных технологий весьма перспективным оказывается мажоритарное преобразование двоичных сигналов. Мажоритарная логическая функция Maj (•) - это булевская логическая функция, определенная на двоичном наборе своих аргументов (bi, b2, bm), где b, е (0,1) i = l,m [25,26,32]. Это функция абсолютного большинства, если m - нечетное число, т.е. m = 2t + 1, где t = 1,2,. В этом случае она определяется следующим образом

Здесь #ш - число символов bj = 1 в наборе из m двоичных символов, bjG {0,1}.

Если #т = т/2, что может иметь место при m = 2t, t = 1,2,., т.е. когда m - четное число, то допустимо различное доопределение мажоритарной операции. При #m = т/2 можно полагать, что Maj (•) = 1, если #т = т/2, а можно полагать, что Maj (•) = 0, если #m = т/2.

Следует придерживаться всегда одного и того же способа доопределения мажоритарной функции для случая m = 2t, t = 1,2,. Надо заметить, что в случае доопределения функции Maj (•) при m = 2t, строго говоря, она уже не будет мажоритарной, но мы ее по-прежнему будем называть мажоритарной. Более детальные исследования этой функции при ее использовании для преобразования сигналов в информационных радиоэлектронных системах показывают, что нечетная длина входного набора мажоритарной функции, т.е. m = 2t + 1, t = 1,2,., дает лучший эффект, чем четная длина, когда m = 2t. Поэтому целесообразно использовать нечетную длину входного набора, что мы и будем предполагать в дальнейшем, если не будет соответствующих оговорок.

Если перейти от множества двоичных символов bj е {0,1} к множеству символов aj е {±1} с помощью преобразования [26]

1.1) а = 1 - 2Ь (1.2) то тем самым будет осуществлена подстановка а = -1 b = 1. а = 1 <-» b = 0. (1.3.а)

Операция умножения, заданная на множестве {±1}, определяется таблицей 1.1 [23].

Таблица 1.1

X 1 -1

1 1 -1

-1 -1 1

В случае множества bje {0,1} этой операции умножения будет соответствовать операция сложения по модулю два, определяемая таблицей 1.2 [23].

Таблица 1.2 е 0 1

0 0 1

1 1 0

Из сравнения таблицы 1.1 и таблицы 1.2 можно увидеть, что они эквивалентны с учетом подстановки (1.3.а). Поэтому в дальнейшем будем использовать таблицу умножения (Табл. 1.1) или таблицу сложения по модулю два (Табл. 1.2) в зависимости от того, отображаются ли двоичные сигналы в множество двоичных символов а;е{±1} или Ь;е{0,1}.

Если обрабатываемые двоичные символы - это множество bje{0,l}, то мажоритарная операция определяется соотношением (1.1). Если же двоичные символы представлены на множестве aj€{±l}, то эквивалентной операции (1.1) будет операция Sign (•) ("сигнум" - знак), которая определяется следующим образом [23] ч fv^ ^ [ 1, при х > 0 Sign(x) = Sign 2>; = ' F (1.3)

Vi=i J [-1, прих<0

Операция сигнум (1.3) является операцией жесткого ограничения (клиппирова-ния) линейной суммы входного набора из m двоичных символов а^е {±1}. Она переводит произвольный непрерывный аналоговый сигнал S в двоичный биполярный сигнал, как это показано, например, на рис.1.1.

S /

Рис. 1.1. Операция сигнум — операция жесткого ограничения (клиппирования) График функции сигнум, формула (1.3.) представлен на рис. 1.2,а) О

Sign х

Xl

-> X

-1 а)

Sign х х2

О -1

->х б)

Рис.1.2. График функции Sign (х) (а) при х > <0, и Sign (х) б) при х > х2, х < xi

Однако функция сигнум Sign (х), определяемая соотношением (1.3), определена при условии, что ее аргумент х Ф 0. На практике это выполняется во многих случаях, например, когда x(t) - реализация непрерывного случайного процесса. В частности, когда x(t) - реализация случайного гауссовского процесса. Если используется линейное уплотнение m каналов, и m » 1, то в силу центральной предельной теоремы теории вероятностей (теоремы А.М.Ляпунова) линейный уплотненный сигнал будет иметь гауссовское распределение вероятностей, что как раз соответствует указанному выше случаю. Другим примером такого непрерывного аналогового сигнала является речевой сигнал [8]. Как известно, речевые сигналы имеют у-распределение, и при х = 0 в этом распределении имеется 5-функция, соответствующая паузам речевого сигнала. Но поскольку в паузах речи всегда есть посторонние шумы, например, тепловые, то реальные речевые сигналы являются непрерывными, причем х ^ 0, и их распределение часто аппроксимируют суммой двух гауссовских распределений, одно из них - распределение согласных фонем (звуков), другое - гласных [17]. Клипированный речевой сигнал сохраняет хорошую разборчивость речи.

Однако в общем случае аргумент х функции сигнум (1.3) может быть х > 0, х < О, х = 0. В таком случае сигнал S(t), подвергнутый клиппированию с учетом доопределения функции сигнум, будет уже не двоичным, как это имело место на рис. 1.1, а троичным, как это показано на рис. 1.3, т.е. это будет троичный сигнал

Sign 1 Г

-1

Рис. 1.3. Операция Sign (х) при х > х2, х < Х).

График функции Sign (х) для этого случая представлен на рис. 1.2, б). Интервал от X] до х2, на котором переменная х = 0, будем называть зоной стирания. Концы этого интервала, т.е. значения Х] и х2, могут доопределяться по разному, например хе{1,0-1).

S А

1, при X > х2 Sign(x) = « 0, прих,<х<х2 (1.4.а) -1, при х < Xj или

Sign(x)=

1, при x > x2

0,прих1<х<х2 (1.4.6) -1, при х < х, или

1, при х > х2, и с вероятностью р / 2, если х = х2;

Sign(x) = -j 0, при х, < х < х 2, и с вероятностью 1-р, если х, = х = х2; (1.4.в) -1, при х < Xj, и с вероятностью р / 2, если х = х,; где 0 < р < 1

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

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

В дальнейшем для нас будет особенно важен случай m = 3, т.е. случай трехвхо-дового мажоритарного элемента. Записав таблицу истинности мажоритарной функции для этого случая, легко установить, что она имеет вид

Maj (Ьь Ь2, Ь3) = bib2 + bib3 + b2b3 (1.5)

Блок-схема данного мажоритарного элемента представлена на рис. 1.4 [31].

Xl *2 х3

Рис. 1.4. Блок-схема мажоритарного элемента при ш = 3

Мажоритарная операция (1.1) и эквивалентная ей операция (1.3), (1.4) находят широкое применение в радиоэлектронных системах. Можно, например, указать отмеченное выше клиппирование речевых сигналов, мажоритарное декодирование линейных циклических кодов [9]. Однако в настоящей диссертационной работе предлагаются и разрабатываются другие приложения мажоритарной операции и эквивалентной ей операции сигнум в радиоэлектронных системах и информационных технологиях. Центральными в этих системах и технологиях является именно мажоритарное преобразование, что и объединяет их в общий комплекс систем и технологий, которые можно назвать мажоритарными. Их актуальность особенно проявляется в том, что двоичные (троичные) сигналы, формируемые в результате, наиболее удобны при их преобразовании и обработке на элементах современной микроэлектронной техники и компьютерах. В криптографических преобразованиях является важным, что мажоритарная функция (или эквивалентная ей функция сигнум) являются односторонними (однонаправленными функциями). Функция f(x) является односторонней (однонаправленной), если по значению аргумента х легко вычислить значение функции f(x), но по значению функции f(x) невозможно (или вычислительно невозможно) определить значение ее аргумента [2]. Другими словами, односторонняя функция f(x) не имеет обратной функции П'(х). Для мажоритарной функции (операции сигнум) это свойство очевидно: бесконечно много значений аргумента х дают значение f(x) = 1 или f(x)=-l для х > х2 или х < xi соответственно.

Можно указать следующие области и типы радиоэлектронных систем и информационных технологий, где мажоритарная функция (функция сигнум) позволяет получить преимущества по сравнению с традиционными методами:

• многоканальные системы и сети связи, в которых осуществляется уплотнение каналов - цифровых источников информации. Это могут быть, например, телеметрические системы, многоканальные системы речевой связи и т.п.;

• радиорелейные линии, где разнородная цифровая информация уплотняется и ретранслируется;

• тропосферные радиолинии, где разнородная цифровая информация уплотняется и передается по каналу связи с замираниями, которые приводят к пакетированию ошибок;

• помехоустойчивое кодирование двоичных данных;

• преобразование потоков последовательных двоичных данных в параллельные и обратно;

• построение генераторов ключевых потоков (генераторов гаммы) для одно-ключевых криптосистем, использующих аддитивные поточные шифры;

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

Теоретическое и экспериментальное исследование ряда этих радиоэлектронных систем и информационных технологий проводится в данной диссертационной работе.

Выводы по главе 1

1. Рассмотрены свойства мажоритарного преобразования сигналов и эквивалентного мажоритарной функции - функции Сигнум, как с жесткими решениями, так и с решениями со стиранием.

2. Проведена классификация информационных систем и технологий, в которых мажоритарное преобразование является перспективным.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Рощин, Андрей Борисович

Выводы по главе 5

1. Проведено компьютерное моделирование и макетирование двухкаскадного мажоритарного кодека-мультиселека, которое показало хорошее совпадение результатов моделирования и экспериментальных результатов, полученных при исследовании макета, с теоретическими, полученными в диссертации.

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

3. Показано, что при макетировании двухкаскадного кодека-мультиселека были использованы исследования, проведенные в данной диссертационной работе. В частности, предложенная система словной синхронизации была реализована в экспериментальном макете и на практике доказала свою работоспособность.

6. Заключение

6.1. Положения, выносимые на защиту

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

2. Система словной синхронизации при приеме мажоритарно уплотненных сигналов без использования дополнительных синхронизирующих символов.

3. Способ кодирования двоичной информации с приоритетами по помехоустойчивости, использующий каскадное мажоритарное уплотнение.

4. Алгоритм хэширования двоичных последовательностей основанный на использовании мажоритарного преобразования сигналов.

6.2. Преимущество полученных результатов по сравнению с аналогами

По пункту 1 положений выносимых на защиту в качестве прототипа был выбран метод повышения помехоустойчивости каскадных мажоритарно уплотненных сигналов, использующий стирания на промежуточных каскадах разделения [25]. Предлагаемый автором метод повышения помехоустойчивости, использующий дополнительный канал корреляционной обработки и совместную обработку выходных сигналов всех каналов модуля разделения, включая дополнительный, позволяет получить примерно такую же битовую вероятность ошибки при одинаковом битовом отношении сигнал/шум, как и в выбранном прототипе. Однако, стирания приводят к троичному выходному сигналу модуля разделения, что не позволяет использовать этот метод в системе с неполной загрузкой. Предложенный автором метод повышения помехоустойчивости использует жесткие решения в модуле разделения, т.е. формируемый выходной сигнал в таких модулях разделения является двоичным. Это позволяет использовать такие методы разделения в системах с мажоритарным уплотнением и неполной загрузкой. В частности, в диссертации показано, что если использовать модуль уплотнения с тремя входами, то при числе каскадов, равном трем и активности каналов 5-10"2 вероятность ошибки на декодированный символ может быть снижена при прочих равных условиях примерно на 4 порядка. Следовательно, в системах с неполной загрузкой предложенный метод повышения помехоустойчивости существенно более эффективен, чем прототип.

По пункту 2 положений выносимых на защиту в качестве прототипа выбрана система с временным разделением каналов, в которой для блоковой синхронизации в каждое кодовое слово в его начале или конце вводится однотипный символ +1 или -1. На приемной стороне осуществляется накопление принимаемых символов равноотстоящих на блоковую длину кода. Однотипные символы синхронизации при накоплении будут давать всегда одинаковый результат накопления, добавляя всегда в накапливаемую сумму либо +1, либо -1. Информационные символы, находящиеся внутри слова считаются равновероятными и результат их накопления будет случайной величиной с биномиальным распределением и математическим ожиданием, равным 0.

Установив в каждом накопителе определенный порог N, выбираемый из допустимого времени вхождения в синхронизм и вероятности ложной синхронизации осуществляют селекцию синхронизирующих символов и устанавливают границы слова. В методе словной синхронизации мажоритарно уплотненных сигналов, предложенном автором диссертационной работы нет необходимости вводить дополнительные синхросимволы, поскольку для словной синхронизации используется свойство четности (нечетности) выходных сигналов модуля разделения с учетом дополнительного канала корреляционной обработки. Символы четности (нечетности) накапливаются, что позволяет установить правильные границы слова.

Таким образом, предложенный способ, по сравнению с прототипом, позволяет повысить эффективность системы в k+1/k раз, где к — длина информационного кодового слова.

По пункту 3 положений выносимых на защиту в качестве прототипа выбрана система передачи информации с КИМ и равной защитой символов в случае передачи непрерывного аналогового сообщения. В качестве примера в диссертации показано, что при битовом отношении сигнал/шум h* = 4^6 [дБ], длине кодового слова КИМ, равной 11 при использовании в случае мажоритарного уплотнения трех приоритетных групп с числом информационных символов в группе 1; 3; 7, а в качестве канальных сигналов М-последовательностей с длиной 7 выигрыш предложенного метода с неравной защитой символов составляет порядка трех раз при одинаковой дисперсии восстановленного сообщения.

Также проведено сравнение эффективности использования мажоритарного уплотнения, приоритетного по помехоустойчивости со случаем линейных кодов, также приоритетных по помехоустойчивости при одинаковой избыточности кода, одинаковой блоковой длине слова и том же числе приоритетных групп. Показано, что при малых отношениях сигнал/шум hj; линейный код в рассмотренном варианте его построения дает несколько большую величину выигрыша, однако при hj; >3 рассмотренный вариант мажоритарного уплотнения выигрывает у линейного кода, а асимптотически оба варианта передачи незначительно отличаются друг от друга.

По пункту 4 положений выносимых на защиту в качестве прототипов были выбраны американский криптоалгоритм DES [41] и отечественный алгоритм ГОСТ-28147-89 [40], которые работают в режиме сцепления блоков и позволяют осуществить криптографическое сжатие - хэширование. Предложенный автором алгоритм хэширования, основанный на криптоалгоритме "Гамма" и использующий мажоритарное преобразование сигналов при одинаковой длине ключа обеспечивает быстродействие по сравнению с алгоритмом DES приблизительно в 5 раз больше, а поскольку алгоритм ГОСТ-28147-89 имеет существенно более низкое быстродействие, чем DES [43], то выигрыш в быстродействии предлагаемого алгоритма хэширования будет еще больше.

Список литературы диссертационного исследования кандидат технических наук Рощин, Андрей Борисович, 2004 год

1. Шеннон К.Э. Теория связи в секретных системах./ Работы по теории информации и кибернетике. - М.: ИЛ.,1963,с.ЗЗЗ-402.

2. Месси Л.Дж. Введение в современную криптологию М.:ТИИЭР, 1988, т.76, №5, с.24 - 42.

3. Мельников Ю.Н. Электронная цифровая подпись. Возможности защиты. Конфидент, №6, 1995, с.35 - 49.

4. Okamoto T.,Fujisaki Е. On Comparison of Practical Digital Signature Schemes/NTT Review, 1993, vol.5, №1, p.75 81.

5. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: "Энергия", 1974

6. Соболь И.М. Численные методы Монте-Карло-М.: Наука, 1973

7. Программа для ЭВМ "Система защиты данных "Гамма-3". Свидетельство об официальной регистрации программы для ЭВМ №940477/ Правообладатель МАИ, авт. Волков С.С., Назаров О.П.и др., РосАПО,8.11.94.

8. Величкин А.И. Теория дискретной передачи непрерывных сообщений М.: Сов.радио, 1970

9. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. М.: Связь, 1968

10. Левин Б.Р. Теоретические основы статистической радиотехники. Кн.1 -М.: Сов.радио, 1969

11. Тепляков И.М., Калашников И.Д., Рощин Б.В. Радиолинии космических систем передачи информации М.: Сов.радио, 1975

12. Тепляков И.М., Рощин Б.В., Фомин А.И., Вейцель В.А. Радиосистемы передачи информации. Радио и связь, 1982

13. Холл М. Комбинаторика М.: Мир, 1970

14. Хворостенко Н.П. Статистическая теория демодуляции дискретных сигналов -М.: Связь, 1968

15. Петраков А.П., Лагутин B.C. Защита абонентского телетрафика. М.: Радио и связь, 2001

16. Елизаров Т.Ю., Казарин О.В., Рубашкин В.Н. Сжатие хэширование сообщений в спутниковой телеохране. - М.: РИО МТУ СИ, 1998

17. Хургин Я.И. Ну и что? М.: Молодая гвардия, 1970

18. Назаров О.П., Рощин А.Б., Козлова М.В. Аутентификация субъектов доступа в информационных системах с использованием интерактивных алгоритмов. -Безопасность информационных технологий, №2, 1999, с.99 103

19. Рощин А.Б. Интерактивный алгоритм аутентификации пользователя в системе/ Научно-техническая конференция студентов и аспирантов ВУЗов России. Тезисы докладов, том 1 — М.: МЭИ, 1998 с.198

20. Назаров О.П., Рощин А.Б. Система опознавания летательных аппаратов ("Свой-чужой") / Ракетные и аэрокосмические системы, МАИ, 2000 с.61-63

21. Калашников И.Д., Степанов B.C., Чуркин А.В. Адаптивные системы сбора и передачи информации — М.: Энергия, 1975

22. Рощин Б.В. Структура сигналов в многоканальных системах передачи информации летательных аппаратов. М.: МАИ, 1989

23. Симонов С.В. Биометрические устройства в подсистемах аутентификации -Конфидент. Защита информации. № 4-5, 2000, с.56-59

24. Гридин В.Н., Мазепа Р.Б., Рощин Б.В. Мажоритарное уплотнение и кодирование двоичных сигналов. — М.: Наука, 2001

25. Уздемир А.П. Корреляционные функции комбинированных последовательностей. Радиотехника и электроника, №3,1972, с.499-510.

26. Питерсон У., Велдон У. Коды, исправляющие ошибки / пер. с англ. под ред. Добрушина P.JL и Самойленко С.И. -М.: Мир, 1976

27. Титсворт. Применение булевой функции для построения многоканальной телеметрической системы Зарубежная радиоэлектроника, 1964, №8, с.33-39.

28. Устройство для уплотнения каналов многоканальной системы передачи информации. А.с. 642859 СССР: М.Кл2. Н04 13/00/ Калашников И.Д., Карлов А.А., Рощин Б.В., Федотов В.А., Шейнин Г.В.; Бюллетень №2, 1979.

29. Ипатов В.П., Коломенский Ю.Н., Шабалин Р.Н. К вопросу о приеме мажоритарно уплотненных сигналов. // Радиотехника и электротехника, т.20, 1975, №4, с.834-838

30. Дертоузос М. Пороговая логика / Пер. с англ. под ред. Варшавского В.И. М.: Мир, 1967

31. Рощин Б.В., Назаров О.П. Аутентификация информации в радиоэлектронных системах. М.: МАИ, 2000

32. Андрианов В.И., Соколов А.В. Средства мобильной связи. СПБ: БХВ-Санкт-Петербург, 1999

33. Громаков Ю.А. Стандарты и системы подвижной радиосвязи. М.: ЭКО-ТРЕНДЗ, 1998

34. Тепляков И.М. Радиотелеметрия. М.: Сов.радио, 1966

35. Кларк Дж.,мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи / Пер. с англ. под ред. Цыбакова Б.С. М.: Радио и связь, 1987

36. ГОСТ 28147-89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

37. ГОСТ Р34.10-94. Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе ассиметричного криптографического алгоритма.

38. ГОСТ 34.11-94. Информационная технология. Криптографическая защита информации. Функция хэширования.

39. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.: "Кудиц-образ", 2001

40. Герасименко В.А., Малюк А.А. Основы защиты информации. М.: МИФИ, 1997

41. Спесивцев А.В., Вегнер В.А. и др. Защита информации в персональных ЭВМ. М.: Радио и связь, 1992

42. Львовский Е.Н. Статистические методы построения эмпирических формул. -М.: Высшая школа, 1988

43. Masnick В., Wolf J. On linear unequal error protection codes IEEE Trans. Inform. Theory, 1967, vol.13, №4, p.600-607

44. Бояринов И.М. Помехоустойчивое кодирование числовой информации. М.: Наука, 1983

45. Зиновьев В.А., Зяблов В.В. Коды с неравной защитой информационных символов Проблемы передачи информации, 1979, т. 15, №3, с.50-60

46. Дынькин В.Н., Тогонидзе В.А. Циклические коды с неравной защитой символов Проблемы передачи информации, 1976, т.12, №1, с.24-28