Главная » Просмотр файлов » А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования

А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 8

Файл №1127104 А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования) 8 страницаА.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104) страница 82019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Они позволяют исправлять любое фиксированноечисло ошибок над двухбуквенным алфавитом и примыкают к коду Хэмминга (который является их частным случаем).3618. ëÏÄÙ âþèРассмотрим поле F из = 2 элементов и многочлены степени меньше с коэффициентами в этом поле. Такой многочлен ( ) = + + . . . + − −определяется коэффициентами , . . . , − . С другой стороны, он однозначно определяется своими значениями в точках поля F (в поле как раз элементов). Значения многочлена в каждой точке поля можно выбратьпроизвольно: каковы бы ни были эти значения, мы сможем подобратьсоответствующий им многочлен степени − 1. Так что соответствиекоэффициенты ↔ значенияявляется изоморфизмом -мерных пространств над полем F.

(Этот изоморфизм является дискретным вариантом преобразования Фурье.)Наложим теперь на многочлен некоторые ограничения. Во-первых,потребуем, чтобы его степень была меньше − (для некоторого фиксированного ). Другими словами, потребуем, чтобы старшие коэффициентов равнялись нулю. (Таблицы значений таких многочленов образуют,как мы помним, код Рида { Соломона с расстоянием + 1.)Во-вторых, потребуем ещё, чтобы значения многочлена во всех точках поля равнялись нулю или единице (поля F).

В этом случае таблицазначений будет двоичным словом длины .Все такие таблицы и являются кодовыми словами кода БЧХ.Переформулировка: слово из нулей и единиц является кодовымсловом кода БЧХ, если соответствующий ему многочлен (принимающийуказанные значения в точках поля F) имеет степень меньше − .(Здесь и | параметры кода.)Кодовое расстояние этого кода не меньше +1 (поскольку он являетсячастью кода Рида { Соломона с таким кодовым расстоянием).

Сложнеепонять, сколько при этом образуется кодовых слов. Хотя оба ограниченияна многочлен просты, но одно из них формулируется в терминах егокоэффициентов, а другое | в терминах значений, и надо ещё понять,как они взаимодействуют друг с другом.Для этого нам понадобятся некоторые сведения из алгебры. В поле Fвыделим подполе F ⊂ F, состоящее из нуля и единицы. [Чтобы убедиться, что это действительно подполе, достаточно проверить, что 1 + 1 = 0в F, то есть что характеристика поля F равна 2.

Это доказывается так:если характеристика равна > 2, то в F есть подполе из элементов,и F есть векторное пространство над этим подполем, так что размер Fесть степень числа .]10110213718. ëÏÄÙ âþèКак мы уже говорили, многочлены степени меньше образуют векторное пространство над F; условие обращения старших коэффициентов в нуль задаёт подпространство этого пространства. Но второе нашеусловие (значения во всех точках нули и единицы) не является линейным над F. Однако оно является линейным над F (по тривиальным причинам).

Поэтому построенное нами множество кодовых слов кода БЧХ(обозначим его ) является векторным пространством над полем F , инадо только определить его F -размерность.Если бы не требование обращения в нуль старших коэффициентов,то F -размерность была бы равна . Обращение в нуль каждого из коэффициентов задаётся уравнениями: коэффициент принадлежит полю F, которое имеет размерность над F . (Говоря о уравнениях, мыимеем в виду F -линейные уравнения.) Эти уравнения могут быть (и будут, как мы увидим) зависимыми, но уже сейчас можно сформулироватьтакое. F -размерность не меньше − , то есть − log .Это уже кое-что: мы получаем код длины с log проверочнымисимволами (и − log значащими) и расстоянием +1.

Например, при = 2 получается код с расстоянием 3 (как и у кода Хэмминга) и 2 log проверочными символами (что вдвое больше, чем у Хэмминга).Однако на самом деле ситуация оказывается ещё немного лучше: условий, соответствующих обращению в нуль старших коэффициентовмногочлена , линейно зависимы над полем F . Чтобы понять это, нампонадобится вспомнить ещё кое-что из алгебры.Для начала заметим, что условие «все значения многочлена | нулиили единицы» можно переформулировать так: ( ) = ( ) для всех ∈ F. Другими словами, многочлен − должен обращаться в нульво всех точках поля F. Это не значит, что все его коэффициенты нулевые(ведь степень многочлена − может быть почти в два раза большечисла элементов в поле), а означает лишь, что делится на многочлен222222Следствие22222 ( ) = ∏ ( − ).∈FПоследний многочлен равен − . Действительно, по теореме Лагранжа порядок каждого элемента в мультипликативной группе поля делитпорядок группы, равный − 1 (на самом деле верно более сильное свойство: мультипликативная группа поля обязана быть циклической; но этосейчас нам не важно).

Поэтому − = 1 для любого ненулевого элемента поля, и = для любого элемента поля. Значит, многочлен − 13818. ëÏÄÙ âþèобращается в нуль во всех точках поля, поэтому он делится на ; остаётся заметить, что у этих двух многочленов совпадают степени и старшиекоэффициенты.Итак, условие «все значения | нули или единицы» можно переформулировать так: − делится на многочлен − без остатка.Как записать это условие в терминах коэффициентов многочлена ?Заметим, что делить с остатком на − очень просто. Надо понизитьстепени по правилам2+1→+2→→ −→...−22231(Дальше должна идти строка − → → , но до таких степеней в нашем случае дело не дойдёт.) Затем надо привести подобные члены. (Этапроцедура соответствует обычному делению многочленов «уголком».)Сделаем это для многочлена − , если212 ( ) = − − + − − + . .

. + + .121210Вычислить легко, если вспомнить, что в поле характеристики 2, где1 + 1 = 0, имеет место равенство ( + ) = + , поскольку член2 обращается в нуль. Поэтому квадрат суммы есть сумма квадратов, и22 ( ) = − 221−22+ − 22−2422+ ... + + .21220Делимость − на − означает, что после замен одночленов всоответствии с приведённой выше таблицей из должно получиться ,223918.

ëÏÄÙ âþèто есть − = − − = − − = −.../ = ... = = =211233522221224212200(в обоих столбцах каждый коэффициент встречается по одному разу; вправом столбце сначала идут все нечётные, а потом все чётные коэффициенты). Заметим, что несмотря на свой квадратичный вид, каждоеиз этих условий является F -линейным (поскольку возведение в квадрат,как мы уже говорили, линейно над полем характеристики 2).Итак, мы записали условие «все значения многочлена | нули илиединицы» в виде F -линейных уравнений на его коэффициенты. Как мызнаем, пространство решений этой системы линейных уравнений имеетразмерность .

Мы хотим выяснить, напомним, насколько уменьшитсяразмерность, если наложить дополнительные ограничения − = 0, . . . , − = 0.Про − мы и так уже знаем, что − = − , то есть что − равнонулю или единице. Поэтому условие − = 0 уменьшает размерностьпространства решений на 1 (а не на , как было в нашей прежней оценке).Дальнейшие уравнения системы выражают − , − ,.

. . , через сбольшими индексами. Поэтому условия обращения в нуль достаточнозаписывать лишь для − , − , . . . вплоть до − (для чётного ) и − (для нечётного ).Ограничимся для простоты случаем чётного (при этом кодовое расстояние будет не меньше + 1, и можно исправлять /2 ошибок). Тогдаполучится /2 условий коразмерности плюс ещё одно условие коразмерности 1 (на − ).

Отсюда получаем, что F -размерность пространства кодов БЧХ длины с расстоянием не меньше + 1 для чётного не меньше − 1 − /2 = − 1 − (/2) log .Словами: на каждую исправляемую ошибку нужно log контрольныхбитов, плюс ещё один контрольный бит на всех.221211111324+112514019. âþè É èÜÍÍÉÎÇИнтересно сравнить параметры БЧХ-кодов с границей Хэмминга. Шаррадиуса = /2 содержит примерно ≈ / ! элементов (мы считаем,что ≪ и потому заменяем ( − 1) . . . ( − + 1) на ). ГраницаХэмминга говорит, что логарифм числа кодовых слов не превосходитпримерно − log( / !) = − log + log( !);первые два слагаемых как раз соответствуют БЧХ-кодам, так что разницалишь на log( !).19. БЧХ и ХэммингПокажем, что код Хэмминга может быть получен как частный случайкода БЧХ.Пусть, например, = 3, = 8 и мы рассматриваем поле F .

Характеристики

Тип файла
PDF-файл
Размер
713,8 Kb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6480
Авторов
на СтудИзбе
304
Средний доход
с одного платного файла
Обучение Подробнее