Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини

Иванова, Ирина Владимировна

Автоматизация и управление технологическими процессами и производствами (по отраслям)

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини

доктора технических наук: Иванова, Ирина Владимировна
город: Санкт-Петербург
год: 2005
специальность ВАК РФ: 05.13.06
цена: 450 рублей

Диссертация по информатике, вычислительной технике и управлению на тему «Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини»

Автореферат диссертации по теме "Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини"

На правах рукописи

ИВАНОВА ИРИНА ВЛАДИМИРОВНА

НАУЧНЫЕ ОСНОВЫ СОЗДАНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ КОДИРОВАНИЯ ДАННЫХ В КОНЕЧНЫХ ПОЛЯХ ГАЛУА МЕТОДАМИ ДИСКРЕТНОЙ АЛГЕБРЫ КЛИНИ

Специальность 05.13.06 — Автоматизация и управление технологическими

процессами и производствами (промышленность)

АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора технических наук

Санкт-Петербург-2005

Работа выполнена на кафедре компьютерных технологий и программного обеспечения Северо-Западного государственного заочного технического университета (СЗТУ).

Официальные оппоненты:

Ведущая организация: ОАО «НПО» Прибор»

Защита состоится 27 декабря 2005 г. в 14 часов на заседании диссертационного совета Д212.244.01 при Северо-Западном государственном заочном техническом университете, 191186, Санкт-Петербург, ул. Миллионная, д.5

С диссертацией можно ознакомиться в библиотеке Северо-Западного государственного заочного технического университета. Автореферат разослан 25 ноября 2005 г.

Ученый секретарь

- заслуженный деятель науки РФ, доктор технических наук, профессор Яковлев Валентин Васильевич;

- доктор технических наук, профессор Крук Евгений Аврамович,

- доктор технических наук, профессор Уткин Лев Владимирович.

диссертационного совета

Максаров В.В.

Общая характеристика работы

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

кодирования/декодирования и разработку «быстрых» алгоритмов автоматического введения защитных кодов в трактах передачи информации.

Актуальность темы.

Исследования проводились в рамках государственных программ и координационных планов, по ведомственным тематическим заказам (государственная регистрация отчетов по НИР за №№ 01850013661, 01870067179, 01860107705), в соответствии с комплексной целевой программой «Российские верфи», в научно-исследовательских проектных разработках Технологического института энергетических обследований, диагностики и неразрушающего контроля «ВЕМО», что является формальным признаком актуальности.

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

В последние десятилетия исследования по проблемам быстрого кодирования/декодирования стали приоритетными. Приоритет исследований обусловлен высоким уровнем развития микроэлектроники, аппаратных и программных средств, обеспечивающих обмен информацией. Объективным следствием развития технических средств явились и функциональные ограничения применяемых методов конечной алгебры, многозначной логики и традиционной идеологии проектирования цифровой микроэлектронной аппаратуры на базе многозначных элементов. Известны изобретательские решения отдельных задач помехозащищенности, они не снимают проблемы в целом, но с очевидностью указывают на необходимость пересмотреть научные основы организации процедур кодирования/декодирования информации в реальном времени.

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

Объект исследования - средства защиты информации от помех в автоматизированных системах управления технологическими процессами.

Для достижения цели представлялось необходимым решить следующие

основные задачи:

1. Системный анализ требований к информационному обеспечению автоматизированной системы управления технологическим процессом (АСУ ТП), помехоустойчивая запись/воспроизведение цифровых данных.

2. Переход к единому представлению цифровых данных в информационной системе (ИС) АСУ ТП с целью обеспечения помехозащищенности, анализ методов и структур кодирования/декодирования.

3. Разработка программно-аппаратных средств для выполнения операций и процедур кодирования и декодирования кодов над конечными полями.

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

5. Обеспечение работы АСУ ТП в реальном масштабе времени, разработка безрекуррентных процедур вычисления особых продолжений ганкелевых (теплицевых) матриц и синдромов и орбитально-табличных методов решения степенных уравнений, а также систем линейных и линейно-нелинейных уравнений над полями Галуа.

6. Разработка средств защиты информации от помех в ИС АСУ ТП на основе микропроцессоров, функциональных расширителей для кодеков и декодеров.

7. Создание концептуальных основ построения современных ИС АСУ ТП на основе анализа регулярных форм (в том числе предлагаемых) для многозначных функций, а также полиномиальных представлений, в том числе в троичной и четырехзначной алгебре логики.

8. Разработка научных основ создания автоматизированных систем кодирования/декодирования данных, использующих асимметричные алгебры многозначной логики, включая малоуровневые представления.

9. Разработка методов анализа и синтеза ИС АСУ ТП нового поколения.

Научная новизна полученных результатов состоит в системном

аналитическом описании процедур кодирования/декодирования,

абстрагировании и адекватности интерпретаций и реализации результатов

аналитических преобразований. Наиболее существенные научные результаты, полученные автором следующие:

1. Способ частотно-временного (гибридного) декодирования цифровой информации АСУ ТП.

2. Комплекс математических моделей, включающий:

- безрекуррентный способ продолжения синдрома для ускорения процесса декодирования;

— решение степенных уравнений и систем уравнений в полях Галуа для повышения качества декодирования;

— решение многозначных (троичных и четырехзначных) логических уравнений и их систем для обеспечения анализа и синтеза ИС АСУ ТП нового поколения.

3. Концептуальные основы построения современных информационных систем АСУ технологических процессов, в том числе:

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

— асимметричные алгебры с двумя бинарными операциями: асимметричные кольца, асимметричные тела, асимметричные поля и их разновидности;

- обобщенные регулярные формы в асимметричных алгебрах логики и практические примеры аналитических представлений многозначных функций в асимметричных алгебрах

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

Достоверность научных положений, выводов и рекомендаций

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

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

принципиальных, схемотехнических и конструктивных решений ряда задач помехоустойчивого кодирования/декодирования, в их перечень входят:

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

2. Разработанные алгоритмы кодирования и декодирования по особым продолжениям обеспечивают автоматическое выполнение процедур защиты информации в АСУ ТП от помех.

3. Разработанный алгебраический аппарат (многозначная логика) создает основу для построения интегральных схем для практической реализации быстрых алгоритмов.

4. Предложенный способ построения поля Галуа обеспечивает наглядную интерпретацию процедур кодирования/декодирования.

5. Аналитические методы описания- структур многозначной логики могут быть использованы при анализе функциональных свойств и схемотехнических решений вычислительных средств для ИС АСУ ТП.

На защиту выносится комплексное решение проблемы обеспечения достоверности информационного обеспечения систем управления процессами и производствами на основе теоретических и технических аспектов создания систем кодирования /декодирования и включающее:

1. Концептуальную модель системного метода построения кодов Рида-Соломона в полях Галуа.

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

3. Теоретические основы кодирования/декодирования с использованием кодов Рида-Соломона над полем Галуа ОР(2г), позволяющие снизить погрешность ошибок при канальном декодировании в 2<т*1)(я~г) раза.

4. Математические методы решения степенных уравнений (и=3,4,5), систем линейных и линейно-нелинейных уравнений над ОР(2г), возникающих при

исправлении стираний, ошибок и стираний.

5. Новые алгебры логики и методы решения многозначных логических уравнений и их систем.

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

7. Методы анализа и синтеза многозначных схем с обратными связями, позволяющих простые реализации средствами микроэлектроники.

Реализация результатов работы. Разработанный метод декодирования кодов Рида-Соломона по особым продолжениям расширенных ганкелевых (теплицевых) матриц над полями Галуа, позволяющий безрекуррентное вычисление синдрома ошибок внедрен в рамках хоздоговорной научно-исследовательской работы СЗПИ (номера Государственной регистрации отчетов но хоздоговорным НИР; 01850013661, 01870067179, 01860107705), что подтверждено соответствующим актом использования результатов диссертационной работы для экспресс-классификации многомерных случайных сигналов при практической реализации в научно-исследовательских проектных разработках, предприятиями различного профиля при модернизации существующих систем автоматического управления, кибернетики, радиотехники, информатики, аналого-цифровой измерительной техники: Технологическим институтом энергетических обследований, диагностики и неразрушающего контроля «ВЕМО»; НИОКР ОАО «Авангард»; НИОКР, проводимых ООО «ЭлектроРадиоАвтоматики-Р» и др., в соответствии с комплексной целевой программой «Российские верфи». Тематика диссертационной работы используется в учебном процессе высших и средних учебных заведений в курсах «Информатика», «Дискретная математика», «Математическая логика и теория алгоритмов», «Теория автоматов», «Схемотехника», «Эксплуатация средств вычислительной техники» при создании учебно-методических пособий.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на 6-й международной научно-практической

конференции «Современные информационные и электронные технологии» (Одесса, 23-27 мая 2005г.); на всесоюзной конференции «Микропроцессорные средства локальной автоматики» - Гродно,' 1989г.; на республиканском семинаре В СОИ, Ужгород, 1984г; на всесоюзной конференции «Применение МП комплектов БИС при разработке радиоэлектронной аппаратуры», Ленинград, 1983 г. и семи научно-технических конференциях и семинарах.

Публикации. По теме диссертационной работы опубликовано две монографии (одна в соавторстве), двадцать четыре статьи, шесть из них в изданиях, рецензируемых и рекомендованных перечнем ВАК.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, приложения и списка литературы. Общий объем работы составляет 276 страниц машинописного текста, 46 таблиц и 24 рисунка. Список литературы содержит 1?0 наименований.

Краткое содержание работы

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

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

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

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

Наиболее сложным применением АСУ ТП является ее использование в качестве одного из элементов информационно-управляющей системы для оперативного управления производственным предприятием (рис. 1). В структуре этой системы АСУ играет важную, но до некоторой степени вспомогательную роль. Функции руководства на таких больших предприятиях, какими являются нефтеперерабатывающие или химические комплексы, за последние десятилетия сильно усложнились. Они будут становиться еще сложнее по мере роста количества доступной информации, роста объемов производства, по мере постоянного увеличения спроса на продукцию и усиления конкуренции в международном масштабе. По этим причинам связи между различными подразделениями предприятий также становятся все более сложными. С появлением новых элементов в деловой области или в технологии проблема обостряется. ИС АСУ ТП выполняет, в основном, функции сбора данных о процессе и управлении в соответствии с поставленными целями и алгоритмами управления. В связи с этим в работе исследованы проблемы организации и синтеза кодеков в системах автоматизированной обработки данных. Обоснован переход к единому представлению цифровых данных в ИС АСУ ТП с целью обеспечения помехозащищенности. Анализ тенденций развития методов декодирования приводит к определенным требованиям к кодекам: работа в реальном режиме времени и выполнение вычислений в полях Галуа йЩд).

В диссертационной работе проанализированы наиболее широко применяемые типы кодов, виды и методы декодирования, исходя из основных понятий и классификаций дискретных преобразований, выбрано поле Галуа, в котором будут производиться основные преобразования; проанализированы известные методы декодирования кодов Рида-Соломона; дан обзор применений кодов РС, как кодов, корректирующих ошибки в независимых группах разрядов

Служба координации и экономики

Заявки на сырье и планы, основанные на

прогнозах относительно готовой продукции

Текущее состояние

Запасы в резурв. парке Стоимость сырья

Тенденции, стимулы

Предлагаемый план

Предлагаемые смеси

Имеющиеся запасы

Переч. иеобх. продуктов

Нормали на продукцию

Стоимость продукции ^ Оконч. план на неделю

Окончательные смеси

Лаборатория

Анализ сырья, полупродуктов, готовой продукции

Техническая служба

Снижение затрат, усовершенствов. процесса, улучшение качества, увеличение выпуска, помощь производству, эффективное использование оборудования

Отклонения от норм

Лабораторн. отчеты

Результаты контроля

Результаты анализов

.Текущее состояние

Тенденции, стимулы Лаборат. отчеты

Авизном. исследов.

Мощность оборуд.

Технологии, схема

Имеющиеся ёмкости

Модели установок

Форм, хим. технолог.

Потреби, в ремонте

Изменения в произв.

ЭВМ

Банк данных

Останов, оборуд.

Отказы приборов. ЭФФект- оборуд.

График ремонтов ,

Отгрузки

Поступления

Заказы

Стоим-ть сырья

Запасы, продуты^

Запасы в резерв.

Накопление мес.

Отгрузка мес.

Запасы химикато^ Газ.топливо-услу^

Температуры

Давления

Расходы

Анализы на потоке

Уровни в резерв.

Смена режимов

Изм.технолог.схемь

Отклонив, данные

Текущее состояние

ЛаСюрат .отчеты

Недельные планы

Контр, цифры

Нормали

Отч. о смешении

Ремонтная служба

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

Учет запасов

Анализ работы

резер^

Тендснцнн.стимул^

Бухгалтерия

Счетоводство, ревизии, касса, страхование, финансовые отчеты

Производств, служба

Производство продукции для передачи на другие участки,

другие предприятия и для продажи

Рис.1. Информационная система для оперативного управления производственным процессом

слова запоминающего устройства, определена необходимость неоднократного перемежения, каскадирования и применения ПЛМ. Декодер исправляет стирания и ошибки (которые являются элементами поля СР(2Г), т.е. состоят из г бит), если их число не нарушает условия ¿/<2т+г+1 (где (I - кодовое расстояние кода; т - число стираний; V - число ошибок. Повысить кодовое расстояние с/ кода можно при каскадировании (рис.2). Символы внешнего и внутреннего кодов могут выбираться из разных алфавитов — например, из поля СД2) и некоторого его расширения СЩТ). В этой части работы выбраны обобщенные структуры кодеров и декодеров для РС-кодов и показано, что в качестве кодов в обоих каскадах целесообразно использовать коды РС над полем ОЦТ). Причем кодирование и декодирование возможно во временной и частотной областях. Кодирование во временной области осуществляется с помощью порождающей матрицы или порождающего полинома.

Сообщение й

Кодер V

Внешний Интерливер Внутренний 1 Канальный

кодер 1 модулятор

1.-

Помехи

1 I 111 1 1

г- V*

Канальный 1 -4» Внутренний

демодулятор 1 1 1 декодер

Декодер

Схема опознания ошибочного символа

Деинтерливер

Внешний декодер

- Метка стирания

Сообщение -►

Рис. 2. Структура системы записи-воспроизведения дискретной информации.

Особенность временного декодирования - раздельное вычисление позиций и величин ошибок. Для этого приходится решать: степенное уравнение локаторов и систему линейных уравнений относительно величин стираний.

Частотное декодирование не требует решения указанных уравнений, так как позволяет непосредственно найти спектр конфигурации ошибок, вычисляемый как продолжение синдрома (ганкелевой матрицы). Недостаток данного метода -невозможность полного косвенного контроля выделенного сообщения. Исследования показали, что наиболее перспективна смешанная реализация кодека: временной кодер - гибридный декодер (рис.3).

Рис.3. Гибридная (частотно-временная) структура декодеров

В настоящее время анализ методики построения алгебр логик применительно к задачам синтеза схем сводился к построению регулярных форм. Если к—рг, где риг соответственно простое и натуральное, а к - значность алгебры логики, то функция может быть представлена полиномом над полем вНТ).

Так в литературе для случая к=2, т.е. двоичной алгебры логики, введено обозначение

ЗС1,у—•//(*) = *° =

X , при X = I х , при x^i

1 , при х=а О , при х*=о.

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

Составим пару логических функций:

а )Fn = х°" Л ...Л хр Л... Л 42 Л х^; б) = V... V х* V... V хр V *,р1, р, = Ш,.

В диссертационной работе к уже известным совершенным каноническим формам совершенной дизъюнктивной нормальной форме (СДНФ) и совершенной конъюнктивной нормальной форме (СКНФ), для двоичной алгебры логики, добавлены канонические формы, не имеющие до сих пор специального названия.

Дадим название новым совершенным каноническим формам:

/= е Ft= е (З)

/е{1} /е{1)

или /= ф Fj— © <8>... »Xj*1 (4)

/€{1} /е{1>

- совершенная квазиполиномиальная нормальная форма (Ск-ПНФ);

/= , ~, ~ # vfe1 V...vxfl /е{ 0} /б{0}

- совершенная специальная нормальная форма (ССНФ),

где обозначения / € {1} и / 6 {0} означают, что берутся только те комбинации, на которых заданная функция f принимает значение соответственно 1 или 0.

Правило построения СДНФ и Ск-ПНФ: 1. Составить конъюнкции (произведения) из аргументов для тех их комбинаций, на которых функция /обращается в единицу; при этом если аргумент входит в

данную комбинацию как 0, то в конъюнкцию вводится инверсия щ, а если как 1 - то .

2. Полученные конъюнкции (произведения) соединяются знаком V (для СДНФ) или © (для Ск-ПНФ).

Правило построения СКНФ и ССНФ: 1. Составить дизъюнкцию для тех комбинаций, на которых функция / обращается в нуль; при этом если аргумент XI входит в данную комбинацию как

1, то в дизъюнкцию вводится инверсия я,-, а если как 0 - то X;.

2. Полученные дизъюнкции соединяются знаком Л (для СКНФ) или ~ (для ССНФ).

В работе рассмотрены канонические формы с парой бинарных операций, а также другие канонические формы, при которых функции У*} и Ф,- выражаются через бинарную и унарную операции, например, через импликацию и инверсию (так как а-^Ь — аЧЬ) или запрет и инверсию (так как аЧЬ — а V Ь ). Могут быть построены регулярные формы и на базе одной бинарной операции: Шеффера или Пирса. Так, однократно применив правило де Моргана к СДНФ или СКНФ, можно получить логическое выражение в базисе {И-НЕ} или {ИЛИ-НЕ}. Для построения регулярных форм в ¿-значной алгебре логики; характеристической

функции (ХФ) х°(1) в двоичном случае соответствует большая ХФ в многозначной алгебре логики

х*_и=Л-(*)=*(0 =

А-1,при * = / О , при x^i .

По аналогии с £=2 введены функции:

а) F„ = х(У Ах(„аЛГ^Л...Лx¡°>\k = val;

б)ф„ = я) vхп-Гl} v • • •v*iPl>.* = val>Р/ =

в которых символы V и Л понимаются соответственно как £-значные конъюнкция и дизъюнкция, т.е. как функции min и Мах.

Введем бинарные А-значные операции © и * со свойствами: 09u = ö90 = a и {к-\)*а = а*(к-\) = а.

Можно показать, что каждая из операций © и * может быть выбрана к{к — 1) способами. Так, при к=2 имеем 2 способа, при к=3 - уже 12 способов, при £=4 существует уже 36 способов. Как и в двоичном случае, мы выбираем 4 операции:

Л-значная дизъюнкция V (Мах) ¿-значная конъюнкция Л (min)

сумма © по модулю к к- значная операция ~

для © ; для * ,

где ~ определяется следующим соотношением а ~Ъ = а Ф ¿Ф 1 , по модулю к.

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

Функция следующего вида называется полиномом

/ = *"-1 у = Л /(хьх2,...,х„)~ £ а,- П х-, / = О У = 1

где 2 и П соответственно символы суммы и произведения со свойствами, зависящими от к (значности логики); л-число аргументов; щ - константы, такие,

что еАГ\{0}, Xj€K, 1 — \,2,...,к-\, х'— х--х{1 раз),

причем знак операции умножения опущен.

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

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

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

коэффициентов с,-, / = 0,1 ,...,М — к" — 1.

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

В работе рассмотрены известные и предложены новые регулярные формы в конечнозначной алгебре логики (дискретной алгебре Клини).

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

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

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

Кроме того, выбор представления элементов расширенного конечного поля ОХ 2Г) позволяет упростить правила выполнения операций над

элементами поля. Наибольшее распространение получили следующие способы представления элементов поля GFfT): в виде десятичных номеров -чисел N (модифицированных логарифмов); степеней а.' примитивного элемента а; логарифмов log(a') по основанию а функций Зеха (обычных и модифицированных); двоичных векторов; полиномов; разложения по нормальному базису.

В работе рассмотрено несколько типов дискретных преобразований:

1. Фурье над полем Галуа или преобразование (многочлен) Мэттсона-Соломона (ФМС преобразование), которое определяется с помощью матрицы Ф=[<»'■'], где для наглядности строки и столбцы пронумерованы переменными г и j.

2. Дискретное преобразование с помощью матриц Ганкеля-Теплица (ГТ), определяемое матрицей [а'^Кразмера ихп).

Если ФМС преобразование заданного порядка и, существует не во всяком поле Галуа, то ГТ преобразование существует в любом поле Галуа, а ядро а этого преобразования суть примитивный элемент поля.

ГТ преобразование позволяет не только строить простые и быстрые схемы для нахождения произведения элементов поля Галуа GF{2Г), но также вычислять полевые свертки. Используя циклические Гц и Тц матрицы, т.е. ганкелевы и теплицевы циркулянты возможно вычисление циклической свертки.

Известно, что задача исправления ошибок в теории помехоустойчивого кодирования приводит к необходимости решать степенные уравнения в полях Галуа. В диссертационной работе развиты табличные методы решения данных уравнений, рассмотрены методы сокращения объема памяти, хранящей значения корней путем перехода к орбитальным представлениям с использованием понятия цикло-классов сопряженных элементов. Табличные методы решения уравнений основаны на их преобразовании к каноническим формам. В табл.1 приведены формулы для

приведения уравнений степени п—4,5 к каноническому виду над полем

Ряд задач в теории помехоустойчивого кодирования, например, по восстановлению стираний приводит к необходимости решать системы линейных уравнений над тем или иным алгебраическим полем. В работе предложен метод решения системы из А линейных уравнений АХ=8 (где X — вектор-столбец неизвестных переменных; Б — вектор-столбец известных синдромов - свободных членов) с матрицей Ван-дер-Монда (А): такая система возникает при декодировании.

С целью сокращения вычислительного процесса введены частные

симметрические функций а^Р.сгу^, связанные с известными элементарными

симметрическими функциями (полными) соотношением а у = а® + а^' ^, где о у — сумма всех произведений, каждое из которых содержит ] сомножителей

аI с несовпадающими индексами; с/р — частная симметрическая функция, полученная из полной функция _/-го порядка Оу, исключением слагаемых,

содержащих элемент а,-; а^' -1 — соответственно, не содержащих элемент а-. Тогда для

й Д А уГ, }

здесь Вь - определитель Ван-дер-Монда, но порядка й-1, а Д - определитель Ван-дер-Монда порядка А; для (7/7(2г),

Таблица 1

Формулы для приведения уравнений степени л=2...5 к каноническому виду над полем

п Уравнение Преобразование Канонический вид Параметры

2 Х2+АХ+В = 0 х — Аг г2 +г+£>=0 о=в/а2

3 з? + Ах2+Вх+С = 0 х^А+г^ + В)^2 23+2 + £ = 0 Г-... ¿В+С

х = В^2+2(А + В1/2) 23 + 22+£ = 0 (А2 + В)312

4 л4+0Х + Е = О Х = 291/3 г4 +2 + (р = 0 1р = еГ4/3

х4 + Ах3 + Вх2 + Сх+ £> = 0 х=В/А+Аг 24 + 23 +Ц2 + У = 0 ц = (В2+ЛС)/Л4 \ = (В4 +АЪСВ + А4П)!А*

х = (С/АУ2+1/у См. 1) а3 = 0+(ВС)/А + (С/А)2 а2=В + (АС)!/2,а1 = А Ех=а[[ат11а^ = аз/а2

'^ЗУ4 + а2у2 +«17+1 = 0 у = 2(а2/а3)1/2 24+22+£12 + £22 = 0

5 х5 + Ах4 + Вх3 + Сх2 + Их+Е = 0 х = С/В + 1/м> См. 2) а = р/а,Ь = 5/а,с = у/а,^=1/а а = Х5-МА.4 + йХ+Е,Х=С/В Р = Х4+0.+Ду = Х + Л Д = а4+с,£> = а2Ь + ас + г/

2:>и>5 + см4 + ЪУ? + ст + <1 = 0 См. 3)

3),54-,й2+л/+е=о 25 + 22 + 02 + е = О

Вычисление элементарных симметрических функций производится по рекуррентной формуле:

У У + -1 > )■

Требуемое число операций как сложений, так и умножений равно «

0.5Л2.

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

В работе предложено декодирование кодов Рида-Соломона на основе вычисления особых продолжений ганкелевых (теплицевых) матриц и синдромов. В теории помехоустойчивого кодирования оперирование с ганкелевыми (или теплицевыми) матрицами осуществляется при составлении системы линейных уравнений, называемых синдромными и в векторно-матричной форме записываемых в виде Ата = Ь; Аг5 = Ь,где Ат, Аг -квадратные матрицы порядка и, соответственно теплицева и ганкелева; о=[о2 аз ■•■сти]' ~ вектор-столбец высоты и неизвестных переменных;

Ь = \Ьф2--.Ь„^ — вектор-столбец высоты и известных величин (параметров), причем вектор Ь является продолжением матрицы А, то есть У = (ап+\ап+2-~а2пУ-> ® — обращенный вектор <т .

Матрица А полностью определена набором коэффициентов А = (а! <32 ...<Я2л)- Задача состоит в нахождении особых.продолжений матриц Апп+\,Ап, не изменяющих ранг матрицы Лпп. Отыскание особого продолжения ганкелевой матрицы сводится к нахождению полинома

о(г) = хт + Ст1гг_1 + 022г-2 +... + + аг, где г - ранг матрицы Ап „+1. Для нахождения а (г) могут использоваться

следующие методы: прямой метод вычисления определителя; метод Берлекэмпа-Месси; алгоритм Евклида вычисления наибольшего общего делителя (НОД)

полиномов гт и А(г) по тоё2т, либо гт -1 и А(г) по той гт, где т = 2«,

/=2л _ . ¿(*> = £ а^2"-'. /=1

Алгоритм прерывается в момент, когда степень очередного остатка Я станет менее ^ • В этом случае а(г) находятся как рекуррентная

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

В данной работе показано, что особые продолжения расширенных

ганкелевых и теплицевых матриц (прямоугольных форм) могут быть найдены

без рекуррентных процедур. Этот метод основан на алгоритме Евклида,

аппроксимации Падэ и учитывает взаимосвязь между бесконечными

ганкелевыми матрицами и дробно-рациональными функциями. Так по

остатку Я(г) и известному полиному А (г) может быть рассчитан полином

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

й2л+у,у = 1,2,... продолжения расширенной ганкелевой матрицы

—■ 2» — — а = Л г +А, остаток Р;

а = Р г + А, остаток Л,

где Р(г) обращенный полином для суммы старших членов представления

А(г)а(г) = Р(г) + ()(2) + ]!{(2) можно рассматривать как остаток, а точнее как

полу-НОД для полиномов 2 и А(г).

Декодирование РС кода в частотной области состоит из следующих этапов: преобразование ФМС; нахождение полинома локаторов; рекуррентное продолжение синдрома; коррекция.

Второй этап упрощается (по сравнению с временным декодированием), так как отпадает надобность в полном решении ключевого уравнения

5(г)а(г) = ю(г), тос! гт, а достаточно найти лишь полином локаторов о(г).

Третий этап сводится к вычислению спектра ошибок.

Используя смешанный кодек для РС кодов: временной кодер - гибридный (частотно-временной) декодер можно для вычисления синдрома использовать быстрое ФМС преобразование, при этом порождающий полином g(z) составляется в симметричной форме. Синдром 5 вычисляется либо по методу Горнера, либо методами, аналогичными быстрым алгоритмам усеченного ФМС-преобразования, основанными на факторизации матриц и которая осуществляется следующим образом: пусть и = и наД полем СД^=2') существуют

ФМС преобразования соответствующих длин, тогда

ф„=Р'П4'М''>, (6)

/=1

где

4° = ЕМ. ® ; Ф<?> = ЕМ. ® ФИ/ ® Ещ;

М1 = "/+1 "¡+2—"г+1 .,.«м;

Ий »1, »

¿V, = ¿4 = ага8[1)0 ((П,.),^(Г1,),.. .,£>^(7!,)];

(П/> = с11аВ{[е(л1)]°,[е(л/)]1.....[е^,)]"'-1};

щ = «М е(т|,-) = ел. =

Р - матрица разрядно-инверсных перестановок;

® - символ кронекеровского произведения.

Гибридное декодирование РС кода состоит из следующих этапов: вычисление т-точечного ФМС преобразования; нахождение полинома локаторов; рекуррентное продолжение синдрома; обратное ФМС преобразование; коррекция.

В третьей главе рассматриваются обобщенные регулярные формы в асимметричных алгебрах логики. Рассматриваются малоуровневые регулярные

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

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

Удается исключить и унарные операции, если последние представимы с помощью бинарных операций. В частности, это осуществимо, если используемая алгебра - поле Галуа GF(' к = дг ), где д - простое число, г -произвольное натуральное число. В этом случае любая функция представима в виде некоторого полинома.

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

N N N

/,(Х) = © ^ = © Ц, * /;) = © 7=0 7=0 у=0

ав]*

6 4*)

;'=0

(7)

Далее, можно использовать одну и ту же операцию, т.е. принять О = * и перейти к

N N N

Ш) = © = © К; */,) = ©

7=0 7=0 7=0

а*7 *

* Х1 и=0

** р /оЛ = © * (8) 7=0;=0

Ю А

где и' — йу, арность операции * увеличена на единицу.

Форму (7) представления многозначных функций назовем совершенной (обобщенной) мультиплексорной нормальной формой (СМулНФ), а форму (8) -совершенной (обобщенной) модульной нормальной формой (СМодНФ).

Зададимся последовательностями элементов из множества Кр -словами длины р в алфавите К как наборами Х = (Х1Х2 ••■ Хр)

входных переменных, где %i е К; X; = const i = 1,2, ,..,р.

Сами наборы будем интерпретировать как запись (разложение) чисел X 6 |о,1,..., N = kp — lj в виде р-разрядных чисел в it-ичной системе счисления. Подставив в выражение для любой перестановки в виде сложной функции

/И(я) = ЛИ(/2(-"(Л»»-))

всевозможные наборы % Для переменных р, получим систему из

N+1 уравнений относительно неизвестных aj:

ш= ©

7=0

ч*\64а,}

7=0

= © h*^-). (9) j=0 '

где Лх) - значение функции /(X) на наборе х = (х1 Х2 ■Хр)> Xj — О Х]0'^ значение у'-того полного терма /у на том же

наборе.

В результате задача о функциональной полноте системы базовых функций < 1\О,*,0 > и возможности представления любой многозначной функции в виде выражения (7), а комбинационного устройства — в виде некоторой схемы, сведена к установлению условий разрешимости системы логических уравнений вида (9) относительно квазискаляров а j, принимаемых за

неизвестные.

Аналитические методы решения таких уравнений развиты в следующей главе. Представим базисЛГ^^ ....лД* виде квадратной матрицы

0М №

о« 10}

... оИ.

с1,1 с1,2 ... С2Д с2,2... с2,к

ск,1ск,2...ск,к

—СТ,

где Т - операция транспонирования.

Обозначив неизвестные А = {яо>а1.....1} через 2 = .....г^}

сможем исходную систему уравнений записать в символической матричной форме: © [г * С ] © или Ъ С = Р , причем в последней ("классической") записи подразумевается "умножение" строки на столбец.

В работе рассмотрены специальные структуры базисных матриц (диагональная, треугольная) неразрывно связанные со свойством асимметричности операций * и © . Если же предположить, что элементарный базис (матрица С ) может быть образован произвольными элементами, то (при к>2) приходится постулировать дистрибутивность операции * относительно © . В частности, известно, что если * и © - модулярные операции умножения и сложения по модулю к ( и следовательно, алгебра < К; *,& > - ассоциативное кольцо с делением на некоторые элементы), то для разрешимости любой системы уравнений необходимо и достаточно, чтобы определитель сЫ|С| порождающей матрицы был делителем по операции * .

Данный результат может быть обобщен на произвольные операции * и © при сохранении следующих свойств: алгебра < К; © > - абелева группа, а алгебра < К;* > - группоид, не обязательно коммутативный, с доминантой и изотопными единицами (хотя бы с одной), т.е. алгебра <£;*,©> — в общем случае некоммутативное кольцо с изоединицами е' .

В этом случае все обобщенные главные миноры Д) матрицы С = |сгу |

должны быть из семейства изоединиц: Д; € {е'}, где Д} — с\ \,

= СЗЗ-(С13/А{)С31-

—[с23/¿2 "(чз / ДО (с21 / Д'г)] Ьг - (42/ Д!)СЗ|]•

Здесь минусом обозначена операция, обратная к ©, точкой (которая опущена) операция * , а косой чертой / операция, обратная к ♦ .

При выполнении сформулированных условий "проходит" обобщенное V' /

правило Крамера: х,- = '/., , V; - обобщенный определитель матрицы,

полученный из исходной матрицы С заменой вектора (столбца коэффициентов при неизвестном Х{) на вектор-столбец правых частей исходной системы уравнений. Возможен и иной способ обобщения, допускающий чтобы по операции * несущее множество К \ {с/} было группой (необязательно абелевой).

К сожалению, некоммутативность операции * при А=К и конечном (и даже счетном) к использовать не удается, так как конечные тела не существуют. (Коммутативные алгебры, в данном случае - поля Галуа, содержат

<?г элементов, где д - простое число, а г - натуральное число; следовательно,

допустима лишь логика со значностью к = <{ .)

Однако, сохраняя значность входных и выходных сигналов, можно принять, что множество скаляров А более мощное, чем множество К; это вполне допустимо, если на устройство, как на "черный ящик" налагаются требования лишь по входу - выходу.

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

С11С'2 =с22-(с12/А[)С21, с21с22

А'3 = Ъ<Л

с21с22с23 с31с32с33

пороговых и нейронных (присвоение весов двоичным переменным), многозначных инжекционных (объединение выходных коллекторов, что математически адекватно умножению на константы) и др. Данный принцип также реализуем средствами гибридной аналого-цифровой техники, основанной на применении операционных усилителей и цифровых (логических) схем.

В четвертой главе разработаны методы решения уравнений и систем уравнений многозначной алгебры логики.

Заметим, что если уравнение неоднородное, то как показано в [1], оно может быть приведено к равносильному однородному, а система однородных уравнений - к одному однородному уравнению.

Итак, пусть задано однородное (без правой части) уравнение многозначной (А>значной) логики с одним неизвестным,

/(*,Л) = 0, (10)

где / — функция, х — неизвестная величина и А — вектор (множество, набор) известных величин (параметров). Причем, /, х, А принимают произвольные значения из /С={0,1,2,...,£-1} (образованного нулем и целыми положительными числами).

Обозначим функцию /(х,Л) в левой части уравнения (10) так: Р, т.е. Р—f (*, А). В Л-значной логике имеем к функций , ^,..., .

Далее нам понадобится понятие большой характеристической функции (5).

Введем новое понятие: разложение функции многозначной логики по некоторой переменной (аналог теоремы разложения Шеннона, справедливой для двоичного случая).

/(хьх2,-. ,,х1,...,хр) - х\^А/{хъх2.....0,.. .,хр)У

\х^К/{хьх2,...Х...,хр)У...\х^К/{хьх2,...Л,...,хр)У... (11)

...у*Р-,)ЛД*ь*г.....к-\,...,хр).

Здесь символы ли v - многозначные логические операции соответственно конъюнкция и дизъюнкция.

В частности, для функции одной переменной f(x) имеем взамен соотношения (11) следующее разложение:

/(*) = *(0V(0)Vx(1>A/(l)V • • • Vx(0AAi)... Vx(*_,)Af(k -1). (12) Метод решения многозначных логических уравнений основывается на следующей теореме.

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

Доказательство. Применим введенное понятие о разложении многозначной функции к уравнению (10), или по-другому — к уравнению F(x) = 0; имеем

F(x) = xWAF0Vx(VAFlV...Vx(-k~1)AFk:_1=0 . (13)

Очевидно, здесь коэффициенты Fj принимают произвольные значения из множества К.

Рассмотрим однородное многозначное уравнение aiAxWVa2Ax(J')V..:Va„Ax('fi=0. Данное уравнение равносильно однородному многозначному уравнению (т.е. х е К) с двоичными коэффициентами щ € {0,1}.

Это позволяет воспользоваться двоичным разложением коэффициентов, т. е. считать, что коэффициенты Ft принимают значения только 0 и 1. Составим таблицу для двоичных значений(левая сторона).

Здесь R = 2 , символы й — так называемые произвольные постоянные, принимающие значения, указанные в скобках, например h (0,...,&-1) -произвольная постоянная, принимает любое значение из множества Л"={0, 1, 2, ..., ¿-1}; й(1,2) - значения 1 или 2, А(0,2) - значения 0 или 2 и т.п.

Таблица 2

N • /о Уравнения Корни

0 0 .. 0 0 х = Н = П (0,...Д-1)

1 0 .. 0 1 х = Н (1,2.....Аг-1)

2 0 .. 1 0 ;с(0)л0У:Д\1...=0 х = Н (0,2,...,к-1)

3 0 .. 1 1 х = П (2,...,£ — 1)

Я-3 1 .. 0 1 ^^.льМ-о х = \

1 .. 1 0 х-0

Д-1 1 ..1 1 решения нет

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

= 0.

Это условие целесообразно называть разрешающим.

В работе приведены примеры решения многозначных (троичных и четырехзначных) логических уравнений и их систем.

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

В пятой главе предложены и исследованы принципы структурной организации микропроцессорного устройства помехоустойчивой записи-воспроизведения цифровой информации на базе серийных отечественных ИС, предложены и исследованы устройства быстрого выполнения умножения и деления, вычисления синдромов. Применение БИС ПЗУ и БИС ПЛМ для указанных функций позволяет сократить оборудование. Предложен вариант декомпозиций для реализации умножителя, приемлемого по сложности.

Разработаны схемы предварительного обнаружения ошибок при демодуляции канального кода, произведена оценка и расчет вероятности ошибок. Полная вероятность не обнаружения ошибок с помощью т компонент синдрома находятся по формуле:

- без предварительного обнаружения ошибок при канальном декодировании

__ ..—тяг _т+1/оот+1.

РаЯ Ро Сп '

- с предварительным обнаружением ошибок при канальном декодировании

Р**Ч РО сп >

где ро - вероятность искажения одного (произвольного) символа в кодовом ' слове; т - количество проверочных символов.

Таким образом, предварительное обнаружение ошибок при канальном декодировании позволяет снизить погрешность в 2^" + раза.

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

Задача ставится следующим образом. Найти представление многозначной функции /(х) в виде "квазиполинома"

/(*) = © С; *мЛх),

у=о >

где мультипликативная операция * ("умножение") имеет приоритет перед аддитивной операцией © ("сложением"); Cj — коэффициенты

квазиполиномиального разложения; М^ — искомый (в данной задаче)

множитель, такой, что Mj{x) = г/ при некоторых] и Mj(x) = e=^d при

других ) . (Здесь Ы — доминанта, е - единица по операции *, возможно, изотопные.)

Таким образом, из постановки задачи сразу следует, что операции * и © должны быть, как минимум связаны аксиомой взаимодействия

<2 * а = (I — а * п*а = а — а*п.

тогда а=а<5><1.

Откуда (если принять а = с/) Л — п '.

И не обязательно дистрибутивным законом, как в известных представлениях.

Используя операции * и © в работе найдены выражения для Му (х),

ассоциирующиеся с интерполяционными формулами Лагранжа и Ньютона. Реализация "диагонального" базиса (квазиполиномом - в интерполяционной

форме Лагранжа), если Lj(x)—Mj(x) = d при и приу=х.

¿,(х) = * (хвхЛ^хвхо)*^©^)* ... 1=0,/* ]

Однако проще представление в нижеприводимой интерполяционной

форме Ньютона, содержащей меньше множителей (х©х,). Примем

"спадающий вид" треугольного базиса, при кoтopoмNj(x)=■Mj(x) — d, если

]<х, и Nj(x) = если />х. В этом случае представление многозначных

функций ищем в форме:

/(*)=с0е © Су* * (л£>х/)=с0©с]*(л©*о)ес2*(х©*о)*(л©^1)в..., (И) 7=1 ¡=0

где у -ый множитель Ньютона 0=1,2,..., к-\) имеет вид

ЛГу(х) = ^(х©.*/) = (;с©х0)*(*©*!)* ... *(х©х/_1). (15)

Теорема. Для представления произвольной функции многозначной логики в квазиполиномиальной форме Ньютона (14) или (15) необходимо и достаточно, чтобы алгебра < К; © > была группой, необязательно абелевой, а алгебра < К; *> — полугруппой с двусторонней доминантой и хотя бы с односторонним делением (т.е. каждый элемент - правая изоединица).

Пример операций, удовлетворяющих последней теореме, иллюстрируется табл.3. В этом случае искомые коэффициенты С последовательно определяются при _/ = 0,1,2,... из следующей системы логических уравнений:

/О)=с0еес;*;, 1=1

т.е./(0) = С0; /Ги = С0еС!*1; Д2) = СфСх*2еС2*2 и т.д.

Таблица 3

Примеры операций * и © в бипоиде целостности для к= 6

* 0 1 2 3 4 5 б) 0 0 1 2 3 4 5

0 0 0 0 0 0 0 0 0 1 2 3 4 5

1 0 1 1 1 1 1 1 1 0 3 .2 5 4

2 0 2 2 2 2 2 2 2 4 0 5 1 3

3 0 3 3 3 3 3 3 3 5 1 4 0 2

4 0 4 4 4 4 4 4 4 2 5 0 3 1

5 0 5 5 5 5 5 5 5 3 4 1 2 0

Завершая рассмотрение квазиполиномиальных форм Ньютона, отметим проблему их минимизации для конкретных многозначных функций. Эта проблема имеет свою специфику по сравнению с известной проблемой минимизации классических дизъюнктивных и конъюнктивных нормальных форм и обусловливается тем, что треугольному базису изотопно целое семейство "квазитреугольных" базисов (сводящихся к треугольному путем перестановок строк и столбцов порождающей матрицы).

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

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

квазиполиномы Ньютона, аналогичные выражению (14), в логико-алгебраическом базисе < Л,® > , где Л — многозначная конъюнкция, Ф — сумма по модулю к. Имеем:

/(х) = л0 ф а^А (х ® ® (д:фх0)Л(дгф:с1)ф...,=

= *ф а{ Л х^ = ад Ф х« ® агк х^ ф... ф ак_хК х^'1); 1=0

/=о

»Д1} — ® (и©йД» = 1,2,...А —1, где и ме{х,>4.

)=0х

Обобщенную асимметрично-билинейную форму /(х,у■) от двух переменных х, у вводим по определению:

Я*,*1)— *© СуЛх^ЛуМ, (18)

'=0,у"=0

где коэффициенты Су заданы табл.4.

Таблица 4 Матрица коэффициентов Си

х« -

Соо 0)1 с02 ... С0,к-\

С10 С11 С,2 ... С\,к-\ •

Ск-\,0Ск- • Ск-\,к-\

Аналогично вводятся обобщенные асимметрично-полиномиальные формы: трилинейная Дх,у,т) , ...,/> -линейная, где р-число входов (в данном случае -сомножителей) у многозначного устройства.

Задача легко обобщается на случай многих переменных. Итак, пусть дана

(16) (17)

матрица ^ = Подставляя в выражение (18) значения х=г, >>=/ получаем

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

Тогда

х-у = х Л у+х Л + ... +х Л +у Л +...+У Л х^-1}. (19) х»у = х Л у®х Л у^ф ... ©х Л ¿Д*-1' ф_у Л х«®. ..фу Л Х(к~1\ (20) Полагая х=у, получим квадраторное устройство, функционирующее в соответствии со следующей формулой:

Дх)=х-х=х2 =х+х« +х<3> + ... +,<*-»} +хй +х{3} +...+^-1} =

=х+2.х{2}+2.хй + ...+2.#Л (21)

где использована также операция обычного умножения на константу. Если в формуле (21) суммирование осуществить по модулю к, то получим "модульный квадратор". Известно, что возможна реализация элементарной ячейки базисной системы (ЭЯ) на элементах инжекционной логики, при этом объединение коллекторов одного и того же (п-р-п) транзистора эквивалентно обычному умножению выходного сигнала на константу, а различных транзисторов — обычному сложению. Это позволяет реализовать квадратор всего на 2{к-1) транзисторах с инжекционным питанием. Пример схемы квадратора для к=6 представлен на рис.4, где ОТ — отражатель тока, имеющий характеристику

¡г — х при х</; \ 0 при х>/-1.

Представления (19) и (20) содержат 2к-3 слагаемых и проще описанных в литературе форм для функций умножения (рис.5). Можно еще изменить мультипликативную операцию обобщенного модуля, чтобы ■ таблица коэффициентов содержала еще больше нулей. В работе введена такая операция (обозначена ®).Обобщенная асимметрично-билинейная форма определена в

виде: /(х,у)~ Ф С;/® х^ ,=0,7=0

Рис. 4. Пример схемы квадратора

Рис. 5. Пример множительного устройства

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

х-у = х®у + хЮ®уЮ+ ... + (9

/=1

В полученной форме только ¿—1 слагаемое. Если суммирование модульное, то и результат умножения х-у также будет получен по модулю к.

В принципе можно составить выражение для трех и большего р числа сомножителей. Но при увеличении к и р количество слагаемых Г быстро нарастает; для подсчета их числа, например, в алгебре <ЛТ;1\Л,Ф>

можно получить формулу: Т = [к — 1)^ — [к — 2)р. (22)

В результате имеем

Л—1

ХР = а1Х + а2х№ + ... + = £ , (23)

1=1

где а-[ = 1, а при / > 1 коэффициенты щ определяются из соотношения: щ = 7}+1 — 7}, что с учетом (22) дает

щ =!р-2(1-1)р+(1-2)р,1*1. (24)

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

/(х) = ¿о + Ь]Х + Ь2х2 + ... + Ь„х", где все операции обычные, но аргумент и параметры - дискретные. Пример. Пусть к = 4 и задана функция /(х) = 7х + 5х2 + х3, т.е. и = 3,Ь0 = 0,= 1,Ь2 = 5,Ь3 = 1.

9 1

Подставим в /(х) значения х их, предварительно определенные из формул (23) и (24): х2 = х + 2х^ + 2х^^,х3 = х + бх^ + 12х*3}. После приведения подобных членов, находим /(х) = 1 Зх +16х^ + 22х

т.е. в (23) для реализации заданной функции следует принять:

«0 — а\ =13, «2 =16, «з =22. Представим (23) в матричном виде: Р=Х- А, откуда А=Х~'р, где Б и А - вектор-столбцы, а X — матрица базисной системы функций, X"1 — обратная матрица. Для рассмотренного выше примера имеем:

1 0 0 0 0 0 0

-1 1 0 0 13 13 13

1- -2 1 0 42 -2-13 + 42 16

0 1 - 2 1 93 13-2-42 + 93 22

что совпадает с полученным ранее результатом.

В работе приведены примеры реализаций, хотя проблема практической реализации средствами микроэлектроники основных операций в асимметричных алгебрах ещё далека от завершения, как и вообще проблема схемной реализации устройств многозначной логики.

Основные результаты диссертационной работы. В ходе проведенных исследований, формулировки и решения поставленной в работе научной проблемы были получены следующие научные и практические результаты:

1. Сформулированы требования к информационному обеспечению ИС АСУ ТП показано, что помехозащищенные коды Рида-Соломона являются универсальными методами защиты информации от различного вида помех. Исследована проблема повышения защищенности высокоскоростного информационного обмена в ИС АСУ ТП.

2. Предложена и разработана обобщенная структура декодера, включающая канальное и гибридное (частотно-временное) декодирование двухкаскадного кода Рида-Соломона с перемежением и предварительным выявлением ошибок после канального декодирования.

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

конечных полях.

4. Предложено дискретное преобразование Ганкеля-Теплица и исследовано его применение для ускорения выполнения операции над полями Галуа.

5. Разработан безрекуррентный способ продолжения синдрома, как особого продолжения ганкелевой (теплицевой) матрицы, построенной на известных компонентах синдрома.

6. Предложены методы, позволяющие увеличить количество исправляемых ошибок, - канонизации и решения степенных уравнений (п = 3,4,5) над полями Галуа.

7; Разработаны методы, позволяющие повысить достоверность информации, передаваемой в ИС АСУ ТП, использующие решение систем линейных и нелинейных уравнений над ОР(2г).

8. Предложены и разработаны базовые структуры кодеков на основе микропроцессоров, декодеров ■ канальных кодов, интерливеров и деинтерливеров.

9. Созданы научные основы построения автоматизированных систем кодирования данных в современных ИС АСУ ТП включающие:

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

10. Разработаны методы анализа и синтеза ИС АСУ ТП нового поколения на многозначных схемах с обратными связями на основе решения многозначных (троичных и четырехзначных) логических уравнений и их систем.

Результаты работы использованы Технологическим институтом

энергетических обследований, диагностики и неразрушающего контроля «ВЕМО»; ОАО «Авангард»; ООО «ЭлектроРадиоАвтоматики-Р» и др., а

также в учебном процессе вузов, ведущих подготовку инженеров-

системотехников.

Основные положения и научные результаты опубликованы в следующих работах:

Монографии

1. Математические основы цифровой техники (прикладная конечная алгебра и многозначная логика)./ И.В. Иванова, В.М. Муттер, В.В. Трофимов, М.Ю. Калинунпсина. - СПб.: Литера плюс, 1999.-351 с.

2. Иванова И.В. Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини: Монография / И.В.Иванова. - СПб.: СЗТУ, 2005. - 152 с.

Статьи в журналах, рекомендуемых Перечнем ВАК

3. Иванова И.В. Общий метод решения однородного уравнения многозначной логики. / И.В.Иванова. //Известия СПб ГЭТУ «ЛЭТИ» серия «Приборостроение и информационные технологии». - 2005. - вып. 1.- С, 56-38.

4. Иванова И.В. Научные основы современных цифровых систем, использующих новый способ кодирования информации./И.В.Иванова. //Технология приборостроения. -2005. — №2(14). — С.53-68.

5. Иванова И.В. Недвоичные методы представления информации и многозначная элементная база. / И.В. Иванова. //Надежность. - 2005. - № 4(16), С. 8-18.

6. Иванова И.В. Классификация и синтез полиномиальных кодеков в системах автоматизированной обработки данных. / И.В.Иванова. // Технология и конструирование в электронной аппаратуре. Электронные средства: исследования, разработки. - 2005. -вып.4, С.19-23.

7. Иванова И.В. Анализ методов синдромного декодирования кодов Рида-Соломона. /И.В.Иванова. // Технология и конструирование в электронной аппаратуре. Электронные средства: исследования, разработки. - 2005. - вып.5, С. 3-6.

8. Иванова И.В. Алгоритм декодирования кодов Рида-Соломона на основе вычисления особых продолжений ганкелевых (тёплицевых) матриц и синдромов. / И.В.Иванова. // Технология и конструирование в электронной аппаратуре. Электронные средства: исследования, разработки. - 2005. - вып.б, С. 8-11.

Статьи, депонированные в ВИНИТИ

9. Иванова И.В. Методы анализа сигналов сложной формы, не имеющих записи в аналитическом виде. / И.В. Иванова, С.Н. Иванов; СЗПИ. - Л., 1983. - 5с. - Деп. в ВИНИТИ 19.10.83, № 5734-83.

10. Иванова И.В. Метод формирования КСС на основе функций Уолша. / И.В. Иванова, С.Н. Иванов; СЗПИ.-Л., 1983.-7с.-Деп. в ВИНИТИ 19.10.83, № 5733-83.

11. Микропроцессоры в цифровой обработке сигналов / Иванова И.В., Шишкин Ю.А., Григорьев В.В., Дроздова Г.Д. // Сб. «Применение МП комплектов БИС при разработке радиоэлектронной аппаратуры. - Л., 1983. - С.27-31.

12. Иванова И.В. Построение устройств цифровой обработки звуковых сигналов. / И.В. Иванова, Ю.А.Шишкин; ЛИИЖТ. - СПб., 1984. - 13с. - Деп. в ВИНИТИ 05.12.84, № 7742-84.

13. Моделирование на ЦВМ операций над полями Галуа. / И.В. Иванова, В.М. Муттер и [др.] ; СЗПИ. - Л., 1986. - 14с. - Деп. в ВИНИТИ 23.06.86, №4889.

14. Моделирование на ЦВМ процессов кодирования и декодирования / И.В. Иванова, В.М. Муттер и [др.]; СЗПИ.-Л., 1986.-37с.-Деп. в ВИНИТИ 23.06.86, № 4586.

15. Иванова И.В. Решение систем уравнений над полями Галуа в процессе декодирования кода Рида-Соломона. / И.В. Иванова, В.М. Мутгер; СЗПИ. - Л., 1987. - 33с. - Деп. в ВИНИТИ 25.03.87, Ха 2160.

16. Иванова И.В. Об особых продолжениях расширенных ганкелевых и теплицевых матриц над полями Галуа (с приложением к декодированию кода Рида-Соломона). / И.В. Иванова, В.М. Мутгер; СЗПИ. - Л., 1987. - 16с. - Деп. в ВИНИТИ 04.06.87, № 4028.

17. Иванова И.В. Микропроцессорная система для моделирования работы декодеров Рида-Соломона. / И.В. Иванова, В.М. Мутгер, В.И.Маринкин; СЗПИ. - Л., 1988. -44с. - Деп. в ВИНИТИ 05.09.88, № 7423.

18. Иванова И.В. Решение кубических уравнений над полями Галуа./ И.В. Иванова, В.М. Мутгер; СЗПИ. - Л., 1989. - 18с. - Деп. в ВИНИТИ 11.04.89, № 2325.

19. Иванова И.В. Решение уравнений четвертой степени над полями Галуа. / И.В. Иванова, В.М. Мутгер; СЗПИ. - Л., 1989. - 14с. - Деп. в ВИНИТИ 11.04.89, №>2326.

20. Иванова И.В. Решение уравнений пятой степени над полями Галуа. / И.В. Иванова, В.М. Мутгер; СЗПИ.-Л., 1989.-13с.- Деп. в ВИНИТИ 11.04.89, Ха2327.

21. Иванова И.В. Устройство многозначной логики на формальных нейронах (в недистрибутивных логико-алгебраических базисах). / И.В. Иванова, В.М. Мутгер, В.М.Шабер; СЗПИ. - Л., 1989. - 18с. - Деп. в ВИНИТИ 29.05.89, №3513.

22. Иванова И.В. Кодеки канальных кодов. / И.В. Иванова, В.М. Муттер; СЗПИ. - Л., 1989. -25с,-Деп. в ВИНИТИ 30.08.89,"Ха5619.

23. Иванова И.В. Преобразование Ганкеля-Теплица. / И.В. Иванова, В.М. Муттер; СЗПИ. -Л., 1995. -41с. - Деп. в ВИНИТИ 20.02.95, №468.

24. Иванова И.В. Решение уравнений троичной и четырехзначной логики. / И.В. Иванова, В.М. Мутгер; СЗПИ. - Л., 1996. - 9с. - Деп. в ВИНИТИ 16.02.96, №506.

25. Иванова И.В. Некоторые методы синтеза цифровых схем многозначной логики. / И.В. Иванова, В.М. Мутгер и [др.]; СЗПИ. - Л., 1997. - 30с. - Деп. в ВИНИТИ 30.06.97, №257.

26. Иванова И.В. Недистрибутивные конечные алгебры и логики в теории информационных и вычислительных систем. / И.В. Иванова, В.М. Мутгер, М.Ю. Калинушкина; СЗПИ. -СПб., 1999. - 10 с. - Деп. в ВИНИТИ 16.04.99, №1207.

27. Иванова И.В. Теория алгоритмов./ И.В.Иванова, В.И.Николаев. - СПб.: СЗПИ. - 1995. -178 с. (Учебное пособие).

28. Иванова И.В. Теория автоматов. / И.В.Иванова и [др.] - СПб.: СЗПИ. - 1997. - 95 с. (Учебное пособие).

29. Иванова И.В. Логика и теория алгоритмов. Дискретная математика: Рабочая программа. Задания и методические указания к выполнению контрольных работ./ И.В.Иванова, Г.И. Анкудинов, В.И. Николаев.- СПб.: СЗПИ,- 1996,2000,- 104 с.

30. Иванова И.В. Эксплуатация средств вычислительной техники. Рабочая программа. Задания на контрольные работы и методические указания к их выполнению. / И.В.Иванова. - СПб.: СЗПИ,- 2003.- 49с.

Доклады на научно-технических семинарах и конференциях

31. Иванова И.В. Разработка программно-аппаратных средств для кодирования и декодирования кодов Рида-Соломона на основе вычисления особых продолжений ганкелевых(теплицевых) матриц и синдромов. / И.В.Иванова. // Современные информ. и электронные технологии: Труды 6-й международной НПК. - Одесса, 2005. - С.82.

32. Иванова И.В. Организация и синтез кодеков в системах автоматизированной обработки данных. / И.В.Иванова. // Современные информ. и электронные технологии: Труды 6-й международной НПК. - Одесса, 2005. - С.83.

33. Иванова И.В. Проблема функциональной полноты в алгебре многозначной логики (необходимые и достаточные условия) с точки зрения абстрактной теории Галуа./ И.В.Иванова, В.М.Муттер. // Межвуз сб «Проблемы системотехники и АСУ». - СЗПИ. -

Л., 1991. -С. 143-172.

34. Иванова И.В. Использование аспектной декомпозизии при создании информационных систем./ И.В.Иванова, А.И. Иськив. // Доклады 11-й научно-техн. конф. - МГТУ. -Мурманск, 2000. - С. 14-15.

35. Иванова И.В. Новый подход к решению многозначных логических уравнений. / И.В. Иванова, В.М. Мутгер, М.Ю. Калинушкина. // Высшая математика. Физика. Информатика. Процессы управления и информационные системы. Системный анализ и прогнозирование: Доклады юбилейной научно-технической конференции студентов, аспирантов и сотрудников СЗПИ.- СП6.-.2000.-С.57-61.

36. Иванова И.В. Построение высокопроизводительных систем обработки информации повышенной надежности к контролепригодности. / И.В.Иванова, В.В. Григорьев, Г.Д. Дроздова. // Доклады республиканского семинара «Высокопроизводительные системы обработки информации. - Ужгород, 1984. - С.28-30.

37. Иванова И.В. Микропроцессорные кодеки для систем локальной автоматики. / И.В.Иванова, В.М. Мутгер. // Доклады всесоюзной конференция «Микропроцессорные средства локальной автоматики». - Гродно, 1989. - С.34-36.

38. Иванова И.В.Аналитические методы решения многозначных логических уравнений (в дискретной алгебре Клини). / И.В. Иванова И.В., М.Ю. Калинушкина, В.М. Муттер. // Информационные системы управления в лесном комплексе: Материалы научно-технической конференции. - СПбЛТА. - СПб.: 1999.- С.124-126.

39. Иванова И.В. Познавательно-психологические барьеры в теоретическом курсе дисциплин «Телеинформатика». / И.В.Иванова, В.М. Мутгер. // Материалы республ. научно-метод. конф.: Особенности организации подготовки инженеров без отрыва от производства. - Л.: СЗПИ. - 1990. - С.46-49.

ИВАНОВА ИРИНА ВЛАДИМИРОВНА

Автореферат

Лицензия ЛР 020308 от 14.02.97 Санитарно-эпидемиологическое заключение

_№78.01.07.953.П.005641.11.03 от 21.11.2003 г._

Подписано в печать 10.11,2005.Формат 60x84 1/16

Б. кн.-журн. Пл. 2,0. Б.л. I. Изд-во СЗТУ

Тираж 100. Заказ 1282.

Северо-Западный государственный заочный технический университет Издательство СЗТУ, член Издательско-полиграфической ассоциации вузов Санкт-Петербурга 1911186, Санкт-Петербург, ул. Миллионная, д.5

Оглавление автор диссертации — доктора технических наук Иванова, Ирина Владимировна

ВВЕДЕНИЕ.

Глава 1. Анализ тенденций развития автоматизированных систем кодирования и декодирования данных.

1.1. Анализ требований к информационному обеспечению АСУ ТП.

1.2. Тенденции развития методов декодирования.

1.3. Основные понятия и классификация дискретных преобразований.

1.4. Коды Рида-Соломона и методы декодирования.

1.5. Некоторые применения кодов Рида-Соломона.

1.6. Модель системы записи-воспроизведения цифровой информации.

1.7. Кодирование и декодирование кодов Рида-Соломона во временной области.

4 1.8. Операции над конечными циклическими группами и полями Галуа в процедурах кодирования и декодирования.

1.9. Операции над расширенными полями GF(2r).

1.10. Дискретные преобразования Фурье-Галуа и Ганкеля-Тёплица-Галуа.

1.11 .Общие сведения об алгебрах и логиках.

1.11.1. Понятие о дискретных и конечнозначных алгебрах логики.

1.11.2. Элементарные многозначные функции.

1.11.3.Операция суперпозиции многозначных логических функций.

1.11.4. Четыре основные проблемы, возникающие при синтезе логических схем.

1.11.5. Понятие о регулярных формах в конечнозначной алгебре логики

1.11.6. Функциональная полнота полиномиальных представлений.

Глава 2. Метод декодирования кодов Рида-Соломона на основе безрекуррентпых процедур вычисления особых продолжений гаикелевых(теплицевых) матриц и синдромов.^

2.1. Степенные уравнения порядка п = 2,. .,5.

2.2. Системы уравнений.

2.3. Вычисление особых продолжений ганкелевых(теплицевых) матриц.

N1 2.4. Кодирование-декодирование в частотной области.

2.5. Смешанное кодирование-декодирование.

Глава 3. Регулярные аналитические представления многозначных логических функций в асимметричных алгебрах.

3.1. Асимметричные алгебры с парой бинарных операций.

3.2. Некоторые обобщения асимметричных алгебр.

Ф 3.3. Обобщенные регулярные формы и постановка задачи.

3.3.1. Малоуровневые регулярные формы.

3.3.2. Сведение задачи о регулярных представлениях функций многозначной логики к задаче о разрешимости системы многозначных уравнений.

3.4. Аналитические представления многозначных функций в асимметричных алгебрах.

3.4.1. "Диагональная" система (базис).

3.4.2. "Треугольная" система (базис).

Глава 4. Разработка методов решения уравнений и систем уравнений много значной алгебры логики.

4.1. Классификация логических уравнений и систем уравнений.

4.2. Троичные логические уравнения.

4.2.1. Числовые троичные логические уравнения с одним неизвестным.

4.2.2. Буквенное троичное логическое уравнение с одним неизвестным.

4.2.3. Системы троичных логических уравнений.

4.3. Понятие о решении конечнозначных логических уравнений. fc 4.3.1. Обобщение основного метода решения.

4.3.2. Основной метод решения.

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

4.4.1. Анализ многозначных схем с обратными связями.

• 4.4.2. Синтез многозначных триггерных последовательностных схем.

Глава 5. Примеры практических схем и аналитических представлений элементов автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини.

5.1. Базовые структуры кодеков на основе микропроцессоров.

5.2. Функциональные расширители.

5.3. Реализация аналитических представлений многозначных функций в асимметричных алгебрах.

5.3.1. Реализация "диагонального" базиса (квазиполиномом в интерполяционной форме Лагранжа).

5.3.2. Реализация "треугольного" базиса (квазиполиномом в интерполяционной форме Ньютона).

5.3.3. Реализация асимметричных логико-арифметических базисов.

Введение 2005 год, диссертация по информатике, вычислительной технике и управлению, Иванова, Ирина Владимировна

В диссертации представлено обобщение выполненных автором в 1985-2004 г.г. исследований по проблемам помехозащищенности информационных потоков в системах автоматизированного управления производственными процессами. Исследования охватывают широкий спектр структур получения, передачи, приема и обработки информации и подчинены разработке общего принципа выполнения процедур защиты информации от потерь или искажений в реальном времени и в автоматическом режиме.

В работе предложена концепция формирования такого «общего принципа» на основе синтеза процедур, традиционно выполняемых при использовании полей Галуа для кодов Рида-Соломона. Реализация концепции предполагает детальный системный анализ традиционных методов кодирования/декодирования и разработку «быстрых» алгоритмов автоматического введения защитных кодов в трактах передачи информации.

Актуальность темы.

Исследования проводились в рамках государственных программ и координационных планов, по ведомственным тематическим заказам (государственная регистрация отчетов по НИР за№№ 01850013661, 01870067179, 01860107705), в соответствии с комплексной целевой программой «Российские верфи», в научно-исследовательских проектных разработках Технологического института энергетических обследований, диагностики и не-разрушающего контроля «ВЕМО», что является формальным признаком актуальности.

Исследования подчинены решению ряда проблем помехозащищенности информационных потоков в производственных средах, более точно - в системах автоматизированного управления производственными процессами. Совокупность таких потоков (растущая чрезвычайно быстро) характерна разнообразием их по объему, по содержанию, по вероятности ошибок и требованиям к достоверности. Применение известных методов защиты во многих случаях не устраивает потребителя по ряду причин, главные из которых длительность процедур кодирования/декодирования и высокий уровень их сложности (соответственно высокая квалификация оператора).

Необходимость формирования развитого ряда методов помехозащищенности информации диктуется потребностями практики и признается специалистами, ведущими разработки в данной области. Фундаментальные идеи решения проблемы содержатся в работах отечественных и зарубежных учёных: Шеннон К., Блейхут Р.Э., Кларк Дж, Кейн Дж., Берлекэмп Э.Р., Питерсон У., Уэлдон Э., Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А., Прэтт У., Макклеллан Дж.Х., Рейдер Ч.М., Кассами Т., Токура Н., Ивадари Е., Инагаки Я., Блох Э.Л., Зяблов В.В., Муттер В.М., Колесник В.Д., Мирончиков Е.Т., Раков М.А., и др. В последние десятилетия исследования по проблемам быстрого кодирования/декодирования стали приоритетными. Приоритет исследований обусловлен высоким уровнем развития микроэлектроники, аппаратных и программных средств, обеспечивающих обмен информацией. Объективным следствием развития технических средств явились и функциональные ограничения применяемых методов конечной алгебры, многозначной логики и традиционной идеологии проектирования цифровой микроэлектронной аппаратуры на базе многозначных элементов. Известны изобретательские решения отдельных задач помехозащищенности, они не снимают проблемы в целом, но с очевидностью указывают на необходимость пересмотреть научные основы организации процедур кодирования/декодирования информации в реальном времени.

Объект исследования - средства защиты информации от помех в автоматизированных системах управления технологическими процессами. Для достижения цели представлялось необходимым решить следующие основные задачи:

9. Разработка методов анализа и синтеза ИС АСУ ТП нового поколения.

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

1. Способ частотно-временного (гибридного) декодирования цифровой информации АСУ ТП.

2. Комплекс математических моделей, включающий:

- безрекуррентный способ продолжения синдрома для ускорения процесса декодирования;

- решение степенных уравнений и систем уравнений в полях Галуа для повышения качества декодирования;

- решение многозначных (троичных и четырехзначных) логических уравнений и их систем для обеспечения анализа и синтеза ИС АСУ ТП нового поколения.

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

- асимметричные алгебры с двумя бинарными операциями: асимметричные кольца, асимметричные тела, асимметричные поля и их разновидности;

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

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

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

5. Аналитические методы описания структур многозначной логики могут быть использованы при анализе функциональных свойств и схемотехнических решений вычислительных средств для ИС АСУ ТП.

1. Концептуальную модель системного метода построения кодов Рида-Соломона в полях Галуа.

3. Теоретические основы кодирования/декодирования с использованием кодов Рида-Соломона над полем Галуа GF(2r), позволяющие снизить погрешность ошибок при канальном декодировании в 2(m+l){R'r) раза.

4. Математические методы решения степенных уравнений («=3,4,5), систем линейных и линейно-нелинейных уравнений над GF(2r), возникающих при исправлении стираний, ошибок и стираний.

5. Новые алгебры логики и методы решения многозначных логических уравнений и их систем.

Реализация результатов работы. Разработанный метод декодирования кодов Рида-Соломона по особым продолжениям расширенных ганкелевых (теплицевых) матриц над полями Галуа, позволяющий безрекуррентное вычисление синдрома ошибок внедрен в рамках хоздоговорной научно-исследовательской работы СЗПИ (номера Государственной регистрации отчетов но хоздоговорным НИР; 01850013661, 01870067179, 01860107705), что подтверждено соответствующим актом использования результатов диссертационной работы для экспресс-классификации многомерных случайных сигналов при практической реализации в научно-исследовательских проектных разработках, предприятиями различного профиля при модернизации существующих систем автоматического управления, кибернетики, радиотехники, информатики, аналого-цифровой измерительной техники: Технологическим институтом энергетических обследований, диагностики и неразрушающего контроля «ВЕМО»; НИОКР ОАО «Авангард»; НИОКР, проводимых ООО «ЭлектроРа-диоАвтоматики-Р» и др., в соответствии с комплексной целевой программой «Российские верфи». Тематика диссертационной работы используется в учебном процессе высших и средних учебных заведений в курсах «Информатика», «Дискретная математика», «Математическая логика и теория алгоритмов», «Теория автоматов», «Схемотехника», «Эксплуатация средств вычислительной техники» при создании учебно-методических пособий.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на 6-й международной научно-практической конференции «Современные информационные и электронные технологии» (Одесса, 23-27 мая 2005г.); на всесоюзной конференции «Микропроцессорные средства локальной автоматики» - Гродно, 1989г.; на республиканском семинаре ВСОИ, Ужгород, 1984г; на всесоюзной конференции «Применение МП комплектов БИС при разработке радиоэлектронной аппаратуры», Ленинград, 1983 г. и семи научно-технических конференциях и семинарах.

Заключение диссертация на тему "Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини"

Результаты работы использованы Технологическим институтом энергетических обследований, диагностики и неразрушающего контроля «ВЕМО»; ОАО «Авангард»; ООО «ЭлектроРадиоАвтоматики-Р» и др., а также в учебном процессе вузов, ведущих подготовку инженеров-системотехников.

ЗАКЛЮЧЕНИЕ

В ходе проведенных исследований, формулировки и решения поставленной в работе научной проблемы были получены следующие научные и практические результаты:

1. Сформулированы требования к информационному обеспечению АСУ ТП показано, что помехозащищенные коды Рида-Соломона являются универсальными методами защиты информации от различного вида помех. Исследована проблема повышения защищенности высокоскоростного информационного обмена в АСУ ТП.

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

6. Предложены методы, позволяющие увеличить количество исправляемых ошибок, - канонизации и решения степенных уравнений (и = 3,4,5) над полями Галуа.

7. Разработаны методы, позволяющие повысить достоверность информации, передаваемой в информационных системах АСУ ТП, использующие решение систем линейных и нелинейных уравнений над GF(2r).

8. Предложены и разработаны базовые структуры кодеков на основе микропроцессоров, декодеров канальных кодов, интерливеров и деинтерливеров.

9. Созданы научные основы построения автоматизированных систем кодирования данных в современных информационных систем АСУ ТП включающие:

-обобщение известных и приведенных новых регулярных форм в конечнозначной алгебре лоI гики, предложены правила их построения;

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

- новые асимметричные алгебры с двумя бинарными операциями: асимметричные кольца, асимметричные тела, асимметричные поля и их разновидности;

- новые обобщенные регулярные формы в асимметричных алгебрах логики и практические примеры аналитических представлений многозначных функций в асимметричных алгебрах. 10. Разработаны методы анализа и синтеза информационных систем АСУ ТП нового поколения на многозначных схемах с обратными связями на основе решения многозначных (троичных и четырехзначных) логических уравнений и их систем.

Библиография Иванова, Ирина Владимировна, диссертация по теме Автоматизация и управление технологическими процессами и производствами (по отраслям)

1. Азаров, В.В.Оценка сложности реализации вычисления в конечных полях. / В.В. Азаров,

2. Г.С. Истомин. М.: Томск, 1975. - В кн.: VI конференции по теории кодирования и передачи информации, ч.И. - С. 7-12.

3. Ахо, А. Построение и анализ вычислительных алгоритмов./ А. Ахо, Д. Хопкрофт,

4. Д.М.Ульман. М.: Мир, 1979.

5. А.с. 1210141 СССР, МКИ3 Н С II В20/10. Устройство для воспроизведения цифровых сообщений / В.М. Муттер, В.И. Маринкин, В.И. Ефимов, С.Н. Иванов (СССР). -№3769498; заявл. 9.07.84.

6. А.с. 1238148 СССР, МКИ3 4С II В20/10. Устройство для воспроизведения цифровых сообщений с носителями записи. / В.М. Муттер, В.И. Маринкин, В.И. Ефимов, Л.В. Боброва (СССР). №3769463; заявл. 9.07.84.

7. А.с. 1243027 СССР, МКИ3 4С II В20/10. Устройство для воспроизведения цифровых сообщений. / В.М. Муттер, В.И. Маринкин, В.И. Ефимов, Б.В. Шамрай (СССР). -№3769329; заявл. 9.07.84; опубл. 07.07.86, Бюл. № 25 2с.

8. Афанасьев, В.Б. Алгоритмы БПФ для полей. / В.Б. Афанасьев, И.И. Грушко.// Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987. - С. 33-35.

9. Ахмед, Н. Ортогональные преобразования при обработке цифровых сигналов./ Н. Ахмед,

10. К.Р. Рао. М.: Связь, 1980. - 248 с.

11. Бабанин, А.Г. Анализ определительного метода декодирования кода Рида-Соломона./ А.Г.Бабанин, М.В. Бессонов, В.Ю. Добрынин. //Электронное моделирование. М., 1984. -Т.6, №3.-С.41-45.

12. Берлекэмп, Э. Р. Алгебраическая теория кодирования: пер. с англ./ Э.Р.Берлекэмп- М.: Мир, 1971.-476 с.

13. Берлекэмп, Э.Р. Техника кодирования с исправлением ошибок. / Э.Р.Берлекэмп //ТИИЭР. 1980. - Т.68, №5. - С.24-58.

14. Биркгоф, Г. Современная прикладная алгебра / Г. Биркгоф, Т. Барти. М.: Мир, 1976. -400 с.

15. Бесперстов, Э.А. Использование микропроцессора в декодере кода БЧХ./ Э.А. Бесперстов, А.П. Веселое. // Техника средств связи. Сер. ТРПиА. М., 1986. - №3. - С.66-69.

16. Бесперстов, Э.А. Декодер приемника системы цифрового радиовещания. / Э.А Бесперстов, Л.М. Финк. // Техника средств связи. Сер. ТРПиА. М., 1986. - №3. - С.53-59.

17. Блейхут, Р.Э. Теория и практика кодов, контролирующих ошибки. / Р.Э. Блейхут. М.: Мир, 1986.-576 с.

18. Блейхут, Р.Э. Алгебраические поля, обработка сигналов, контроль ошибок. / Р.Э. Блейхут. //ТИИЭР. -1985. Т. 73, №5. - С.30-53.

19. Блох, Э.Л. Обобщенные каскадные коды: Алгебраическая теория и сложность реализации. / Э.Л. Блох, В.В. Зяблов. М.: Связь, 1976. - 240с.

20. Блох, Э.Л Линейные каскадные коды./ Э.Л. Блох, В.В, Зяблов. М.: Наука, 1982. - 230 с.

21. Блох, Э.Л. О методе декодирования для кодов Боуза-Чоудхури, исправляющих тройные ошибки. / Э.Л. Блох. //Изв. АНСССР. Техническая кибернетика. М.:1964.- №3- С.30-37.

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

23. Варакин, Л.Е. Теория систем сигналов./ Л.Е. Варакин. М.: Сов. Радио, 1978. - 304 с21 .Варинец, Л.В. Абстрактные алгебраические системы и цифровая обработка сигналов./ Л.В. Варинец и др. Киев: Наукова Думка, 1986. - 248 с.

24. Вариес, Н.И. Код Файра и его применение в полупроводниковых ЗУПВ./ Н.И. Вариес, А.К. Култыгин.// В кн.: Развитие теории и техники хранения информации. Доклады Всесоюзной научно-технической конференции. - Пенза: 1983.

25. Вариченко, Л. В. Абстрактные алгебраические системы и цифровая обработка сигналов. / Л.В. Вариченко, В.Г. Лабунец, М.А. Раков. Киев.: Наук.думка. -1986. - 248 с.

26. Воеводин, В.В. Вычислительные процессы с теплицывыми матрицами./ В.В.Воеводин, Е.Е. Тыртышников. М.: Наука. -1987. - 320 с.

27. Вологдин, Э.И. Коррекция ошибок при цифровой звукозаписи. / Э.И. Вологдип. // Техникасредств связи. Сер. ТРПиА. М.: 1981. - №2. - С.89-108.

28. Вологдин, Э.И. Исправление ошибок в цифровой системе грамзаписи. / Э.И. Вологдин, A.M. Коган // Техника средств связи. Сер. ТРПиА. М.: 1984. - №2. - С. 15-20.

29. Вологдин, Э.И. Цифровая звукозапись на оптическом диске. / Э.И. Вологдин. //Техника средств связи. Сер. ТРПиА. -М.: 1979. №2. - С.5-13.

30. Габидулин, Э.М. Кодирование в радиоэлектронике./ Э.М. Габидулин, В.Б. Афанасьев.

31. М.: Радио и связь, 1986. 176 с.

32. Галлагер, Р. Теория информации и надежная связь./ Р. Галлагер. М.: Сов. Радио, 1974.

33. Гинзбург, С.А. Функциональные преобразователи с аналого-цифровым представлениеминформации / С.А. Гинзбург, Ю.Я. Любарский. М.: Энергия, 1973. - 136 с.

34. Глушков, В.М. Синтез цифровых автоматов. / В.М. Глушков. М.: Физматгиз,1962. - 476с.

35. Горенбургов, М.А. Методы нечеткой логики в информатизации предпринимательства: доклад и тезисы / М.А. Горенбургов, В.М. Муттер, М.Ю. Калинушкина. СПб.: УЭФ,1996. -Зс.

36. Дагман, Э.Е. Быстрые дискретные ортогональные преобразования. / Э.Е. Дагман, Г.А.

37. Кухарев. Новосибирск: 1983.-231с.

38. Евтеев, Ю.И. Аппаратурная реализация дискретного преобразования Фурье. / Ю.И. Ев-теев и др. М., 1978. - 186с.

39. Евсеев, Г.С. К вопросу о сложности декодирования линейных кодов. / Г.С. Евсеев // В кн.: Тр. V Междунар. симп. по теории информ. Ч.1.- 1979 С.139-141.

40. Завьялов, В.А. Коды, корректирующие ошибки в независимых группах разрядов слова ЗУ /

41. B.А. Завьялов // Вопросы надежности и технического диагностирования вычислительных устройств. -М.: Энергоатомиздат, 1986. -С.29-37.

42. Закревский, А.Д. Логические уравнения / А.Д. Закревский. Минск, 1975.

43. Зиновьев, А.А. Философские проблемы многозначной логики / А.А.Зиновьев.- М.,1960-81с.

44. Иванова, И.В. Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини: Монография / И.В.Иванова. СПб.: СЗТУ, 2005. - 152 с.

45. Иванова, И.В. Общий метод решения однородного уравнения многозначной логики. /

46. И.В.Иванова. //Известия СПб ГЭТУ «ЛЭТИ» серия «Приборостроение и информационные технологии». 2005. - вып.1- С.36-38.

47. Иванова, И.В. Научные основы современных цифровых систем, использующих новый способ кодирования информации./И.В.Иванова. //Технология приборостроения. 2005. -№2(14). -С.53-68.

48. Иванова, И.В. Недвоичные методы представления информации и многозначная элементная база. / И.В. Иванова. // Надежность. 2005. -№ 4(16), С. 8-18.

49. Иванова, ИВ. Анализ методов синдромного декодирования кодов Рида-Соломона.

50. Иванова, И.В. Метод формирования КСС на основе функций Уолша. / И.В. Иванова, С.Н. Иванов; СЗПИ. Л., 1983. - 7с. - Деп. в ВИНИТИ 19.10.83, № 5733-83.

51. Иванова, И.В. Построение устройств цифровой обработки звуковых сигналов. / И.В. Иванова, Ю.А.Шишкин; ЛИИЖТ. СПб., 1984. - 13с. - Деп. в ВИНИТИ 05.12.84, № 774284.

52. Иванова, ИВ. Решение систем уравнений над полями Галуа в процессе декодирования кода Рида-Соломона. / И.В. Иванова, В.М. Муттер; СЗПИ. Л., 1987. - 33с. - Деп. в ВИНИТИ 25.03.87, №2160.

53. Иванова, И.В. Об особых продолжениях расширенных ганкелевых и теплицевых матриц над полями Галуа (с приложением к декодированию кода Рида-Соломона). / И.В. Иванова, В.М. Муттер; СЗПИ. Л., 1987. - 16с. - Деп. в ВИНИТИ 04.06.87, № 4028.

54. Иванова, И.В. Микропроцессорная система для моделирования работы декодеров Рида

55. Соломона. / И.В. Иванова, В.М. Муттер, В.И.Маринкин; СЗПИ. Л., 1988. - 44с. - Деп. в ВИНИТИ 05.09.88, №7423.

56. Иванова, ИВ. Решение кубических уравнений над полями Галуа./ И.В. Иванова, В.М. Муттер; СЗПИ. Л., 1989. - 18с. - Деп. в ВИНИТИ 11.04.89, № 2325.

57. Иванова, И.В. Решение уравнений четвертой степени над полями Галуа. / И.В. Иванова, В.М. Муттер; СЗПИ. Л., 1989. - 14с. - Деп. в ВИНИТИ 11.04.89, №2326.

58. Иванова, И.В. Решение уравнений пятой степени над полями Галуа. / И.В. Иванова, В.М.

59. Иванова, ИВ. Кодеки канальных кодов. / И.В. Иванова, В.М. Муттер; СЗПИ. Л., 1989. -25с.- Деп. в ВИНИТИ 30.08.89, №5619.

60. Иванова, ИВ. Проблема функциональной полноты в алгебре многозначной логики (необходимые и достаточные условия) с точки зрения абстрактной теории Галуа. / И.В. Иванова, В.М. Муттер. // Проблемы системотехники и АСУ. Л.: СЗПИ. - 1991. - С.143-171.

61. Иванова, И.В. Некоторые методы синтеза цифровых схем многозначной логики. / И.В.

62. Иванова, В.М. Муттер и др.; СЗПИ. Л., 1997. - 30с. - Деп. в ВИНИТИ 30.06.97, №257.

63. Иванова, И.В. Недистрибутивные конечные алгебры и логики в теории информационных и вычислительных систем. / И.В. Иванова, В.М. Муттер, М.Ю. Калинушкина; СЗПИ. -СПб., 1999. 10 с. - Деп. в ВИНИТИ 16.04.99, №1207.

64. Иваськив, Ю.Л. Принципы построения многозначных физических схем./ Ю.Л. Иваськив. -Киев: Наукова думка. 1971.

65. Иохвидов, ИС. Ганкелевы и теплицевы матрицы и формы. / И.С. Иохвидов. М.: Наука.1974.

66. Капустин, Э.А. Оценка возможности реализации кода МККТТ для передачи изображенийфаксимильным методом при использовании микропроцессорного комплекта К580. / Э.А, Капустин. // Каналы и аппаратура передачи дискретной информации М.,1986 - С. 41-45.

67. Карповский, М.Г. Спектральные методы анализа и синтеза дискретных устройств. / М.Г. Карповский, Э.С. Москалев. Л.: Энергия, 1973. - 138с.

68. Кларк, Дж. Кодирование с исправлением ошибок в системах цифровой связи: пер. с англ. / Дж. Кларк, Дж. Кейн. М.: Радио и связь, 1987. - 392с.

69. Клипы, С.К Математическая логика / С.К. Клини. М.: Мир, 1973.

70. Кметь, А.Б. Четырехзначная логика. Реализация функций / А.Б. Кметь. М.: 1991.

71. Коган, A.M. Помехоустойчивое кодирование в стандарте компакт диск. / A.M. Коган, Ю.Г. Гофман, Л.Г. Синицина. // Техника средств связи. Сер. ТРПиА.- М., 1986 №2.-С.12-19.

72. Коган, A.M. Стандартизация при цифровой звукозаписи. / A.M. Коган. // Техника средств связи. Сер. ТРПиА. М., 1981. - №2. - С. 126-133.

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

74. Корн, Г. Справочник по математике (для научных работников и инженеров)./ Г. Корн, Т. Корн. -М.: Наука. 1973.-831 с.

75. Крук, Е.А. Комбинаторное декодирование в связи и криптографии. / Е.А.Крук, С.В.Федоренко.// Научно-технические ведомости СПбГТУ. СПб.: Изд-во СПбГТУ, 2002. - №3. - С.69-77.

76. Крук, Е.А. Самодуальные квазициклические коды. / Е.А.Крук, С.В.Федоренко. //Научно, технические ведомости СПбГТУ. СПб.: Изд-во СПбГТУ, 2004. -№1. - С.52-61.

77. Кузнецов, О. П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский. М.: Энергоатомиздат, 1988. - 480 с.

78. Куликов, Л.Я. Алгебра и теория чисел / Л.Я. Куликов. М.: Высшая школа, 1979. - 559 с.

79. Курош, А.Г. Общая алгебра. / А.Г. Курош. М.: Наука, 1974. -160 с.

80. Курош, А.Г. Курс высшей алгебры / А.Г. Курош. М.: Наука, 1982.

81. Левин, В.И. Бесконечнозначная логики в задачах кибернетики / В.И. Левин. М.: Радио и ' связь, 1982.- 176 с.

82. Лидл, Р. Конечные поля: в 2 т. / Р. Лидл, Г. Нидеррайтер . М.: Мир, 1988. - 822 с.

83. Мак-Вильямс, Ф.Дж. Теория кодов, исправляющих ошибки: пер. с англ./ Ф.Дж.Мак

84. Вильямс, Н.Дж.А. Слоэн. М.: Связь, 1979. - 744 с.

85. Маккелан, Дж. X. Применение теории чисел в цифровой обработке сигналов: Пер. с англ./ Дж. X. Маккелан, И.М. Рейдер. М.: Радио и связь. - 1983. - 264 с.

86. Математические основы цифровой техники: прикладная конечная алгебра и многозначная * логика / В.М. Муттер, В.В. Трофимов, И.В. Иванова, М.Ю. Калинушкина. СПб.: Литераплюс, 1999.-351 с.

87. Микропроцессоры в цифровой обработке сигналов / Иванова И.В., Шишкин Ю.А., Григорьев В.В., Дроздова Г.Д. // Применение МП комплектов БИС при разработке радиоэлектронной аппаратуры. Л., 1983.- С.27-31.

88. Микропроцессор К580ИК80 в аппаратуре передачи данных с адресным переспросом / М.Т. Валиев и др. // Каналы и аппаратура передачи дискретной информации. М., 1986. -С.10-14.

89. Мкртчян, С.О. Проектирование логических устройств ЭВМ на нейронных элементах / С.О. Мкртчян. М.: Энергия, 1977. - 200 с.

90. Моделирующие системы с многозначным и гибридным кодированием / под ред. М.А. Ра-кова. -Киев:Науковадумка, 1980.

91. Моделирование на ЦВМ операций над полями Галуа. / И.В. Иванова, В.М. Муттер идр.; СЗПИ.-JL, 1986. 14с. - Деп. в ВИНИТИ 23.06.86, №4889.

92. Моделирование на ЦВМ процессов кодирования и декодирования / И.В. Иванова, В.М. Муттер и др.; СЗПИ. Л., 1986. - 37с. - Деп. в ВИНИТИ 23.06.86, № 4586.

93. Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение./ Р. Морелос-Сарагоса. М.: Техносфера. - 2005. - 320 с.

94. Муттер, В.М. Основы помехоустойчивой телепередачи информации/ В.М. Муттер. Л.: Энергоатомиздат, 1990. - 288 с.

95. Муттер, В.М. Недистрибутивные абстрактные алгебры для аналитического представления функций многозначной логики / В.М. Муттер; СЗПИ. СПб., 1982. - 22 с. - Деп. в ВИНИТИ 15.12.1982, №2895-В82.

96. Муттер, В.М. Уравнения многозначной и нечеткой (дискретной и непрерывной) логики /

97. В.М. Муттер // Доклад на II Международной конференции: Актуальные проблемы фундаментальных наук. М.: МВТУ, 1994,- 6 с.

98. Муттер, В.М. Регулярные аналитические (интерполяционные) представления функций многозначной логики в недистрибутивных и в асимметричеких алгебрах / В.М.Муттер; СЗПИ. СПб., 1982. - 12 с. - Деп. в ВИНИТИ 15.05.1982, № 1279-В82.

99. Муттер, В.М. Представление функций многозначной логики в недистрибутивных логико-алгебраических базисах / В.М. Муттер; СЗПИ. СПб., 1982. - 11 с. - Деп. в ВИНИТИ 15.12.1982, №2893-В82.

100. Муттер, В.М. Малоуровневые представления функций многозначной логики / В.М. Муттер; СЗПИ. СПб., 1982. - 20 с. - Деп. в ВИНИТИ 15.12.1982, № 2894-В82.

101. Муттер, В.М. Электронные цифровые устройства автоматики, телемеханики и радиотехники / В.М. Муттер. Л.: СЗПИ, 1980. - 80 с.

102. Муттер, В.М. Решение квадратных уравнений над полями Галуа. / В.М. Муттер и др.; СЗПИ. СПб., 1984. - 15 с. - Деп. в ВИНИТИ 20.06.84, № 4687-В84.

103. Муттер, В.М. Устройство для вычисления полинома. / В.М. Муттер и др. А.с. № 1179323,1985.

104. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток./ Г. Нуссбаумер. М.: Радио и связь, 1985. - 248 с.

105. Отнес, Р. Прикладной анализ временных рядов./ Р. Отнес, JI. Эноксен. М.: 1982.-340 с.

106. Пастухов, А.В. Способ построения высоконадежных устройств параллельного кодирования и декодирования кодов Хэмминга. / А.В. Пастухов. // Вопросы радиоэлектроники. Серия ЭВТ. 1976. - С.75-81.

107. Пастухов, А.В. О классе кодов с исправлением кратных ошибок в независимых группах символов. /А.В, Пастухов.//Вопросы радиоэлектроники. Сер.ЭВТ. -1981 .—№10.— С.68-74.

108. Питерсон, У. Коды, исправляющие ошибки: Пер. с англ. / У. Питерсон, Э. Уэлдон. М.: Мир, 1976.-596с.

109. Полед, А. Цифровая обработка сигналов. / А. Полед, Б. Лиц. Киев: Вища школа, 1979. -264 с.

110. Понтрягин, JI.C. Непрерывные группы. /Л.С. Понтрягин. М.: Гостехиздат, 1954.

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

112. Прикладные нечеткие системы / под ред. Т.Тэрано и др. М.: Мир, 1993. - 368 с.

113. Применение цифровой обработки сигналов / Под ред. Э.Оппенгейма М.: Мир, 1980360 с.

114. Прэтт, У. Цифровая обработка изображений. / У. Прэтт. М.: Мир, 1982. -Т.1.-312 с.

115. Пухальский, Г.И. Цифровые устройства: учебное пособие для втузов / Г.И. Пухальский, Т.Я. Новосельцева. СПб.: Политехника, 1996. - 885 с.

116. Рабинер, JI.P. Теория и применение цифровой обработки сигналов. / Л.Р. Рабинер, Б. Го-улд. М.: Мир, 1978. - 848 с.

117. Раков, М.А. Реализация многозначных структур автоматики / М.А. Раков. Киев: Нау-кова думка, 1976. -350 с.

118. Садыхов, Р.Х. Методы и средства обработки сигналов в дискретных базисах./ Р.Х. Са-дыхов и др. Минск: Наука и техника, 1987. - 296 с.

119. Самарский, А.С. Экономичное построение блока коррекции ошибок памяти и его эффективность./ А.С. Самарский, В.Г. Беляев. // Вопросы радиоэлектроники. Серия ЭВТ. -1977.- №11.-С.36-41.

120. Ситников, О.П. Гармонический анализ на группах в абстрактной теории систем. / О.П. Ситников. Свердловск: УПИ, 1976. - С.5-23.

121. Скляр, Б. Цифровая связь, теоретические основы и практическое применение: пер. с англ./ Б.Скляр. М.: Изд. дом «Вильяме», 2003. - 1104 с.1124. Стандарт МЭК: Цифровая звуковая система Компакт Диск, 1983. Standart on Compact

122. Digital Audio System, 1982.

123. Теория кодирования / Т.Касами, Н.Токура, Е.Ивадари, Я.Инагаки: Пер. с япон. М.: Мир, 1978.-576с.

124. Трахтмаи, A.M. Основы теории дискретных сигналов на конечных интервалах. / A.M. Трахтман, В.А. Трахтман. М.: Сов.радио, 1975. - 208 с.

125. Трахтмаи, A.M. Введение в обобщенную спектральную теорию сигналов. / A.M. Трахт-I ман. М.: Сов.радио, 1972. - 340с.

126. Тузов, Г.И. Помехозащищенность радиосистем со сложными сигналами. / Г.И. Тузов и др. М: Радио и связь, 1985. - 264 с.

127. Управляющие вычислительные машины в АСУ технологическими процессами./ под ред. Т.Харрисона. М: Мир, 1975. -Т.1.-530 с.

128. Уткин, Л.В. Нетрадиционные методы оценки надежности информационных систем. / Л.В.Уткин, И.Б.Шубинский. СПб.: Изд-во Любавич, 2000. -173 с.

129. М.Л.Чернобай. // Труды Межд. конф. Мягкие вычисления и измерения. СПб, 2001. -С.174-179.

130. Форни, Д. Каскадные коды. / Д. Форни М.: Мир, 1970. - 207 с.

131. Фрид, Э. Элементарное введение в абстрактную алгебру / Э. Фрид. М.: 1979. - 260 с.

132. Хвощ, С.Т. Микропроцессоры и микро-ЭВМ в системах автоматического управления: Справочник. / С.Т. Хвощ, Н.Н. Варлинский, Е.А. Попов. / Под ред. С.Т.Хвоща. JI.: -Машиностроение. -1987. - 640 с.

133. Шеннон, К. Математическая теория связи: Работы по теории информации и кибернетике. / К. Шеннон. М.: - 1963. - С.243-332.

134. Шеннон, К. Вероятность ошибки для оптимальных кодов в гаусовском канале: Работы по теории информации и кибернетике./ К. Шеннон. М.: - 1963. - С.540-586.

135. Эванс, М. Матрица Нельсона, позволяющая выявить две ошибки на слово. / М.Эванс.// Электроника. 1982. - Т.55, №11. - С.59-64.

136. Яблонский, С.В. Введение в дискретную математику. / С.В. Яблонский. М.: Наука, 2001.-384 с.

137. Яглом, И.М. Математические структуры и математическое моделирование / И.М. Яглом. -М.: Сов.радио, 1980.-144 с.

138. Яковлев, В.В. Информационные технологии на железнодорожном транспорте. / В.ВЛковлев, Э.КЛецкий и др.. СПб.: ЛИИЖТ, 2000. -640 с.

139. Яковлев, В.В. Архитектура и технологии IBM с электронным сервером Z серии. / В.ВЛковлев, Э.КЛецкий и др.. СПб.: ЛИИЖТ, 2000. -640 с.

140. Яковлев, В.В. Информационная безопасность и защита данных в корпоративных сетях на железнодорожном транспорте. / В.В.Яковлев, А.А.Корниенко. СПб.: ЛИИЖТ, 2002. -400 с.

141. Ярославский, Л.П. Введение в цифровую обработку изображений./ Л.П. Ярославский. -М.: Сов. Радио, 1979.-312 с.

142. Ярославский Л.П. Методы цифровой голографии. / Л.П. Ярославский, Н.С. Мерзляков. -М.: Наука, 1977.-192 с.

143. Barlee, Т.С. Computation with Finite-Fields. / Т.С. Bartee, D.I. Schneider // Information and control. 1963.-№6.-P.79-98.

144. Berlekamp, E.R. On the solution of algebraic equations over finite fields. / E.R. Berlekamp, H. Rumsey, G. Solomon. // Information and control. 1967. - V.10. - P.553-564.

145. Blahut, R.E. Fast algorithms for digital signal processing. / R.E. Blahut.- Reading: Addison -Wesley, 1985.

146. Blahut, R.E. Transform Techniques for Error Control Codes. / R.E. Blahut // IBM J. Res. Develop. 1979. - V.23, №3. - P.205-213.

147. Bossen, D.C. A system solotion to memory soft error problem. / D.C. Bossen, M.V. Hsiao. // IBM J. Res. Develop. -1980. V.24, №3. - P.390-397.1 152. Chen, C.L. Formulas for the solutions of quadratic equations over GF(2m). / C.L. Chen // IEEE

148. Transaction on information theory. 1982. - IT-28, №5. - P.792-794.

149. Chen, C.L. Byte-orientad error-correcting codes for semiconductor memory systems. / C.L. Chen // IEEE Trans. Comput. 1986. - V.35, №7. - P. 646-648.

150. Computation providence. -1963. V.23, №105. - P.197-200.

151. Computer science and multiple-valued logic / D.Rine ed. Amsterdam, 1984. - 641 c.

152. Coppersmith, D. Fast evaluation of logarithms in fields of characteristic two. / D. Coppersmith. // IEEE Transaction on information theory. 1984. - V.IT-30, №4. - P.583-587.

153. Krouk, E. Error Correcting Coding and Security for Data Networks. Analysis of the Superchannel Concept. / E. Krouk, G.Kabatiansky, S. Semenov. John Weley & Sons, Ltd, 2005.-278 c.

154. Massey, J.L. Shift-register Synthesis and BCH Decoding./ J.L. Massey. // IEEE Trans. 1969.- V.IT 15, №1, P.l. - P.122-127.

155. Matull, J. Ic's for compact disc decoders. / J. Matull. //Electronic components and applications.- 1982.-V.4,№3.-P.131-141.

156. Mukaidono, M. A set of independent and complete axioms for a fuzzy algebra: Kleene algebra / M. Mukaidono // ISMVL (см. 43.), 1981. P.27-37.

157. Preparata, F.P. Computational Complexity of Fourier transforms over finite fields. / F.P. Preparata, D.V. Salvate. // Mathematics of computation. 1977. - V.31, №139.

158. Proceeding of the 4th -14th International Symposium on multiple-valued logic (ISMVL). N.Y. ' -1974-1984.

159. Rine, D. Computer science and multiple-valued logic./ D. Rine ed.- Amsterdam. 1984-641c.

160. Rosser, S. Many-valued logic / S. Rosser, A. Tuquette. Amsterdam, 1952. - 124 c.

161. Sundberg, C.E.W. Erasure and error decoding for semiconductor metories. / C.E.W. Sundberg // IEEE Trans. Comput. 1978. - V.C-27. - P.696-705.

162. Suqiyama, Y. Amethod for solving key equation for decoding Goppa codes. / Y. Suqiyama, M. Kasahara, S. Hirasawa/ // Information and control. 1975. - №27. - P. 87-99.

163. Trench, W.F. An algorithm for the inversion of finite toeplitz Matrices./ W.F. Trench. // Journal of the society for industrial and applied mathematics. 1964. - №12. - P.515-522.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00