Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Рид – соломон кодыСтр 1 из 2Следующая ⇒ Коды Рида — Соломона (англ. Reed–Solomoncodes) — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами). Код Рида — Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна Массачуссетского технологического института Ирвином Ридоми Густавом Соломоном. Идея использования этого кода была представлена в статье «PolynomialCodesoverCertainFiniteFields». Эффективные алгоритмы декодирования были предложены в 1969 году Элвином Берлекэмпом и ДжэймсомМесси (алгоритм Берлекэмпа — Мэсси) и в 1977 году Давидом Мандельбаумом (метод, использующий Алгоритм Евклида). Первое применение код Рида — Соломона получил в 1982 году в серийном выпуске компакт-дисков. Код Рида — Соломона над , исправляющий ошибок, требует проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной и меньше. Согласно теореме о границе Рейгера, коды Рида — Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок — используя дополнительных проверочных символов исправляется ошибок (и менее). Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной и менее, должен содержать, по меньшей мере, проверочных символов. Код, двойственный коду Рида — Соломона, есть также код Рида-Соломона. Двойственным кодом для циклического кода называется код, порожденный его проверочным многочленом. Матрица порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы отличен от нуля. При выкалывании или укорочении кода Рида-Соломона снова получается код Рида — Соломона. Выкалывание — операция, состоящая в удалении одного проверочного символа. Длина кода уменьшается на единицу, размерность сохраняется. Расстояние кода должно уменьшиться на единицу, ибо в противном случае удаленный символ был бы бесполезен. Укорочение - фиксируем произвольный столбец кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство. Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим. При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок. При систематическом кодировании к информационному блоку из символов приписываются проверочных символов, при вычислении каждого проверочного символа используются все символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка . При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова длины на неприводимый полином при систематическом кодировании можно выполнить следующим образом: · К исходному слову приписываются нулей, получается полином . · Этот полином делится на порождающий полином , находится остаток , , где — частное. · Этот остаток и будет корректирующим кодом Рида — Соломона, он приписывается к исходному блоку символов. Полученное кодовое слово . Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа. Существует и другая процедура кодирования (более практичная и простая). Положим - примитивный элемент поля , и пусть - вектор информационных символов, а значит - информационный многочлен. Тогда вектор есть вектор кода Рида - Соломона, соответствующий информационному вектору . Этот способ кодирования показывает, что для кода РС вообще не нужно знать порождающего многочлена и порождающей матрицы коды, достаточно знать разложениеполя по примитивному элементу и размерность кода (длина кода в этом случае определяется как ). Все дело в том, что за разностью полностью скрывается порождающий многочлен и кодовое расстояние. Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия: · Вычисляет синдром ошибки · Строит полином ошибки · Находит корни данного полинома · Определяет характер ошибки · Исправляет ошибки
|