Блочный код
Главная характеристика блочного кода состоит в том, что это – канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана, и в отличие таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование) ). Обычно, система блочного кодирования получает на входе k-значное кодовое слово W, и преобразовывает его в n-значное кодовое слово C(W). Это кодовое слово и называется блоком.
Блочное кодирование было главным типом кодирования, используемого в ранних системах мобильной коммуникации.
Содержание
Формальное определение
Компромисс между эффективностью (большей скоростью передачи информации) и способностями исправления может также быть виден при попытке задать фиксированную длину ключевого слова, и фиксированную возможность исправления (представленную расстоянием Хемминга d) и максимизируют общее количество ключевых слов. [n, d] — максимальное число ключевых слов для данной длины ключевого слова n и расстояния Хемминга d.
Информационные нормы
.
.
Сферические упаковки и решетки
Блочные коды связаны с проблемой сферической упаковки, которая привлекла к себе внимания в последние годы. В двух измерениях её легко визуализировать, взяв горсть одинаковых монет и выстроив их на столе в виде шестиугольника, как в пчелиных сотах. Однако, блочные коды в больших измерениях также легко визуализировать не удастся. Сильный код Голея, используемый в коммуникациях открытого космоса, использует 24 измерения. Если используется двоичный код (как это обычно и делается) измерения обращаются к длине ключевого слова как определено выше.
Другим пунктом, который часто пропускается, является число соседей, которых может иметь единственное ключевое слово. Снова, давайте использовать монеты как пример. Сначала мы укладываем их в прямоугольной сетке. У каждой монеты будет 4 близких соседа (и 4 в наиболее удаленных углах). В шестиугольнике у каждой монеты будет 6 близких соседей. Когда мы увеличиваем количество измерений, число близких соседей растет очень быстро.
Инструменты сайта
Основное
Навигация
Информация
Действия
Содержание
Раздел создан при поддержке компании
Кодирование
Принципиальная схема цифровой системы связи изображена на рисунке
Эта же схема подходит и для описания системы хранения информации — если заменить процесс пересылки ко каналу связи на процесс записи информации на запоминающее устройство. Будем обобщенно говорить о коммуникации, имея в виду процессы передачи, отображения и сохранения информации. Как сами средства передачи данных, так и записывающие устройства находятся под воздействиями внешних помех (природного или искусственного происхождения). Будем говорить о таких воздействиях как о шуме.
Шеннон [1] показал, что имеется принципиальная возможность использования дискретного зашумленного канала для передачи информации со сколь угодно большой степенью надежности и с любой скоростью, не превосходящей пропускную способность канала. Он также показал, что задачу надежной коммуникации можно разложить на две подзадачи:
Приведенная выше схема детализируется:
Под кодированием канала (телефонного кабеля, спутниковой антенны, оптического диска, запоминающего устройства компьютера и т.п.) понимается преобразование входной информации как набора информационных символов в другой набор символов, имеющий бóльшую длину. За счет этого увеличения длины — за счет избыточности — появляется возможность осуществления проверки информации по прохождению ею канала связи на предмет ее тождественности входной. Полученная информация должна позволять (в идеале однозначно, а на практике — с известной вероятностью ошибки) восстановить входную информацию.
Под кодированием источника (текст, изображение, звук) понимается преобразование входной информации в набор символов, более компактно (сжато) эту информацию описывающий.
Пример. Конспектирование студентом лекции можно считать кодированием лектора как источника звуковых сигналов и изображений (на доске или презентации).
Понятно, что при таком сжатии входной информации, может происходить частичная ее потеря. Проблема заключается в том, чтобы в результате процесса декодирования значительная (т.е. существенная для конкретных целей) часть входной информации была восстановлена адекватно.
Типы кодов
Блочные коды
Пример 1. Пусть алфавит языка состоит из пяти букв:
Этот пример служит примером кода, исправляющего ошибки — в данном случае одну ошибку.
декодирование всегда производить в «ближайший» кодовый блок.
Подробнее — в разделе ☞ КОД ХЭММИНГА.
Префиксные (древовидные) коды
Пример. Пусть кодирование производится по правилу:
Пример. Код
Префиксный код называется примитивным, если его невозможно сократить, т.е. если при вычеркивании любого знака хотя бы в одном кодовом слове код перестает быть префиксным.
Приведите пример непримитивного префиксного кода.
| а | б | в | г | д | е | ж | з | и | к |
|---|---|---|---|---|---|---|---|---|---|
| 00 | 01 | 1000 | 1001 | 101 | 110 | 1110 | 11110 | 111110 | 111111 |
Граф кода называется его деревом, отсюда идет другое название префиксных кодов — древовидные.
Кодирование для чайников, ч.1
Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).
Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.
0. Начало
Давайте рассмотрим некоторые более подробно.
1.1 Речь, мимика, жесты
1.2 Чередующиеся сигналы
В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы «включено/выключено». Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.
1.3 Контекст
2. Кодирование текста
Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.
Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.
Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».
2.1 Блочное кодирование
Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:
Блокировать код
содержание
строительство
Для кодов в литературе установлены разные обозначения:
Далее будет сделана попытка сохранить это, а также использование имен переменных в этой статье, а также в связанных статьях.
Существуют оценки того, могут ли коды быть возможными или нарушать определенные принципы:
Границы указывают на то, могут ли коды существовать, а не на то, могут ли они быть построены и действительно существовать.
Типы блочных кодов
Основное преимущество линейных кодов состоит в том, что их легко кодировать и декодировать.
Информационная скорость блочных кодов
Если код линейный, скорость передачи информации составляет:
Примеры блочных кодов
Код повтора
Код четности
Код Адамара
Еще примеры блочных кодов
пример 1
Пример 2
Это линейный систематический код с базой
Пример 3
Исправлена ошибка
Например, если вы используете присвоение в случае двоичного кодирования
| Информационное слово | кодовое слово |
|---|---|
| 0 | 000 |
| 1 | 111 |
Полученные кодовые слова с ровно одной битовой ошибкой могут быть исправлены путем реверсирования отклоняющегося бита с помощью мажоритарной функции :
| Неверное кодовое слово | Исправленное кодовое слово | Связанное информационное слово |
|---|---|---|
| 00 1 | 00 0 | 0 |
| 0 1 0 | 0 0 0 | 0 |
| 0 11 | 1 11 | 1 |
| 1 00 | 0 00 | 0 |
| 1 0 1 | 1 1 1 | 1 |
| 11 0 | 11 1 | 1 |
Однако, если в этом случае два бита неверны, ошибка распознается, но исправляется неправильно. Если три бита ошибочны, ошибка больше не может быть распознана.
Что такое блочный код
Решение. Если это условие на выполнено, то в качестве следует взять функцию (ближайшее слово из образа ), которая исправит ошибки в позициях.
Она отвечает умножению строки на кодированную матрицу справа и определяет ( )-код.
Код не должен приписывать одно и то же кодовое слово разным словам. Одним из способов добиться этого состоит в том, чтобы первые столбцов матрицы образовали единичную матрицу.
Пример 149. Построить (3,5)-код, используя следующую 355 матрицу:
Решение. Полный список кодирования таков:
| = 000 00000 | = 110 11001 |
| = 100 10010 | = 101 10111 |
| = 010 01010 | = 011 01110 |
| = 001 00101 | = 111 11100 |
Этот список показывает преимущество матричного кодирования: достаточно запомнить кодовых слов вместо слов.
где в качестве выбирается слово наименьшего веса, называемого лидером этого класса.
Пример 150. Составить таблицу декодирования для (3,5)-кода из предыдущего примера.
| 00000 | 10010 | 01010 | 00101 | 11001 | 10111 | 01110 | 11100 |
| 10000 | 00010 | 11010 | 10101 | 01001 | 00111 | 11110 | 01100 |
| 01000 | 11010 | 00010 | 11101 | 10001 | 11111 | 00110 | 10100 |
| 00100 | 10110 | 01110 | 00001 | 11101 | 10011 | 01010 | 11000 |
Чтобы декодировать принятое слово, следует отыскать его в таблице и выбрать в качестве переданного кодовое слово из того же столбца и из первой строки.
Вопросы для самоконтроля
1. Как определяется вес слова?
2. Какая связь между кодовым расстоянием и весом слова?
3. Существует ли связь между вероятностью принятия переданного слова и расстоянием между переданным и принятым словами?
4. Необходимые и достаточные условия обнаружения ошибок.
5. Назовите условия исправления ошибок.
6. В чем заключается методика матричного кодирования?
7. Какой код называется групповым?
8. Геометрические интерпретации кодирующих и декодирующих систем.
I 291. Докажите, что если расстояние между кодовыми словами равно 5, то код способен обнаруживать до четырех ошибок и исправлять до двух ошибок.
292. Какова вероятность того, что не будет обнаружена ошибка при пере-даче слова в (6,7)-коде с проверкой на четность?
293. Вычислите вероятность пропуска ошибок в таком (4,8)-коде, что минимальное расстояние между кодовыми словами равно 4.
294. Рассмотрите (3,4)-код с проверкой на четность и (3,6)-код с двукратной передачей. При вычислите вероятность того, что ошибочно переданное слово не будет обнаружено.
295. Найдите кодирующую матрицу для (3,4)-кода с проверкой на четность.
296. Найдите кодирующую матрицу для (2,6)-кода с трехкратной передачей.
II 297. Код задан матрицей
Какова вероятность того, что слово будет принято как правильное, тогда как на самом деле остались необнаруженными ошибки?
298. Постройте стандартную матрицу, порождающую код, эквивалентный коду с матрицей
III 299. Покажите, что следующие операции над кодирующей матрицей приводят к эквивалентному коду:
а) перестановка строк,
б) перестановка столбцов,
в) замена одной строки суммой ее с другой строкой.
