Содержание к диссертации
Введение
1 Анализ математических моделей модулярных вычислительных структур, используемых в системах мобильной беспроводной связи 20
1.1 Аналитический обзор моделей вычислительных структур мобильной беспроводной связи 20
1.1.1 Системы связи на основе мобильных децентрализованных самоорганизующихся сетей 24
1.1.2 Особенности проектирования спутниковых системы связи 26
1.2 Основные математические модели вычислительных процедур, требуемых в мобильных системах связи, и их модулярная интерпретация 28
1.2.1 Математические модели методов цифровой фильтрации в системах мобильной беспроводной связи 31
1.2.2 Математическая модель выполнения алгоритма быстрого преобразования Фурье для мобильных систем связи 33
1.2.3 Математическая модель выполнения алгоритма быстрого вейвлет-преобразования 35
1.2.4 Математические модели пространственной фильтрации сигналов в системах передачи данных 37
1.2.5 Математические модели множественного доступа с кодовым разделением в базисе модулярной арифметики 39
1.2.6 Математические модели схем порогового доступа к данным в системе остаточных классов 1.3 Основные модели и алгоритмические структуры модулярной арифметики 47
1.4 Принципы построения помехоустойчивых средств мобильной связи на основе системы остаточных классов 52
1.5 Математические модели выполнения немодульных операций в системе остаточных классов
1.6 Постановка задачи исследования 62
1.7 Выводы по первой главе 64
2 Разработка математических моделей вычисления позиционных характеристик модулярного числа на основе центральной функции (ядра) 66
2.1 Разработка математических методов моделирования позиционных характеристик, основанных на функции ядра Акушского 66
2.2 Разработка математических методов моделирования позиционных характеристик, основанных на вычислении обобщенной функции ядра 79
2.3 Модификация численного метода определения позиционной характеристики на основе модифицированной Китайской теоремы об остатках
2.3.1 Оценка количества двоичных знаков приближенной дроби, требуемых для точного восстановления чисел по остаткам 85
2.3.2 Метод работы с дробными величинами для аппаратной реализации метода КТОм
2.4 Разработка численного метода вычисления позиционной характеристики на основе модифицированной функции ядра 95
2.5 Выводы по второй главе 112
3 Разработка математических методов моделирования немодульных операций на основе модифицированной функции ядра 114
3.1 Разработка математического метода моделирования восстановления позиционной формы числа на основе модифицированной Китайской теоремы об остатках 114
3.2 Разработка алгоритма выполнения операции сравнения модулярных чисел на основе традиционной и модифицированной форм функции ядра 122
3.3 Разработка алгоритма определения знака числа в системе остаточных классов на основе модифицированной функции ядра 132
3.4 Разработка алгоритма определения переполнения динамического диапазона избыточной системы остаточных классов на основе модифицированной функции ядра 134
3.5 Разработка алгоритмов обнаружения, локализации и исправления ошибок в коде системы остаточных классов на основе модифицированной функции ядра 137
3.6 Выводы по третьей главе 143
4 Экспериментальное исследование математических методов моделирования проблемных операций в СОК на базе ПЛИС архитектуры FPGA 145
4.1 Основные архитектурные особенности FPGA фирмы Xilinx 145
4.2 Аппаратная реализация обобщенной функции ядра 150
4.3 Реализация и моделирование операции восстановления позиционного представления числа на основе модулярного кода 158
4.4 Реализация и моделирование операции сравнения чисел по величине на основе представления числа в коде СОК 162
4.5 Выводы по четвертой главе 167
Заключение 169
Обозначения и сокращения 174
Список литературы 175
- Основные математические модели вычислительных процедур, требуемых в мобильных системах связи, и их модулярная интерпретация
- Разработка математических методов моделирования позиционных характеристик, основанных на вычислении обобщенной функции ядра
- Разработка алгоритма выполнения операции сравнения модулярных чисел на основе традиционной и модифицированной форм функции ядра
- Реализация и моделирование операции восстановления позиционного представления числа на основе модулярного кода
Введение к работе
Актуальность работы. Мобильные системы и сети являются сравнительно новым направлением разработок и исследований. Несмотря на это мобильные технологии сегодня прочно вошли в повседневную жизнь многих людей и являются важной частью современных информационных технологий. Мобильные технологии лежат в основе многих практических решений. Мобильные системы связи характеризуются использованием мобильных устройств, отличающихся полной или частичной автономностью. Связь устройств между собой и со стационарными станциями в таких системах осуществляется посредством беспроводных сетей. Автономность мобильных устройств накладывает определенные условия на их разработку. В частности, существуют достаточно жесткие ограничения на размеры устройств и их энергопотребление, которые зависят от конкретной задачи. Возникает необходимость разработки моделей основных вычислительных узлов мобильных систем, позволяющих с одной стороны избежать потери эффективности и качества выполнения всех требуемых процедур, а с другой – свести к минимуму общее энергопотребление получаемых устройств. Возникает противоречие в практике, для преодоления которого необходимо детально рассмотреть аспекты энергопотребления как с аппаратной, так и с алгоритмической точки зрения. Одним из наиболее востребованных аппаратных средств является программируемые логические интегральные схемы архитектуры FPGA. Их основной особенностью является возможность исполнения алгоритмов максимально параллельно за счет использования реконфигурируемой структуры вентилей и каналов FPGA. Важным методом организации параллелизма является использование системы остаточных классов (СОК).
Значительный научный вклад в теорию модулярных вычислений и их приложений внесли отечественные и зарубежные исследователи: И.Я. Акушский, Д.И. Юдицкий, В.М. Амербаев, А.А. Коляда, А.И. Галушкин, И.Т. Пак, М.В. Синьков, В.А. Торгашев, Н.И. Червяков, И.А. Калмыков, О.А. Финько, Д. Свобода, N. Szabo, M. Valach, H.L. Garner, A.S. Fraenkel, A. Huang, B. Purhami, W. Ienkns, H. Krisha, A. Omondi, A. Premkumar, I. Ramires, A. Curcik, L.Yang, D. Zhang, P Steffan, G. Pirlo, L. Sousa и другие.
Как показано во многих современных исследованиях, использование СОК позволяет снизить мощность устройств, в сравнении с традиционным двоичным кодированием в дополнительном коде. Использование при этом СОК совместно с ПЛИС позволяет снизить вычислительную сложность и занимаемую площадь устройства. Особую эффективность СОК показала в проектировании устройств цифровой обработки сигналов. Особенностью СОК является возможность помехоустойчивого кодирования информации на ее основе, что является важной чертой при проектировании устройств для беспроводных сетей.
Однако в СОК существует целый ряд операций, реализация которых оказывается затруднительной. Операции такого типа называются
немодульными и связаны с определением позиции числа на числовой прямой, что труднодостижимо в СОК как в непозиционной системе счисления. Важнейшими немодульными операциями являются операции перевода чисел из СОК в позиционную систему счисления и сравнения чисел по величине, необходимое для организации контроля ошибок в коде. Тщательного исследования требует вопрос об оптимальном выборе параметров немодульных операций и выработке общего метода, позволяющего максимально быстро и с малым расходом энергии выполнять немодульные операции. Немодульные операции в СОК сложны по своей природе так как требуют связи между вычислительными каналами по каждому модулю. Выполнение немодульных операций связано с вычислением некоторой позиционной характеристики, позволяющей однозначно определить позицию некоторого числа, представленного в СОК, относительно любого другого числа, представленного в той же системе. Позиционные характеристики зависят от каждого конкретного метода и представляют собой функции, зависящие от значений остатков числа по модулям СОК. Позиционные характеристики разнообразны и сложны в изучении, что делает затруднительным их теоретическое сравнение и анализ. В отсутствии общей методологии и единой системы моделей позиционных характеристик заключается теоретическое противоречие, преодоление которого требуется для определения наиболее эффективных подходов к реализации немодульных операций. Важной задачей является выработка общей теории, позволяющей реализовывать их в едином алгоритмическом базисе и оценивать эффективность имеющихся подходов. Предлагается разработать и ввести в использование обобщенную позиционную характеристику. Задачей исследования является оптимизация и разработка методов и моделей реализации вычисления позиционной характеристики на основе обобщенной позиционной характеристики и выбор ее оптимальных параметров. Разработка универсального подхода позволит выработать стратегию проектирования систем мобильной связи, основанных на применении СОК. Для разработки и моделирования используется FPGA фирмы Xilinx.
Целью диссертационного исследования является снижение энергопотребления систем мобильной связи, основанных на системе остаточных классов.
Объект исследования – системы мобильной беспроводной связи.
Предмет исследования – математические модели, методы и алгоритмы вычислительных средств мобильных систем связи, основанных на модулярной арифметике.
Научная задача – разработка новых математических моделей вычислительных устройств мобильных систем связи, численных методов вычисления немодульных операций на основе различных форм обобщенной позиционной характеристики, а также комплексы программ, применение которых позволит снизить энергопотребление.
Для решения поставленной общей научной задачи была произведена ее декомпозиция на ряд частных задач:
-
Анализ математических моделей и алгоритмов вычислительных процедур, используемых в системах мобильной связи, а также особенностей их реализации в модулярном базисе.
-
Развитие и обобщение математических моделей позиционных характеристик чисел, представленных в системе остаточных классов; разработка модели обобщенной позиционной характеристики; выработка критериев эффективности позиционных характеристик общего вида и выделение методов математического моделирования новых позиционных характеристик.
-
Разработка и модификация численных методов вычисления позиционных характеристик числа на основе функции ядра (ФЯ) Акушского. Применение принципов обобщенной позиционной характеристики для модификации существующих подходов, включая функцию ядра и ее частный случай – диагональную функцию. Выработка методов и алгоритмов выполнения модифицированных функций ядра (МФЯ) для эффективного вычисления позиционных характеристик чисел.
-
Разработка новых моделей и алгоритмов вычисления позиционной характеристики на основе модифицированных функций ядра для исследования математических моделей таких немодульных операций системы остаточных классов как сравнение чисел, представленных в модулярном коде, определение знака числа, определение переполнения динамического диапазона и локализация ошибочного разряда и коррекция ошибок.
-
Разработка моделей архитектуры вычислительных устройств вычисления позиционных характеристик, основанных на модифицированных функциях ядра.
-
Создание комплекса программ для экспериментального исследования на языке VHDL для FPGA в среде Xilinx Vivado 2015 функциональных устройств системы мобильной связи на базе СОК.
Методы исследования включают использование математического аппарата высшей алгебры, теории чисел, теории алгоритмов, численных методов, теории надежности, теории модулярной арифметики, математического моделирования и системного анализа.
На защиту выносятся следующие научные результаты:
-
Математическая модель обобщенной позиционной характеристики как универсального средства моделирования позиционных характеристик чисел, представленных в системе остаточных классов.
-
Численные методы вычисления позиционных характеристик, основанных на МФЯ, учитывающие особенности функционирования аппаратных вычислительных средств.
-
Математические модели и алгоритмы выполнения базовых немодульных операций восстановления позиционного представления чисел
на основе кода СОК и сравнения модулярных чисел, а также основанных на них операций определения знака числа, определения переполнения диапазона представления чисел и операций обнаружения, локализации и исправления ошибок в коде СОК.
-
Разработанные модели аппаратной архитектуры устройств вычисления позиционных характеристик модулярного кода на основе моделей обобщенной позиционной характеристики и моделей модифицированных функций ядра.
-
Комплекс программ моделирования основных блоков системы мобильной связи, основанной на СОК, на базе FPGA.
Научная новизна:
-
Разработана обобщающая математическая модель вычисления позиционных характеристик числа, позволившая не только оценить существующие методы с различных сторон, но и предложить наиболее эффективные подходы и пути их оптимизации.
-
Разработаны математические модели новых позиционных характеристик чисел, представленных в СОК, основанных на модификации ФЯ Акушского и модификации Китайской теоремы об остатках.
-
На основе разработанных моделей предложены новые численные методы вычисления характеристик чисел и выполнения немодульных операций.
-
Методы и алгоритмы выполнения немодульных операций в системе остаточных классов, основанные на использовании разработанных численных методов.
-
Комплексы программ, позволяющие производить моделирование разработанных методов и алгоритмов и их оценку на базе FPGA.
Достоверность результатов обеспечивается корректным и обоснованным применением методов математического моделирования и строгостью проводимых математических доказательств. Справедливость выводов относительно эффективности предложенных моделей и методов подтверждена математическим моделированием в базе FPGA фирмы Xilinx.
Практическая ценность результатов исследования состоит в возможности реализации части функциональных устройств, используемых в мобильных системах связи, основанных на СОК, на базе разработанных подходов и методов, что способствует снижению энергопотребления. Разработан универсальный метод выполнения операций в СОК, позволяющий расширить возможности использования системы остаточных классов при проектировании мобильных устройств и новых беспроводных сетей. Разработанные программные продукты и аппаратные решения, зарегистрированные в соответствующем порядке, способствуют оптимизации эксплуатационных возможностей мобильных устройств. Предложенные технические решения по разработке узлов вычислительной аппаратуры на базе модулярной арифметики могут лечь в основу постановки перспективной опытно-конструкторской разработки.
Внедрение. Результаты диссертационного исследования используются в учебном процессе в СКФУ на кафедре прикладной математики и математического моделирования в дисциплинах «Арифметические, логические и алгоритмические основы вычислительной техники», «Дискретная математика» и «Основы вычислительной математики, математического и информационного моделирования», а также при разработке лабораторных работ по курсу «Проектирование конечных автоматов в системе LabVIEW», что подтверждено Актом об использовании результатов работы в учебном процессе №96 от 29.01.2016. Основные научные результаты использованы в опытно-конструкторских разработках ООО «Медицина-ИТ» (Акт №48 от 19.02.2016) и в разработках ООО «Инфоком-С» при реализации научного проекта «Разработка кроссплатформенной технологии построения мобильных приложений с заданными контурами интеграции для повышения функциональной и ресурсной эффективности корпоративных информационных систем» (Акт №21 от 25.02.2016). Кроме того, ряд результатов работы был использован при выполнении научно-исследовательских работ в базовой части государственного задания СКФУ №2563 «Проблемы интеграции параллельной компьютерной алгебры и искусственных нейронных сетей в области информационно-коммуникационных технологий».
Апробация работы. Основные результаты работы были представлены
на 8-й Международной конференции «Application of Information and
Communication Technologies» (г. Астана, Казахстан, 2014 г.), Международной
конференции «Engineering & Telecommunication» (г. Долгопрудный, 2014 г.),
Вьетнамо-российской международной конференции (г. Ханой, Вьетнам,
2015 г.), 2-й Международной конференции «Afro-European Conference for
Industrial Advancement» (г. Париж, Франция, 2015 г.), Международной
конференции «IEEE North West Russia Section Young Researchers in Electrical
and Electronic Engineering Conference» (г. Санкт-Петербург, 2016 г.),
Всероссийской конференции «Проблемы математики и радиофизики в
области информационной безопасности» (Ставрополь, 2012 г.),
Международной конференции «Высокопроизводительные вычисления –
математические модели и алгоритмы», посвященной Карлу Якоби
(г. Калининград, 2013 г.), Всероссийской конференции
«Высокопроизводительные параллельные вычисления на кластерных системах», (г. Нижний Новгород, 2013 г.), Международной научно-практической конференции молодых ученых «Морально-этические аспекты и темпорально-экологические императивы инвенционного процесса генерации новых научно-технических знаний» (г. Ставрополь, 2014 г.), Международной научно-технической конференции «Современные технологии в нефтегазовом деле» (г. Уфа, 2014 г.), конкурса инновационных проектов в области суперкомпьютерных технологий в рамках форума «Суперкомпьютерные технологии в образовании, науке и промышленности 2013» (победитель, г. Нижний Новгород, 2013 г.), конкурсе инновационных
проектов в области информационной безопасности «ИнфоТеКС – Академия» с проектом «Технология защищенного облачного хранения на основе разделения секрета» (победитель, 2014 г.), конкурсе «У.М.Н.И.К. Российской Федерации» в рамках Всероссийской научно-практической конференции «Инновационные идеи молодежи Ставропольского края – развитию экономики России» с проектом «Разработка аппаратной части модулярной криптографической системы с открытым ключом для FPGA» (победитель, г. Ставрополь, 2014 г.), конкурсе программных проектов компании Майкрософт в рамках Летней школы Майкрософт «Исследуем в облаке» (призер, г. Москва, 2014 г.).
Публикации по теме диссертации. Основные результаты исследования отражены в 28 работах, среди который имеются статьи в научных изданиях, входящих в перечень ВАК Министерства образования и науки, а также входящих в системы индексирования научных работ Scopus и Web Of Science.
Личный вклад соискателя. Все изложенные в работе результаты исследований получены при непосредственном участии автора. Авторским вкладом являются разработка методов, моделей и алгоритмов вычисления позиционных характеристик на основе различных форм обобщенной функции ядра, разработка численных методов выполнения немодульных операций, разработка программного комплекса моделирования функциональных устройств системы связи, основанной на системе остаточных классов.
Структура диссертации. Диссертационная работа состоит из введения, 4-х глав, заключения, списка сокращений и обозначений и списка использованной литературы, содержащего 108 наименований. Основная часть работы содержит 182 страниц машинописного текста. Работа содержит 39 рисунков, 6 таблиц и 7 приложений.
Основные математические модели вычислительных процедур, требуемых в мобильных системах связи, и их модулярная интерпретация
Спутниковые технологии дают уникальные возможности для многих отраслей науки и техники и в некоторых сферах жизни стали незаменимы. Однако основной частью любого спутника является система связи, от качества которой зависят возможности аппарата в целом. В независимости от того, какую задачу решает спутник, система связи занимает ключевое место так как связывает спутник с наземной станцией управления и позволяет получать команды и передавать результаты работы. Особое место занимают спутники связи, являющиеся фактически ретрансляторами сигналов с одной земной станции на несколько других.
Искусственный спутник Земли [71, 82] представляет собой автономное устройство, вращающееся вокруг Земли по геоцентрической орбите. Особенности использования спутников накладывают ряд ограничений на их конструктивные особенности. В частности, автономность подразумевает отсутствие возможности прямого вмешательства человека для исправления неполадок. В условиях автономности и удаленности от человека единственным источником энергии является Солнце, что приводит к необходимости значительного снижения энергопотребления. Мощность излучения Солнца на орбите Земли составляет 1367 Вт/м2, что позволяет получать примерно от 100 до 130 Вт/м2 поверхности солнечных батарей (при КПД 8-13 %). Размер солнечной батареи зависит от размера спутника.
Кроме того, устройство должно быть максимально легким и компактным для достижения лучшей маневренности и меньшего потребления энергии. Данный факт приводит в том числе к необходимости снижения количества логических элементов печатных плат, задействованных в работе спутника. В таких условиях резко возрастает потребность в надежности используемых устройств и алгоритмов так как повышается цена каждого факта приёмопередачи. Важным фактором работы спутника является его удаленность от земных станций и связанные с ней задержки между отправлением и приемом сигнала. При достаточно большой высоте возрастает латентность сигнала, что делает крайне трудоемким повторную отправку данных и обратную связь с передатчиком. При этом беспроводная природа связи приводит к дополнительным интерференциям с наземными сигналами и помехам за счет удаленности приемников и передатчиков.
В обозначенных условиях критически важным является каждый компонент спутника. Главными компонентами спутника являются его конструкционные элементы, система управления положением, система питания, система телеметрии, система трекинга команд, приемопередатчики и антенна. Устойчивость и нужная ориентация антенны поддерживается системой стабилизации. Размер и вес спутника ограничены в основном возможностями транспортных средств, требованиями к солнечным батареям и объему топлива для жизнеобеспечения спутника. Телеметрическое оборудование спутника используется для передачи на Землю информации о его положении. В зависимости от назначения спутника он может содержать дополнительные системы и устройства, обеспечивающие его функциональность.
Важным назначением спутниковых систем является ретрансляция приходящего сигнала, что называется bent-pipe (BP) архитектурой [106]. Основным компонентом таких спутников являются BP-транспондеры, представляющие собой устройства, преобразующие и усиливающие сигнал на входной частоте в выходной сигнал. BP-транспондеры представляют собой аналоговые устройства, однако особого внимания заслуживают спутники связи, основанные на цифровых технологиях. Системы такого рода получают в последние годы все большее распространение и в случае ретрансляции сигнала транспондеры для них должны обладать большим функционалом, чем традиционные BP-транспондеры. Благодаря простоте конструкции и надежному функционированию, BP-транспондеры широко используются в спутниковых системах связи, особенно с учетом того обстоятельства, что полезная нагрузка и энергопотребление на борту ограничены.
1.2 Основные математические модели вычислительных процедур, требуемых в мобильных системах связи, и их модулярная интерпретация
Цифровая обработка сигналов, необходимая для функционирования цифровых мобильных сетей, включает в себя формирование луча для направленной передачи и приема сигнала, КИХ-фильтры и фильтрации сигналов, быстрое преобразование Фурье для организации частотно-временных преобразований выборки данных, которую в некоторых случая эффективно заменить на применение вейвлет-преобразования, обеспечение отказоустойчивости и так далее. Кроме того, важной задачей при передаче сигналов является организация множественного доступа.
Устройства, применяемые в мобильных системах связи, требуют максимально низких энергопотребления и занимаемой площади с одновременно достаточно высокой скоростью работы. Для достижения заданной цели могут быть применены различные подходы, одним из которых является использование модулярной арифметики в качестве вычислительной основы алгоритмов. В данном разделе рассмотрим особенности реализации базовых устройств цифровой мобильной связи на основе их математических моделей. При этом покажем, как именно модулярная арифметика может быть использована в данных задачах и как именно части цифровых устройств мобильной системы связи могут быть реализованы в модулярном коде.
Модулярный код подразумевает представление обрабатываемых данных в системе остаточных классов. В общем смысле, под представлением числа X в системе остаточных классов (СОК) с модулями p1,p2,...,pn понимается записть числа в виде X = (xг, x2,..., xn), где xi = X mod pi для всех i = 1,2,..., n с условием, что 0 X P = pх-p2-...-pn. Числа, представленные в СОК, в ряде случаев можно обрабатывать параллельно, учитывая отсутствие переносов между разрядами СОК, характерное для непозиционных систем. При этом так как xi « X для всех i, то обработка в каждом параллельном канале существенно упрощается. Именно эти особенности модулярного представления лежат в основе преимуществ модулярного кода при проектировании вычислительных средств различной природы.
Если рассматривать потребление энергии в системах цифровой связи, то возможны следующие уровни оптимизации: алгоритмический уровень, уровень архитектуры, арифметический уровень, уровень реализации и технологический. Система остаточных классов может быть использована на всех уровнях, кроме технологического. При этом основное влияние СОК можно отметить при оптимизации энергопотребления системы на арифметическом уровне. Отсутствие распространения переноса между различными параллельными каналами обработки данных позволяет обеспечить две фундаментальные характеристики системы остаточных классов для реализации устройств на ее основе: - простые регулярные структуры;
Разработка математических методов моделирования позиционных характеристик, основанных на вычислении обобщенной функции ядра
Основной идеей помехоустойчивого кодирования на основе СОК является внедрение избыточности за счет добавления дополнительных модулей к системе оснований.
Пусть задана упорядоченная система взаимно простых оснований р1,р2,...,рп, в которой к первых оснований являются информационными, а основания рк+1,рк+2,...рп - контрольными. Информационные основания образуют рабочий диапазон представления СОК: Рк=р1р2...рк. Различные величина и количество контрольных оснований СОК придают данному способу помехоустойчивого кодирования различные свойства, включая количество и кратность ошибок, которые данный код способе обнаруживать и исправлять.
Пусть в данной системе представлено число А = (а1,а2,...,ап). Фактически оно заключает в себе информацию, определяемую в диапазоне [0,Pk). Требуется определить, ошибочно ли оно, и по возможности исправить ошибку. Обнаружить ошибку можно, сравнив число А со значением Рк. Если выполняется неравенство А Рк, то ошибки нет, иначе - в одном или нескольких каналах произошло искажение данных [9]. Кроме решения задачи обнаружения ошибки в СОК существуют задачи локализации и исправления ошибок.
На сегодняшний день наиболее используемыми являются два метода коррекции ошибок в системе остаточных классов. Один из них - это табличный метод, основанный на расширении системы рабочих оснований до системы контрольных оснований [9, 40]. Второй метод - это метод проекций [10, 39]. Каждый их данных методов обладает своими специфическими особенностями. Табличный метод связан с вычислением синдрома ошибки в коде СОК и предполагает расширение диапазона представления чисел. Рассмотрим систему информационных оснований рг,р2,...,рк. Число А в ней можно представить остатками аг,а2,...,ак. Расширяя данную систему на модули рш,рк+2,...,рп, получим числа a k+l,ock+1 ,...,а п. Если данные числа совпадают с остатками числа А по контрольным основаниям в исходном представлении, то ошибки в нем нет. Вычислим синдромы ошибок: Р1=аш-а ш(шАрк+1) где і = 1,2,...,п-к. На основании полученных синдромов из специальной коррекционной таблицы выбирается константа ошибки [40]. Эта константа показывает, по какому основанию произошла ошибка и вычисляется таким образом, чтобы при ее сложении с контролируемым числом имевшая место ошибка устранялась.
Сложность реализации данного подхода зависит от реализации метода расширения диапазона представления чисел. Данная операция является немодульной в СОК и ведет к сложным вычислениям. Кроме того, применение данного метода накладывает на кодовые комбинации особое ограничение: контрольные разряды должны быть надежны так как данный подход не предполагает их непосредственного контроля. Это можно обеспечить путем внедрения дополнительного помехоустойчивого кодирования для контрольных оснований за счет внедрения дополнительной избыточности. Данное обстоятельство делает табличный метод сложнореализуемым для систем мобильной связи.
Метод проекций для обнаружения ошибок в коде СОК в свою очередь заключается в следующем. Под i-ой однократной проекцией числа А = (а1,а2,...,ап) понимается представление числа A в сокращенной системе остаточных классов, представляющей собой исходную систему, из которой исключено i-е основание. Представление получается простым вычеркиванием i-ого остатка в исходной записи числа. Следовательно, число разрядности n имеет п однократных проекций. Аналогичным образом вводятся многократные проекции, за исключением того, что в этом случае система оснований сокращается сразу на несколько модулей. В случае если система оснований содержит лишь один контрольный модуль, метод локализации состоит в следующем. Находятся все проекции числа А = (а1,а2,...,ап): А1=(а2,а3,...,ап), А2=(а1,а3,...,ап), An=(a1,a2,...,(Xn_1). Далее с помощью одного из методов сравнения проверяется условие для каждой полученной проекции: At Pk, i = 1,2,...,п. Если условие не выполняется, то остаток по данному модулю считается правильным, в случае выполнения условия считается, что ошибка произошла по данному основанию [39]. Данный подход легко расширяется для случая нескольких контрольных оснований.
Обнаруженный ошибочный разряд исключается из кода СОК и дальнейших преобразований. Если же данный разряд необходим, то производится однократное расширение системы оснований СОК. Основным минусом данного подхода является большое количество операций сравнения чисел в системе остаточных классов. Как было отмечено ранее, данная операция является немодульной и сложнореализуемой для СОК.
Система остаточных классов с применением избыточности является одной из наиболее используемых альтернатив позиционным помехоустойчивым кодам [53]. Сочетание арифметических особенностей СОК и его высоких коррекционных свойств делает данную систему подходящей для создания на ее основе высокоэффективных систем связи.
Разработка алгоритма выполнения операции сравнения модулярных чисел на основе традиционной и модифицированной форм функции ядра
Как было отмечено ранее, вычисление позиционной характеристики на основе КТО фактически означает перевод числа в позиционную систему счисления. Задачей большинства исследований в области немодульных операций является упрощение вычислений, задаваемых КТО. При этом функция к КТО представляет собой обобщенную функцию ядра.
Один из самых продуктивных подходов к упрощению вычислений на основе КТО заключается в приближенном ее вычислении. За счет изменения подхода к вычислению значений X можно добиться желаемого эффекта ускорения вычислений, сведя их от промежутка [0,P) к некоторому промежутку [0,2N). Для этого рассмотрим далее модификацию Китайской теоремы об остатках с применением дробных величин (приближенный метод) [25, 70], которую в дальнейшем будем обозначать КТОд, как обобщенную функцию ядра и монотонную позиционную характеристику. Все числа в СОК с модулями p1,p2,---,pn расположены в промежутке где P = p1p2-...-pn - диапазон СОК. Если обе части формулы (2.2.2) разделить на P, то получим соотношение P пКТОд (X) = X = — \Pi 1 T—pixi i=1 p i i=1 (2.3.1) где операция означает отбрасывание целой части числа, числа kt= 2, і = 1,2,..., л, (2.3.2) Pi являются константами СОК и могут быть рассчитаны заранее. При этом значение каждой суммы будет находиться в промежутке [0,1], что дает достаточно информации для оценки знака и величины числа, представленного в СОК [35].
Такой переход позволяет заменить точное число его дробной характеристикой, которая является строго возрастающей функцией. При этом имеется важная возможность регулирования точности представления в зависимости от имеющихся ресурсов и поставленной задачи. Само число X может быть найдено по формуле Х = . (2.3.3)
Подход, основанный на формулах (2.3.1) и (2.3.3) позволяет существенно упростить вычисления. Главным преимуществом такого метода является отсутствие вычислений по большому модулю Р. Данный вид ия с остатком, которая является сложно реализуемой. Использование этой операции влечет звычислений приводит для большинства вычислительных устройств к выполнению операции делена собой большие аппаратные и временные затраты.
Однако реализация данного метода приводит к необходимости решения ряда проблем. Так как р{ - простые целые числа, то, согласно (2.3.2), числа к{
представляют собой бесконечные двоичные периодические дроби (во всех случаях, кроме р{=2). Однако в случае машинных вычислений мы можем
воспользоваться лишь ограниченной точностью, что требует округления или отбрасывания младших бит дроби. Определение количества бит, требуемых для точных расчетов - важная задача для реализации данного метода на FPGA. В работе [74] приближенная форма КТО используется для операций определения знака числа и деления в СОК.
При этом для анализа алгоритма предлагается использовать &nb битные дроби, где под Ъ понимается количество бит, требуемых для представления каждого модуля СОК, под п - количество оснований СОК. Там же указано, что точные вычисления могут быть обеспечены путем использования &nb + \og2n битных дробей. Однако данная оценка является недостаточной и приводит к ошибкам в вычислениях позиционного значения числа. В качестве примера рассмотрим двухмодульную СОК с набором модулей А=29, р2=Ъ\. Для нее Р = Ю9 =1110000011 2, п = 2 и Ь = 5. Согласно оценкам в [74], необходимо использовать nb+ {hg2 п\ = 10 + 2 = 12 двоичных знаков после запятой. Основываясь на этом, вычислим к, и к2: -1 р2 p1 зг1 p1 = — = 0,10000100 0111 = — = 0,01111011 1110 -1 p2 29-1 р2 31 Пусть Х = 83, % =Xmodj71 =25 = 110012, х2 =Xmodp2 =21 = 101012. Тогда по формуле (2.3.1): Х = 0,10000100 01112 -110012 + 0,01111011 11102-10101 =0,0001100001 012 и Х = ХР = 0,0001100001 012-1110000011 2 =1010101,0110000011 112 «85. Полученное значение X не совпадает с исходным, равным 83. В рассматриваемом случае 12 знаков после запятой недостаточно для точного восстановления числа. Следовательно, оценка, предложенная в [74], требует уточнения.
Другой проблемой КТОд является факт использования дробных чисел для расчетов. Вычисления с дробными числами существенно усложняют принципиальную схему устройства.
Далее рассмотрим предлагаемые методики решения проблем реализации метода, обозначенного ранее КТОд. Новый метод будем называть модифицированной Китайской теоремой об остатках или КТОм. Основная идея модификации заключается в следующем: 1. Максимально ограничить разрядность каждой из констант (2.3.2) до числа N так, чтобы вычисления (2.3.1) - (2.3.3) производились верно. 2. Каждую вещественную константу (2.3.2) умножить на 2N. 3. Округлить каждое полученное число вверх, то есть до следующего целого числа; 4. Производить все вычисления в кольце классов вычетов по модулю 2м, что можно реализовать ограничив разрядность вычислений до N бит и отбрасывая все старшие биты.
Данные действия позволят получить метод, хорошо реализуемый аппаратно с одной стороны и требующий мало ресурсов с другой. Разобьем переход от КТОд к КТОм на два этапа. В первом получим количество N бит дробной части, требуемого для точного восстановления позиционного значения числа. Во втором переведем вычисления от вещественных чисел к целым для эффективной аппаратной реализации.
Реализация и моделирование операции восстановления позиционного представления числа на основе модулярного кода
Операция сравнения чисел является важной составной частью многих алгоритмов в СОК, в частности - алгоритмов цифровой фильтрации. Традиционным подход для решения проблемы сравнения модулярных чисел связан с переводом в позиционную систему счисления - как в традиционную бинарную, так и в ОПСС. Для многих алгоритмов этот факт служил существенным ограничением, приводящим к невозможности их реализации на основе СОК, так как все преимущества СОК как непозиционной системы не могут оказаться полезными на практике, если в ряде случаев приходится производить перевод в позиционную систему счисления. При большом количестве операций перевода выгоднее оставаться в позиционной и пожертвовать параллелизмом и другими свойствами СОК.
Подход, основанный на обобщенной функции ядра, позволяет уйти от трудностей, связанных с переводом в позиционную форму и подробно описанных ранее, и сосредоточить вычисления только на позиционной характеристике числа. Таким образом можно добиться минимизации вычислительных ресурсов, необходимых для сравнения чисел, в частности разрядности операций и их количества.
Рассмотрим далее алгоритм сравнения чисел, основанный на традиционной функции ядра, в основу которого легла теорема 2.1.1. Согласной данной теореме промежутки, в которых функция ядра сохраняет значение, отмечены тем, что в них xi Ф 0 для таких i, для которых соi Ф0. Следовательно, значения xi для таких i возрастают на данном промежутке. Данное свойство ложится в основу следующего алгоритма сравнения чисел. Рассмотрим СОК с модулями p 1,p2,...,pn и диапазоном P. Пусть функция ядра (2.1.1) по некоторому модулю CP определяется неотрицательными 123 коэффициентами со1,со2,---,соп и пусть для некоторого к сок Ф 0, а (0}.= 0 для всех j = 1,2,..,к-1. При этом СОк есть первый не равный нулю коэффициент. Теорема 2.1.1 позволяет строить монотонную функцию ядра, подходящую для операции сравнения. Основная особенность таких функций заключается в отсутствии отрицательных весов щ. Однако функции ядра, согласно той же теореме, не могут быть строго монотонны, следовательно алгоритм сравнения будет состоять из двух этапов. На первом этапе сравниваются значения функции ядра, на втором - по одному из остатков. Так как согласно модели (2.1.11) функция ядра не изменяется при хг, = 0 в случае щ = 0, то сравнивать на втором этапе необходимо остатки по модулю с ненулевым весом сок.
Алгоритм 3.2.1: Сравнение чисел, представленных в СОК, с использованием функции ядра с неотрицательными коэффециентами. 1) Вход: Х = (х1,х2,---,хй), Y = (y1,y2,—,yn) - числа в СОК 2) Шаг 1: Вычислить С(Х) и C(Y) 3) Шаг 2: a) Если С(Х) C(Y), то X Y b) Если С(Х) C(Y), то X Y c) Если C(X) = C(Y), то і) если хк ук, то X Y ii) если хк ук, то X Y iii) если хк = ук, то X = Y Отметим, что самым эффективным путем использование данного алгоритма является выбор в качестве функции ядра функцию Ср(Х), которая является традиционной функцией ядра с минимальным диапазоном СР=Рп=Р/рп. При этом для данной функции в предложенном алгоритме минимальным ненулевым весом будет (Оп, то к = п. Рассмотрим далее пример выполнения данного алгоритма.
Пусть задана система остаточных классов с основаниями P1=3, р2=4 и р3=5. Построим для данной системы С(Х) с весами соответственно =0, со2=0 и со3=1. При этом Р = 60, СР=Рп = 12, = 40, 2=45, В3=36. Рассчитаем константы kt; к1=С(В1) = 8, к2=С(В2) = 9, к3=С(В3) = 7. Пусть заданы числа Х = 19 = (1,3,4), 7 = 20 = (2,0,0) и Z = 21 = (0,1,1) . Вычислим на основе модели (2.1.8): С(Х) = 8-1 + 9-3 + 7-412=3 С(7) = 8-2 + 9-0 + 7-012 =4 C(Z) = 8-0 + 9-1 + 7-112=4 Так как С(Х) C(Y) и С(Х) C(Z), то, следовательно, X Y и X Z, что соответствует их порядку в позиционной системе счисления. Однако C(Y) = C(Z), что приводит к необходимости дополнительного сравнения по одному из модулей. В данном случае единственным модулем, для которого (0t t 0, является модуль с номером п. Основываясь на том, что ІГІ = 0 Izl = 1, можно Рп Рп сделать вывод, что Y Z. Отметим, что использование для дополнительного сравнения остатков по другим модулям приводит к ошибкам. Конец примера.
Аппаратная схема устройства, отвечающего алгоритму 3.2.1, предполагает наличие блока сравнения двоичных чисел. Операции такого типа поддерживаются всеми существующими вычислительными устройствами, включая FPGA. Будем использовать на практике традиционный блок сравнения чисел, изображенный на рисунке 3.2.1. Пусть требуется сравнить числа А и В по величине. Блок СОМР на рисунке 3.2.1 реализует метод сравнения двоичных чисел и имеет три возможных исхода в зависимости от результата работы. Данный блок ложится в основу разрабатываемых алгоритмов сравнения. На его вход подаются многоразрядные двоичные числа А и В, а каждый из трех одноразрядных выходов, соответствующих трем возможным результатам сравнения, принимает значение 1 или 0 в зависимости от исхода операции.
Схема работы алгоритма сравнения, основанного на функции СР(Х) представлена на рисунке 3.2.2. В результате ее работы соответствующий выход из трех возможных одноразрядных выходных сигналов, примет значение 1, все остальные примут значение 0. Сама схема состоит из параллельного вычисления С(Х) и C(Y), значения которых сравниваются между собой. В случае равенства, параллельно с первым сравнением С1 производится дополнительное сравнение С2 остатков с номером к для произвольного случая и П для Ср . Финальной стадией схемы являются мультиплексоры 2:1 M1 и М2, каждый из которых отвечает за свой результат. В случае, если при основном сравнении С1 С(Х) Ф C(Y), мультиплексоры M1 и М2 выведут на выход результат сравнения С(Х) и C(Y): X Y в случае с (X) C(F) для M1 и X Y в случае С(Х) C(F) для М2. Если же с(X) = C(Y), то необходимо учесть результат дополнительного сравнения С2: X Y в случае хк ук для M1 и X Y в случае хк ук для М2. Выход, отвечающий случаю X = Y примет значение 1 только в результате одновременного равенства с (X) = С (У) и хк = ук.