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

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

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

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

А один процент блоков внешнего кода неможет сильно повлиять на его кодовое расстояние..1. При этой конструкции построение кода и кодирование не требуютперебора. Однако декодирование внутреннего кода (в тех блоках, где оноудаётся) по-прежнему требует перебора всех возможных кодовых слов.2. Построенный код легко описать безо всякого упоминания о конкатенации. В самом деле, мы делаем всё как в кодах Рида { Соломона, только берём значения (во всех точках поля) не одного многочлена ( ), адвух: многочлена ( ) и многочлена ( ).

Другими словами, мы записываем данный нам набор элементов поля в коэффициенты многочленовдважды | начиная со свободного члена и начиная с первой степени |и объединяем полученные значения.Замечания2613. ïÃÅÎËÁ ðÌÏÔËÉÎÁ13. Оценка ПлоткинаРазличие между границами Хэмминга и Гилберта особенно разительнов правой половине рис. 1: при > /2 граница Хэмминга не запрещаетсуществования кодов, а граница Гилберта не гарантирует их существования. Что же происходит на самом деле? (Речь идёт о двоичных кодах,когда ˚ = {0, 1}.)Максимальное расстояние между двумя элементами B равно . Точки, между которыми такое расстояние, отличаются во всех позициях, ипотому ясно, что три точки с попарными расстояниями найти нельзя.Более того, даже если ослабить требования и искать три точки с попарными расстояниями не меньше 0,99 , это тоже не удастся: если и отличаются от в 99% мест, то совпадает с по крайней мере в 98%мест.Аналогичное утверждение, хотя и не по столь очевидным причинам,справедливо для любой доли > 1/2..

Пусть > 1/2. Количество точек в B , попарные расстояниямежду которыми не меньше , не превосходит12 − 1 + 1 .Здесь важно, что оценка на число точек не зависит от (хотя и зависит от : чем ближе к 1/2, тем слабее оценка).леммы. Удобно вместо последовательностей нулей иединиц рассматривать последовательности единиц и минус единиц, считая их векторами в R . Определим скалярное произведение в R , положивЛеммаДоказательство(⟨ , . . . , ⟩, ⟨ , . . .

, ⟩) = ∑ .11Разница с обычным скалярным произведением в R состоит лишь в дополнительном делении на . Это технически удобно, поскольку при этомевклидова длина любого слова (которое, напомним, мы считаем векторомиз плюс-минус единиц) равна 1.Если расстояние Хэмминга между двумя кодовыми словами не меньше , то их скалярное произведение отрицательно и не больше 1 − 2 .Теперь легко получить оценку на число векторов: если имеется единичных векторов , . . .

, в евклидовом пространстве и при этомскалярное произведение любых двух из них не больше 1 − 2 , то0 6 ( + . . . + , + . . . + ) 6 + ( − 1)(1 − 2 )1112713. ïÃÅÎËÁ ðÌÏÔËÉÎÁ(имеется квадратов и (векторов), откуда− 1)попарных произведений различных − 1 6 2 1− 1 ,что и требовалось в лемме.Таком образом, если мы хотим, чтобы количество передаваемой информации росло с ростом , на исправление более чем 25% ошибок надеяться не приходится. В частности, в правой половине рис.

1 никакихинтересных кодов нет, хотя оценка Хэмминга их и не запрещает.Если требовать, чтобы кодовое расстояние было больше 50% (разрешая ему быть сколь угодно близким к 50%), то все углы между кодовымисловами будут тупыми и число точек не больше + 1, как показываетследующее простое утверждение:Если несколько векторов евклидова пространства образуют попарно тупые углы, то после удаления любого из векторов получается линейно независимая система.В самом деле, предположим, что векторы , . . . , образуют попарнотупые углы.

Покажем, что , . . . , линейно независимы. Пусть это нетак и + . . . + = 0.Вычеркнем все нулевые коэффициенты. Если оставшиеся коэффициентыимеют один знак, то умножим скалярно на и получим противоречие:сумма нескольких отрицательных скалярных произведений с коэффициентами одного знака равна нулю.Если оставшиеся коэффициенты имеют разные знаки, то разнесём ихв разные части и получим равенство + . . . = + .

. . ,где все коэффициенты положительны. Если обе части равны нулю, тосмотри выше. Если же нет, то скалярное произведение левой части направую одновременно положительно (как скалярный квадрат вектора) иотрицательно (как сумма отрицательных скалярных произведений с положительными коэффициентами). Линейная независимость доказана.Если разрешить и прямые углы (наряду с тупыми), то максимальноечисло векторов в -мерном евклидовом пространстве возрастёт до 2 .В самом деле, можно взять плюс-минус векторы базиса, их как раз 2 .Больше векторов взять не удастся:01110Если векторы в -мерном евклидовом пространстве образуют по2 .парно прямые или тупые углы, то их число не превосходит2813.

ïÃÅÎËÁ ðÌÏÔËÉÎÁВ самом деле, можно считать, что линейная оболочка векторов совпадает со всем пространством (иначе можно свести дело к меньшей размерности, рассуждая по индукции) и векторы , . . . , образуют базис.Выразим остальные (при > ) через , . . . , .. Заметим, что в таких выражениях все ненулевые коэффициенты (а в каждом из выражений они есть, поскольку ̸= 0) отрицательны.В самом деле, предположим, что это не так и в каком-то из выражений = + . . . + есть положительные . Перенесём все отрицательные коэффициенты влевую часть и получим равенство + (− ) + .

. . = + . . . ,где все коэффициенты при положительны и в правой части что-тоосталось (ведь были положительные коэффициенты). Тогда правая частьэтого равенства (а значит, и левая) отлична от нуля в силу линейной независимости векторов базиса. Произведение левой части на правую должно быть одновременно положительно (как скалярный квадрат ненулевоговектора) и неположительно (поскольку после раскрытия скобок становится суммой неположительных скалярных произведений с положительнымикоэффициентами). Противоречие..

Если общее число векторов больше 2 , то векторы при > (их не меньше + 1 штук в -мерном пространстве) линейно зависимы. Коэффициенты их нулевой линейной комбинации не могут бытьодного знака, ведь в выражениях через базисные векторы , . . . , коэффициенты отрицательны и сократиться друг с другом не могут.

Значит,есть разные знаки и можно снова разнести их по разным частям: + . . . = + . . . ,где все коэффициенты положительны. Обе части содержат хотя быодин ненулевой член и потому не равны нулю (как мы уже знаем пролинейные комбинации с коэффициентами одного знака). Поэтому скалярное произведение левой части и правой одновременно положительно (какскалярный квадрат ненулевого вектора) и неположительно (как сумманеположительных скалярных произведений с положительными коэффициентами). Противоречие.Таким образом, мы приходим к оценке (границе ) Плоткина : числокодовых слов длины с попарными расстояниями не меньше /2 непревосходит 2 .11Шаг 111Шаг 212915. ëÏÄ áÄÁÍÁÒÁ14.

Улучшение оценки СинглтонаИмея оценку Плоткина, вернёмся к рассуждению, использованномудля доказательства оценки Синглтона, и получим более сильную оценку.Будем рассматривать случай кодов в двухбуквенном алфавите.Пусть код имеет длину кодовых слов , длину кодируемого слова ирасстояние (мы будем писать для краткости «[, , ] -код»; индекс 2 |размер алфавита). Принцип Дирихле показывает, что для любого от 1до − 1 среди 2 кодовых слов можно указать 2 − кодовых слов, которыесовпадают в первых битах.

Они образуют [ −, −, ] -код (посколькупервые битов совпадают, различий приходятся на остальные − битов).Доказывая оценку Синглтона, мы брали = − 1 и замечали, чтодля полученного кода (с двумя кодовыми словами) расстояние не большедлины кодового слова: − ( − 1) > .Теперь мы можем взять меньшее , при котором у полученного кода длинакодового слова будет равна удвоенному расстоянию: − = 2, или = − 2.Согласно оценке Плоткина, число кодовых слов не превосходит удвоенной длины:2 − 6 4, или − + 2 6 log(4 ).Замечая, что 6 и деля на , получаем оценку22 + 26 1 + 4 log /.При больших последним слагаемым можно пренебречь и на рис. 1появляется новая граница (пунктир на рис.

3).Видно, что она кое-где сильнее, а кое-где слабее границы Хэмминга.15. Код АдамараОказывается, что оценка Плоткина является точной, если есть степень двойки. Соответствующий пример доставляют коды Адамара.3015. ëÏÄ áÄÁÍÁÒÁ1 /нет1/2есть?нет1/21 /Рис. 3. Улучшение границы Синглтона.Код Адамара состоит из 2 кодовых слов длины , любые два изкоторых отличаются либо ровно в половине позиций (так что соответствующие векторы ортогональны), либо во всех позициях. Код Адамарастроится при = 2 . Для этого позиции в слове будем представлять себекак вершины -мерного булева куба B , а слова | как функции B → B.Такая функция задаётся своими значениями в 2 = вершинах, и этизначения образуют слово длины , надо только фиксировать какой-либопорядок на вершинах куба.В качестве кодовых слов возьмём аффинные функции, то есть функциивида⟨ , .

. . , ⟩ ↦→ + + . . . + при , . . . , ∈ B (умножение и сложение | как в поле из двух элементов). Такая функция задаётся набором своих коэффициентов, и потомуимеется 2 = 2 аффинных функций.Две такие функции либо различаются во всех точках (если отличаютсялишь коэффициентом ), либо ровно в половине точек (образующихаффинное подпространство коразмерности 1 над полем B). Код Адамарапостроен.С точки зрения структуры евклидова пространства R , о котором мыговорили в разделе 13, кодовые слова кода Адамара являются плюс-минус базисными векторами ортонормированного базиса (замена знака соответствует добавлению единицы к аффинной функции, то есть изменению100+10113115. ëÏÄ áÄÁÍÁÒÁ ).0Итак, к настоящему времени у нас есть три явные конструкции кодовдля двухбуквенного алфавита: код Хэмминга, код Форни { Юстесена { Возенкрафта и код Адамара.

Код Хэмминга имеет коэффициент полезногодействия, близкий к 100%, но исправляет только одну ошибку. Напротив, код Адамара исправляет почти что максимально возможное числоошибок (до 25%), но зато имеет очень малый коэффициент полезногодействия. Код Форни занимает промежуточное положение: у него и доляисправляемых ошибок, и коэффициент полезного действия отделены отнуля, хотя и невелики.Для больших алфавитов ситуация лучше: там код Рида { Соломонапри подходящем выборе параметров позволяет достичь любого заданногокоэффициента полезного действия и исправляет при этом максимальновозможное (по неравенству Синглтона) число ошибок.Мы знаем, что в коде Адамара кодовое расстояние равно 50%. Однако у кода Адамара длина кодового слова экспоненциальнобольше длины исходного сообщения ( = 2 ).

Если мы хотим явно указать код, у которого кодовое расстояние приближается к 50% (и границеПлоткина), а длина кодовых слов полиномиальна (от длины кодируемогосообщения), то можно использовать каскадный код, в котором внутренним кодом является код Адамара, а внешним | код Рида { Соломона.Замечание.В самом деле, рассмотрим код Адамара с 2 кодовыми словами размера 2 . Используя его как внутренний код, мы получаем для внешнегокода алфавит из 2 символов. Для простоты записи формул пожертвуем половиной и будем использовать лишь 2 из них. Зафиксируем некоторое > 0. Внешний код Рида { Соломона будет кодировать 2 такихсимволов (блоков из битов) с помощью 2 символов (блоков), каждыйиз которых при внутреннем кодировании изображается 2 битами.(Другими словами, мы разбиваем слово из log битов, где = 2 ,на блоков размера log , и считаем каждый блок элементом F .

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

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

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

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