Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-12-12 | 84 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!