Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Оснащения врачебно-сестринской бригады.
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2017-12-12 | 85 |
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.
Избыточность этой схемы очень большая.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!