Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-12-12 | 81 |
5.00
из
|
Заказать работу |
|
|
Для построения и исследования кодов необходимо иметь информацию о структуре кода (расположении его точек в булевом кубе), а для этого необходимо ввести метрику.
Схемы кодирования могут быть самые разные. Рассмотрим одну из самых известных. (Она считается наиболее естественной и соответствующей практическим задачам.)
В ее основе лежит два принципа:
1. Принцип наибольшего правдоподобия. Этот принцип вытекает из очевидного соотношения
pn<pn- 1(1 -p) <pn- 2(1 -p)2 < … < (1 -p) n (*)
и говорит о том, что вероятность k ошибок с кодовом слове меньше, чем вероятность sошибок для всехs>k.
2. Принцип избыточности.
Мы в нашем рассмотрении не затрагиваем протокольные вопросы, а ограничиваемся чисто алгоритмическими, т.е кодер и декодер в процессе передачи не ведут между собой никакого диалога (например, не могут перезапрашивать один раз уже переданные символы и т.п.) В этом случае алгоритм декодирования по принятой информации исправлять ошибки, которые возникли при передаче. Но, если кодер просто передает в канал информацию, подлежащую передаче, ничего к ней не добавляя, то у декодера нет никакой возможности исправить ошибки. Таким образом, принцип избыточности заключается в том, что для защиты передаваемой информации используется дополнительная информация.
Мы считаем, что все кодовые слова имеют одинаковую длину. (Это вектора пространства Bn). Информация, подлежащая передаче может быть представлена в виде последовательности двоичных слов длины k (k<n). Кодер берет эти слова и преобразует в слова длины n.Здесь и возникает избыточность за счет (n-k) символов.
Если кодер просто добавляет к словам, подлежащим передаче эти (n-k) символов, то они называются проверочными символами, а исходные kсимволов – информационными.
|
Так построенный код называется систематическим кодом.
Однако, надо заметить, что далеко не всегда избыточность реализуется столь простым способом. Поэтому принцип избыточности заключается в том, что для защиты от ошибок в канале к информации, подлежащей передаче, что-то добавляется. За счет этой добавки декодер имеет возможность выяснить, произошли ли ошибки и, если произошли, то исправить их.
Проиллюстрируем сказанное.
Пусть, например, информация, подлежащая передаче, - это битовый поток, подающийся на вход кодера. Кодер нарезает ее в виде последовательности слов длины k. Таким образом можно считать, что передаче в канал подлежат все возможные слова длины k, т.е. вектора пространства Bk, таких словам M=2 k. Кодер преобразует вектора пространстваBk в вектора пространстваBn.Таким образом реализуется принцип избыточности.
В общем случае мы имеем Mслов, подлежащих передаче, которые могут быть идентифицированы с помощью битовых векторов, длины меньшей n.
Обозначим эти слова через α1,α2,…,αM, а сопоставленные им векторапространства Bn(кодовые вектора) через x1,x2,…,xM.
Опр. Отображениеφ, ставящее в соответствие αi,i=1,…,M, вектор из Bnи называется кодированием или просто кодом.
Так как мы рассматриваем ситуацию защиты информации от помех в канале, то для таких кодов используются следующие названия: корректирующий код, код с исправлением ошибок, код с обнаружением ошибок и т.п.
К нему предъявляются естественные требования дешифруемости и неизбыточности. То есть, если φ(αi)=xi, то кодер и декодер всегда «знают» (умеют вычислять), что Но не это является основной проблемой при построении кодов, исправляющих ошибки. Дело в том, что переданное кодером в канал слово xi в результате искажения может превратиться в какое-то слово Yi (это тоже вектор из Bn).
Основная задача кодирования. Отображение φ должно быть построено таким образом, чтобы можно было сконструировать алгоритм преобразования Yiв αi. Это и будет исправлением ошибок. Поэтому под декодированием (дешифруемостью) в коде, исправляющем ошибки понимается именно данное преобразование. (Обозначим это преобразование через ψ).
|
Построение каждого такого кода – это отдельное достижение в математике, поэтому принято кодам давать имена их создателей: код Хэмминга, код Боуза- Чаудхури-Хоквингема (БЧХ-код), коды Гоппа и т.д.
Интуитивно ясно, что чем хуже канал (больше вероятность ошибки), тем большая требуется избыточность. Поэтому каждый код может исправить только ограниченное количество ошибок в слове определенной длины. Например, если код может исправлять не более двух ошибок в слове длины n=10, то при передаче информации по каналу сp=1/3 этот код не сможет всегда исправлять все ошибки (ниже будет показано, что среднее количество ошибок в слове в таком канале равно 3). Если же этот код используется в канале с p=1/1000, то такой код свои задачи выполнит (с вероятностью, близкой к единице). Таким образом, коды подбираются в соответствии с характеристиками канала.
Пример.
Мажоритарное кодирование – схема, где передатчик просто повторяет слово, подлежащее передаче в канал, p=2q+1 >1 раз. Приемник – декодер берет экземпляров полученного слова и каждую позицию в слове дешифрует в тот символ (0 или 1). Который встречается в большей части экземпляров.
Например, двухбитовой слово a = 11 → 11|10|11|00|11|11|11 – передали по каналу 7 раз.
На первой позиции 6 раз «1» и 1 раз «0» a = 1х.
На второй позиции 5 раз «1» и 2 раза «0» a = 11.
Избыточность этой схемы очень большая.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!