Реферат на тему Оценка эффективности полиномиальных кодов со свойством цикличности (циклических)

Содержание:

ВВЕДЕНИЕ 2
1. Понятие линейного кода 3
2. Полиноминальные кольца 5
3. Одиночная ошибка, исправляющая полиномиальные коды 7
4. Коды Рида-Соломона 11
ЗАКЛЮЧЕНИЕ 14
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 16

Введение:

Полиномиальный код — это линейный код, имеющий набор допустимых кодовых слов, который состоит из полиномов, кратных короткому фиксированному полиному, и называется генераторным полиномом.
Они используются для обнаружения и исправления ошибок при передаче данных, а также для хранения данных.
Типы полиномиальных кодов:
 Циклический код избыточности
 Коды БЧХ
 Коды Рида – Соломона
Интерпретация полиноминального кода как кода циклического избыточного кода означает поиск ошибок по правилам сокращенного циклического кода. При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен.
Блочные полиномиальные коды отличаются от остальных только алгоритмами кодирования и декодирования.
Так можно сказать, что полиноминальный код – это код с обнаружением ошибок, в котором контрольные разряды являются остатком от деления передаваемых разрядов на фиксированное число.

Заключение:

Основным достоинством непозиционных кодов является, то, что данные представляются в виде малоразрядных остатков, которые обрабатываются по параллельным вычислительным трактам. Это позволяет повысить скорость вычислений, что и предопределяет интерес к полиномиальным непозиционным кодам в различных областях применения.
Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
Таким образом благодаря применению циклических полиноминальных кодов можно исправлять значительные скопления ошибок. Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).
Как правило, Обнаружение ошибок производится с помощью алгоритма деления с остатком: нужно поделить многочлен, отвечающий принятому слову, на g(x); если остаток степени <deg g оказывается ненулевым, то при передаче произошло искажение.
Применение полиномиальных кодов является эффективным методом повышения надежности и снижения себестоимости систем функционального диагностирования. Простая реализация процесса кодирования при помощи полиномиальных кодов еще раз подтверждает их преимущество. Методы полиномиального кодирования обладают лучшими обнаруживающими характеристиками по сравнению с существующими методами кодирования в системах функционального контроля. Показатели структурной избыточности при применении полиномиального кодирования также свидетельствуют об эффективности его использования при решении поставленной задачи.
Вследствие этого полиномиальные коды могут эффективно использоваться не только для задач обнаружения ошибок в передаче и обработки данных, но и при решении задач технической диагностики как тестового, так и функционального диагностирования устройств железнодорожной автоматики и телемеханики. Учитывая изложенное, использование класса полиномиальных кодов целесообразно при решении задач построения самопроверяемых дискретных устройств железнодорожной автоматики и телемеханики.
Тем не менее, несмотря на эффективное устранение редких, но больших пачек ошибок, эффективность данных кодов при частых, но небольших ошибках (пример: канал с АБГШ) достаточно низкая.
Можно сделать вывод, что использование циклических полиноминальных кодов имеет огромный ряд преимуществ и недостаток в виде неэффективности работы с частыми небольшими ошибками.

Фрагмент текста работы:

1. Понятие линейного кода

В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.
В теории кодирования линейный код представляет собой код с исправлением ошибок, для которого любая линейная комбинация кодовых слов также является кодовым словом. Линейные коды традиционно делятся на блочные и сверточные коды, хотя турбокоды можно рассматривать как гибрид этих двух типов. Линейные коды допускают более эффективные алгоритмы кодирования и декодирования, чем другие коды.
Линейные коды используются в прямом исправлении ошибок и применяются в способах передачи символов (например, битов) по каналу связи, так что, если ошибки возникают в связи, некоторые ошибки могут быть исправлены или обнаружены получателем блока сообщения. Кодовые слова в линейном блочном коде — это блоки символов, которые кодируются с использованием большего количества символов, чем исходное значение, которое должно быть отправлено. Линейный код длиной n передает блоки, содержащие n символов. Например, код Хэмминга является линейным двоичным кодом, который представляет 4-битные сообщения с использованием 7-битных кодовых слов. Два разных кодовых слова отличаются как минимум тремя битами. Как следствие, в каждом кодовом слове может быть обнаружено до двух ошибок, а одна ошибка может быть исправлена. Этот код содержит 24 = 16 кодовых слов. [1]
Линейный код длины n и ранга k является линейным подпространством C с размерностью k векторного пространства F_q^n, где F_q^n — конечное поле с q элементами. Такой код называется q-арным кодом. Если q = 2 или q = 3, код описывается как двоичный код или троичный код соответственно. Векторы в C называются кодовыми словами. Размер кода равен числу кодовых слов и равен qk.
Вес кодового слова — это число его элементов, отличных от нуля, а расстояние между двумя кодовыми словами — это расстояние Хэмминга между ними, то есть количество элементов, в которых они различаются. Расстояние d линейного кода представляет собой минимальный вес его ненулевых кодовых слов или, что эквивалентно, минимальное расстояние между различными кодовыми словами. Линейный код длины n, размера k и расстояния d называется кодом [n, k, d]. [4]
Необходимо дать F_q^n стандартную основу, потому что каждая координата представляет «бит», который передается через «шумный канал» с небольшой вероятностью ошибки передачи (двоичный симметричный канал). Если используется какой-либо другой базис, то эта модель не может быть использована, и метрика Хемминга не измеряет количество ошибок при передаче, как это необходимо.
В качестве первого класса линейных кодов, разработанных с целью исправления ошибок, коды Хэмминга широко используются в цифровых системах связи.
Линейный блочный код со следующей матрицей генератора и матрицей контроля четности является [7,4,3]2 кодом Хэмминга.