Содержание к диссертации
Введение
ГЛАВА 1. Анализ современных методов и алгоритмов помехоустойчивого кодирования 16
1.1. Автоматизированные системы для разработки кодеков помехоустойчивых кодов 16
1.2. Классификация помехоустойчивых кодов 20
1.3. Систематические помехоустойчивые коды 25
1.4. Выбор помехоустойчивого кода 39
1.5. Цель и задачи исследования 42
1.6. Основные результаты и выводы по главе 43
ГЛАВА 2. Алгоритмическое обеспечение системы для разработки кодеков 45
2.1. Алгоритм функционирования системы для разработки кодеков 45
2.2. Выбор образующего полинома 49
2.2.1. Алгоритм поиска образующего полинома 50
2.2.2. Компьютерный эксперимент по поиску образующих
полиномов 52
2.2.3. Обсуждение результатов 56
2.3. Алгоритмы деления полиномов в арифметике по модулю два 59
2.3.1. Классический алгоритм деления 59
2.3.2. Алгоритм Башина 60
2.3.3. Двусторонний алгоритм 63
2.3.4. Матричный алгоритм 66
2.3.5. Задача исследования эффективности алгоритмов деления полиномов по модулю два 70
2.3.6. Анализ результатов компьютерного эксперимента 75
2.4. Алгоритм функционирования кодека 75
2.4.1. Алгоритм функционирования кодера з
2.4.2. Алгоритм функционирования декодера 79
2.4.3. Компьютерный эксперимент по исследованию
эффективности алгоритмов функционирования кодека 85
2.4.4. Анализ результатов эксперимента 89
2.5. Методы уменьшения требуемого объёма памяти при аппаратной реализации кодека с использованием таблиц 90
2.5.1. Метод запоминания позиций ошибок 90
2.5.2. Метод составления словаря 91
2.5.3. Метод выборки исправляющей комбинации 92
2.5.4. Рекомендации по использованию методов уменьшения требуемого объёма памяти 96
2.6. Основные результаты и выводы по главе 97
ГЛАВА 3. Программное обеспечение системы magdiv для разработки кодеков 99
3.1. Описание ПО системы для разработки кодеков помехоустойчивых полиномиальных кодов 99
3.1.1. Требования кПО системы MagDiv 99
3.1.2. Структура ПО системы MagDiv 101
3.1.3 Описание шаблона кодека 107
3.2. Библиотека классов для полиномиальных вычислений 108
3.2.1. Общее описание разработанной библиотеки классов PCodeWords 108
3.2.2. Базовый класс polynom 108
3.2.3. Дочерний класс codeword 109
3.2.4. Анализ результатов 110
3.3. Программное обеспечение для поиска образующих полиномов 111
3.3.1. Требования к ПО для поиска образующих полиномов 111
3.3.2. Описание класса polynom Jjnder 112
3.3.3. Алгоритм функционирования ПО для поиска образующих полиномов 113
3.3.4. Описание пользовательского интерфейса ПО поиска образующих полиномов 114
3.4. Основные результаты и выводы по главе 115
ГЛАВА 4. Результаты практического применения программного обеспечения системы MAGDIV 117
4.1. Задача повышения достоверности передачи данных в системе
управления процессом бурения 117
4.1.1. Постановка задачи 117
4.1.2. Создание файлов проекта кодека для его реализации на ПЛИС 118
4.1.3. Создание файлов проекта кодека для его программной реализации на микроконтроллерах 124
4.2. Задача повышения достоверности передачи данных в инклинометрической системе для буровой установки 128
4.2.1. Постановка задачи 128
4.2.2. Создание файлов проекта кодека с помощью ПО системы MagDiv 130
4.2.3. Пример аппаратной реализации кодека 131
4.3. Основные результаты и выводы по главе 136
Заключение 137
Список использованных источников
- Систематические помехоустойчивые коды
- Методы уменьшения требуемого объёма памяти при аппаратной реализации кодека с использованием таблиц
- Библиотека классов для полиномиальных вычислений
- Создание файлов проекта кодека для его программной реализации на микроконтроллерах
Систематические помехоустойчивые коды
Известные разработки, которые можно считать автоматизированными системами для создания кодеков помехоустойчивых кодов, в основном, имеют исследовательский характер без их практического приложения [47,53,75-77,79-83,91].
Так, система, описанная в [47], позволяет моделировать работу кодеков таких кодов как Хэмминга, БЧХ, Рида-Малера. Она позволяет получать коды любой длины кодового слова за счёт трансформации кода (укорачивания). Однако никаких выигрышей, в первую очередь, с точки зрения уменьшения избыточности кодов эта система не предоставляет. Она позволяет лишь моделировать работу кодеков вышеупомянутых кодов без каких-либо вариантов их практических реализаций (аппаратных или программных).
Описанные в других работах [53,75-77,79-83,91], автоматизированные системы предсказывают или указывают на существование какого-либо кода с определённой корректирующей способностью, т.е. по заданным пользователем данным (длина кодового слова и длина информационного блока) система выдаёт расстояние Хэмминга с указанием названия кода или выдаёт предположение о существовании кода с таким расстоянием. Описания алгоритмов формирования таких кодов или описания кодеков на этих кодах рассмотренные системы не имеют.
На практике нужны автоматизированные системы для разработки кодеков помехоустойчивых кодов, которые должны быть для инженера-проектировщика простым инструментом при проектировании кодеков помехоустойчивых кодов. Инженер, имея исходные данные такие, как длина информационного блока и желаемая корректирующая способность кода, не должен вдаваться в подробности реализации кодека или знать особенности алгоритмов формирования (кодирования) и декодирования различных помехоустойчивых кодов. Алгоритмическое и программное обеспечение такой системы должно представлять из себя решение, которое инженер легко может использовать и получать проект кодеков для ввода их в специализированную САПР с целью аппаратной реализации кодеков на ПЛИС или написать управляющую программу для микроконтроллера по предоставленным системой данным о проектируемом кодеке. Выбор аппаратной реализации кодеков на ПЛИС обусловлен тем, что эти микросхемы позволяют с помощью специализированных САПР конфигурировать их в качестве любых современных аппаратных устройств [56].
Анализ с учётом вышеперечисленных требований существующих систем на предмет их практической значимости для целей разработки кодеков помехоустойчивых кодов показал, что как в России, так и за рубежом сегодня такие системы отсутствуют. Актуальной является проблема создания таких автоматизированных систем.
При проектировании кодеков помехоустойчивых кодов актуальна также задача выбора помехоустойчивого кода, так как основные характеристики кодека напрямую зависят от используемого помехоустойчивого кода. Для выбора конкретного помехоустойчивого кода под конкретные условия применения кодека необходимо обладать следующей информацией: область применения помехоустойчивого кода с точки зрения корректирующей способности кода; особенности реализации процедур кодирования и декодирования помехоустойчивого кода; затраты ресурсов, требующихся для программной или аппаратной реализаций помехоустойчивого кода; ограничения, налагаемые помехоустойчивым кодом, на длину информационного блока.
Всё это говорит о том, что инженер-проектировщик должен быть узким специалистом в области теории помехоустойчивого кодирования. Поэтому одним из требований, предъявляемым в первую очередь к системе, должна быть простота её использования, не требующая от инженера-проектировщика специальных знаний в области теории помехоустойчивого кодирования.
Во-вторых, система должна основываться на таких методах и алгоритмах помехоустойчивого кодирования, которые позволяют строить эффективные, по крайней мере не уступающие лучшим аналогам, помехоустойчивые коды. Процедуры кодирования и декодирования этих кодов должны быть унифицированы и просты, как при аппаратной реализации кодеков на ПЛИС, так и при программной реализации их на микроконтроллерах.
Также стоит рассмотреть требования к создаваемым кодекам помехоустойчивых кодов в зависимости от способа передачи данных. Обычно в телекоммуникационном оборудовании используют последовательный способ передачи данных. Здесь главным критерием является скорость передачи данных, зависящая, в основном, от длины передаваемого кодового слова. В тоже время, в вычислительных системах при использовании печатных плат, когда ведётся параллельная передача данных, можно выделить два основных требования к помехоустойчивому коду. Первое, это минимальная избыточность кода (также как и в случае последовательного способа передачи данных), а второе - высокое быстродействие кодека помехоустойчивого кода, которое зависит, прежде всего, от эффективности методов и алгоритмов, положенных в основу используемого помехоустойчивого кода, и от возможности кодировать и декодировать данные за один такт работы схемы. Быстродействие кодека особенно сказывается при параллельном способе передачи данных, когда каждый бит кодового слова передаётся по отдельной дорожке печатной платы. От быстродействия кодека помехоустойчивого кода в этом случае будет зависеть максимальная скорость передачи данных. От длины кодового слова в случае передачи данных параллельным способом зависит количество таких дорожек. Увеличение дорожек на печатной плате влечёт за собой увеличение затрат, сложности разводки и размеров печатной платы, а также увеличение электромагнитных наводок на дорожки передачи данных. Поэтому минимально возможная избыточность помехоустойчивого кода также актуальна при параллельном способе передачи данных.
Методы уменьшения требуемого объёма памяти при аппаратной реализации кодека с использованием таблиц
Если полиномы делятся нацело (Rck=0), то верхняя оценка числа шагов ск операции деления по ускоренному алгоритму удовлетворяет соотношению: ck entire((n-r+l)/2+0.5), (2.3) где entirety) - ближайшее целое к числу х, не превосходящее X. Если на некотором шаге у выполняется соотношение: Lj r,R 0, (2.4) то остаток от деления полиномов имеет ненулевое значение. Верхняя оценка числа шагов для обнаружения факта Rck ф О при этом также удовлетворяет неравенству (2.3). Чтобы найти значение остатка Rck ф О по ускоренному алгоритму, необходимо после у -го шага, для которого выполняется соотношение (2.4), продолжить вычисления как обычный процесс деления полиномов с нулевыми оставшимися разрядами делителя.
Значения остатка Rck является функцией величин Rj и числа нулей щ, используемых при продолжении процесса деления от у -го до ск-то шага. Очевидно, что при существовании ненулевого остатка Rck, требуется большее число шагов для его вычисления. Вычисление ненулевого остатка покажем на примере деления полинома (хп+хт+х9+х6+х5+1) на полином (х4+х+1): 10 0 11 11110 111 дополнительная итерация по классическому алгоритму деления 111001100001 ШСі= 10 0 110 0 10 0 11 R,= 1111111 Шс2= 10 0 1110 0 0 0 1 1 1 R2= 1 1 0 0 0 1ад - 1 0 0 1 1 Сз- Ш 1 0 0 0 1 1 1 ДОІ R3= 1 0 0 1 1 Ф ш 1 0 0 1 1C4 _ L_1 о о 1і R4= 1 0 0 1 І 10 0 1 11 0 1 t I R5=Rck=l_ 1 0 0 0 К сожалению, алгоритм Башина имеет серьёзный недостаток - существует ограничение на младшие разряды делимого и делителя: они всегда должны быть равны единице. Данный недостаток не позволяет использовать его в процедурах кодирования и декодирования полиномиальных помехоустойчивых кодов, так как младшие разряды кодовых слов могут принимать нулевые значения. Данный недостаток устранён в предложенном нами двустороннем алгоритме.
Двустронний алгоритм является модификацией алгоритма Башина. Нами были внесены коррективы, которые позволили устранить вышеописанные недостатки алгоритма, делающие его непригодным для использования в процедурах кодирования и декодирования полиномиальных кодов.
Для математического обоснования одновременного определения старших и младших разрядов Башиным доказана следующая теорема [3].
Теорема 1. Если полиномы вида (2.1) делятся без остатка, то полиномы, полученные из исходных путем изменения порядка следования коэффициентов на обратный (А"=хпА(х ); В =хгВ(х 1)), также делятся без остатка. Полученное таким образом частное будет иметь обратный порядок следования коэффициентов по сравнению с частным от- деления исходных полиномов (С =хтС(х )).
Нами сформулировано и доказано Следствие из Теоремы 1, которое является основой двустороннего алгоритма. Следствие из Теоремы 1. Полиномы вида (2.1) делятся с остатком, если п-р г, где р - количество младших незначащих нулей делимого. Доказательство (от противного). Обозначим через р количество младших незначащих нулей полинома А. Тогда, А(х) = (ап_ххп-1 +...+архр) = {br_xxr { + ...+b0x)(Cn_rxn-r + ...+Срхр) = В(х)С(х); xp(an_1_pxn-]-p+...+ a0x) = (br_X l+---+ (яn-l-X Ь,, +...+ о ) = ф лГ-1 +...+Ь0х)(Сп_р_гх"-р-г +...+ С0х), если г п—р, то степень п-р—г 0. Что и требовалось доказать. Примечание: предполагается, что младший разряд делителя ненулевой, иначе степень делителя вычисляется без младших незначащих нулей.
На основании Теоремы 1 и Следствия из Теоремы 1 разработан алгоритм ускоренного деления полиномов в арифметике по модулю два [14,92], получивший название «двусторонний алгоритм ускоренного деления полиномов в арифметике по модулю два», у которого одновременно определяются старшие и младшие разряды частного. В отличие от алгоритма Башина [3], данный алгоритм является универсальным (в нём не накладывается никаких ограничений на делимое и делитель) и он всегда обеспечивает корректное вычисление частного.
Пусть п - разрядность делимого, а г - разрядность делителя, тогда старшая степень частного равна s=n-r;A- делимое, В - делитель, С — частное, a D остаток. Тогда двусторонний алгоритм описывается следующим образом. Разработанная модификация алгоритма Башина может применяться в процедурах кодирования и декодирования полиномиальных кодов за счёт введения контроля над младшими незначащими нулями делителя и запоминания состояния соответствующих младших разрядов делимого на первых шагах алгоритма, которые понадобятся при вычислении остатка на самых последних шагах алгоритма. Можно считать, что разработан ускоренный алгоритм деления, верхняя оценка числа шагов которого не больше, чем в классическом алгоритме. Действительно, ускорение предполагается за счёт одновременного определения двух единичных разрядов частного, поэтому выигрыш в количестве итераций будет больше, если п»г.
В разработанном алгоритме существует возможность вычислить остаток за одну итерацию, в случае, если делитель содержит только один ненулевой разряд.
Несмотря на сокращение количества итераций при делении полиномов, разработанный алгоритм остаётся достаточно сложным с точки зрения аппаратной реализации. К тому же, для вычисления остатка всё ещё необходимо выполнять множество итераций вычислений. Для достижения поставленной цели необходим более эффективный и простой алгоритм деления полиномов в арифметике по модулю два.
Исследовав особенности построения двоичных циклических помехоустойчивых кодов и отметив полезные свойства при построении кода с помощью образующей матрицы в систематической форме, мы разработали универсальный алгоритм деления полиномов в арифметике по модулю два, который получил название «матричный алгоритм деления полиномов в арифметике по модулю два» [13 Д4] (далее по тексту матричный алгоритм).
Библиотека классов для полиномиальных вычислений
Нами предлагается метод, который основан на использовании словаря событий, в который входят: О - комбинации, соответствующие событию безошибочного принятия кодового слова или с исправимыми ошибками в контрольных символах, С2 - комбинации, соответствующие событию принятия кодового слова с неисправимыми ошибками, СЗ - комбинации, соответствующие событию принятия кодового слова с исправимыми ошибками в информационных символах. Несложно показать, что количество слов в словаре С вычисляется следующим образом: С = СЗ + С2 + С\, t где CI, С2 и СЪ принимаются значения СЪ- С1т ; С2=1; С1=1. Для организации словаря необходимо разделить память на два блока: в первом блоке будут храниться адреса слов, а во втором блоке — сами слова. Такая организация памяти синдромного декодирования потребует 2к -q + 2q -т бит памяти, где g = jlog2C. Например, для полиномиального кода (31,16,7) и г = 3 с использованием данного метода потребуется 43008 байт вместо 65536 байт, если не применять этот метод, или против 61440 байт метода запоминания позиций. Схема организации памяти для данного метода представлена на рис. 2.25.
В методе составления словаря не удалось полностью уйти от привязки количества адресов к количеству синдромов ошибок, т.к. на самом деле нас интересует соответствие группы синдромов ошибок с соответствующими элементами из словаря событий в виде исправляющих комбинаций. В идеальном варианте требуемый объём ЭНП должен равняться 2й т бит.
Нами предложен новый метод уменьшения требуемого объёма ЭНП на основе принципа организации частично-ассоциативной кэш-памяти. Метод основан на том факте, что количество исправляющих комбинаций (по методу из 2.5.2 - количество событий) намного меньше, чем количество синдромов ошибок. Поэтому в методе предлагается с использованием принципа организации частично-ассоциативной кэш-памяти осуществлять вычисление адреса нужной исправляющей комбинации. Таким образом, объём требуемой памяти будет зависеть не от количества синдромов ошибок, а от количества исправляющих комбинаций.
Исходя из того, что синдром ошибок фактически является адресом исправляющей комбинации при табличном декодировании, то в соответствии с принципом организации частично-ассоциативной кэш-памяти адрес делится на две части: тег и адрес группы. Адрес группы используется для выбора из всех банков памяти тегов, хранящихся там. Выбранные теги сравниваются с тегом из адреса, в соответствии с результатами сравнения тегов формируется номер нужного банка памяти или сигнал об обнаружении неисправимой ошибки. Далее по адресу группы и номеру банка выбирается исправляющая комбинация и сравнивается с комбинацией, сигнализирующей о наличии неисправимой ошибки. Если они равны, то формируется сигнал об обнаружении неисправимой ошибки, иначе эта последовательность передается подсистеме корректировки кода. В данном случае память организуется двумя блоками: блок тегов и блок исправляющей комбинации. Оба эти блока, в свою очередь, подразумевают внутреннее деление на банки памяти. Количество внутренних банков памяти зависит от максимальной частоты встречаемости тегов в нужных нам синдромах ошибок (синдромы исправляемых кодом ошибок, нулевой синдром, синдромы ошибок, не требующие исправления), т.е. от максимального числа тегов соответствующих одному адресу группы.
Данный метод реализуется с помощью алгоритма, имеющего несколько основных этапов: Этап 1. Составление словаря синдромов. Словарь составляется из синдромов ошибок, кратность которых не превышает t (количество исправляемых кодом независимых ошибок) плюс синдром об отсутствии ошибки. Месторасположение ошибки в информационной и/или контрольной последовательности не важно. Количество слов в данном словаре можно вычислить по формуле: Этап 2. Выбор разрядностей тега и адреса группы. Сумма разрядов адреса группы и тега равна к. Расположение тега и адреса группы в синдроме может быть произвольным. Этап 3. Нахождение требуемого количества банков памяти. Для этого необходимо подсчитать для каждого адреса группы соответствующее ему количество тегов и выбрать из них максимальное - это и будет являться количеством необходимых банков памяти. Этап 4. Подсчет требуемого объема памяти. Объем памяти определяется по следующей формуле: 21 -Ь-(р + т), где Ъ - количество банков памяти, / — разрядность адреса группы, р — разрядность тега. Этап 5. Перебор и анализ вариантов. Повторить этапы 2-4 с разными разрядностями тега и адреса группы, затем выбрать наиболее подходящий результат.
Так как количество тегов для каждого адреса группы разное, то в банках памяти возникают пустые места, которые нужно заполнить. Эта проблема решается заполнением всех пустых мест в блоке тегов произвольными значениями (эти теги не будут входить в диапазон адресов исправляющих комбинаций и тем самым будут сигнализировать о неисправимой ошибке), при этом все теги в группе должны быть различными. В блоке исправляющих комбинаций все пустые места заполняются комбинацией, сигнализирующей о наличии неисправимой ошибки. Таким образом, мы получаем два признака обнаружения неисправимой ошибки.
Создание файлов проекта кодека для его программной реализации на микроконтроллерах
Инклинометрическая система для буровой установки (ИСБУ), состоящая из скважинного прибора (СП) и комплекса наземной аппаратуры (КНА), предназначена для измерения на забое и индикации на поверхности земли положения турбобура в пространстве (рис 4.13), а также для управления положением турбобура. ИСБУ используется при сложных технологических операциях турбинного бурения, включая наклонное и горизонтальное бурение скважин. Для измерения положения турбобура в пространстве используется СП, иногда его называют "зонд".
Данные с датчиков инклинометрии обрабатываются вычислительным блоком в СП и передаются на поверхность земли по электромагнитному каналу. Для этого сигнал подается на управляемый выпрямитель в СП, который преобразует переменный ток, вырабатываемый турбогенератором, в постоянный, причем полярность его зависит от управляющего логического уровня: "О" или "1". Этот ток подводится к металлическим частям корпуса турбобура и буровой колонны, электрически не связанных между собой. Таким образом, при подаче напряжения между электрически разделённых турбобуром и буровой колонной происходит растекание тока в породе. Часть этого тока достигает поверхности. Сигнал снимается между приёмным заземлителем и буровой установкой и подаётся на вход КНА (рис. 4.13). Уровень сигнала на входе может изменяться от единиц вольт (на малых глубинах) до сотен микровольт (на максимальных глубинах бурения), поэтому такой сигнал подвержен к воздействию помех со стороны окружающей среды, включая помехи от работающего оборудования.
При передаче данных с СП в КНА необходимо повысить достоверность их передачи. При этом необходимо учесть следующие исходные данные. Длину информационного блока т принять равной 9 бит.
В соответствии с технологией использования ПО системы MagDiv (см. п. 3.1.3) для заданных параметров инженером-проектировщиком т — 9 и t — 3 система сама подбирает подходящий образующий полином из ранее найденных. В данном случае используется образующий полином 110001110101, равный 3189 (в десятичной системе исчисления), или х + х1 + х +х +х +х +1 (записан в виде полинома Жегалкина), длина кодового слова п равна 20.
Стоит отметить, что этот образующий полином 3189ю, найденный с помощью разработанного ПО, позволяет строить помехоустойчивый код, имеющий меньшую длину кодового слова, чем аналогичный БЧХ-код. Этот код обладает меньшей избыточностью, а значит большей эффективностью по сравнению с аналогом БЧХ-кода.
Исходные параметры вводим в соответствующие поля экранных форм пользовательского интерфейса системы MagDiv.
В результате применения ПО системы MagDiv при проектировании кодека получаем проектные файлы кодека на языке описания аппаратуры Verilog (рис. 4.14): codec_20_3.v, Div_codec__20_3.v, Rom_codec_20J3.mif и Rom_codec_20_3.v. Проектные файлы сохраняем для выполнения последующих работ вне системы MagDiv.
Загружаем сгенерированные файлы проекта для аппаратной реализации кодека в САПР Мах+ plus II фирмы Altera. Затем проект необходимо скомпилировать под определённое семейство кристаллов. Для проекта codec_20_3 подходит семейство кристаллов АСЕХ1К и конкретное устройство из этого семейства ЕР 1К50ТС144-1 (рис. 4.15). info. Selecting a device from ACEX1K .amity (or AUTO device codec U3 tnfo: Compiling ptojett using Quartus Rttet tectmetofy. Info: Chip codec 20 У successfully tit into AUIO device E Pl K5RFC144 } .a С помощью САПР Мах+ plus II осуществляется подготовка к конфигурации конкретного кристалла ЕР1К50ТС144-1 и затем производится его конфигурирование спроектированным кодеком codec_20_3. Работа кодека контролируется двумя сигналами: синхронизации и управления режимом работы кодека codec (рис. 4.16). Эти сигналы и данные для регистров информационного и контрольного блоков задаются
В режиме кодирования сигнал codec должен быть равен логической единице. При этом на регистр информационного блока подаются данные для кодирования. При нарастающем фронте сигнала синхронизации с регистра информационного блока данные подаются на блок вычисления синдрома для вычисления контрольных разрядов. Контрольные разряды записываются в соответствующий регистр при появлении спадающего фронта сигнала синхронизации (рис. 4.18).
В режиме декодирования сигнал codec должен быть равен логическому нулю. На регистры информационного и контрольного блоков подаётся кодовое слово для декодирования. При нарастающем фронте сигнала синхронизации соответствующих регистров кодовое слово подаётся на блок вычисления синдрома. Вычисленный синдром поступает на блок исправления ошибок. Исправленное кодовое слово записывается в соответствующие регистры при появлении спадающего фронта сигнала синхронизации (рис. 4.19-4.22). На этих рисунках показаны результаты моделирования работы этого кодека в САПР Мах+ plus II в режиме декодирования. Причём рассмотрены случаи, когда данные приняты без ошибок и когда в принятых данных исправлению подлежат однократная, двухкратная и трёхкратная независимые ошибки.
