- •Федеральное агентство по образованию
- •1.2. Измерение информации
- •1.2.1. Структурные меры информации
- •1.2.2. Статистическая мера информации.
- •2. Кодирование информации
- •2.1. Контрольная работа – часть 1
- •2.1.1. Позиционные системы счисления
- •2.1.2. Смешанные системы счисления
- •2.1.3. Перевод числа из одной системы счисления в другую
- •2.1.4. Код Грея
- •2.1.5. Форма постановки задания
- •2.1.6. Рекомендации по решению задач
- •2.1.7. Примеры решения задач
- •2.1.8. Пример задания по контрольной работе – часть 1
- •2.2. Контрольная работа – часть 2
- •2.2.1. Избыточность сообщений
- •2.2.2. Теоретические основы эффективного кодирования
- •2.2.3. Построение эффективного кода по методам Шеннона-Фано и Хаффмена
- •2.2.4. Теоретические основы помехоустойчивого кодирования
- •2.2.5. Классификация помехоустойчивых кодов
- •2.2.6. Общие принципы использования избыточности при построении корректирующих кодов
- •2.2.7. Коды, обнаруживающие ошибки
- •2.2.8. Примеры решения задач
- •2.2.9. Пример задания по контрольной работе – часть 2
- •2.3. Контрольная работа – часть 3
- •Краткие теоретические сведения
- •2.3.1. Линейные коды, обнаруживающие и исправляющие ошибки
- •2.3.2. Построение двоичного линейного кода
- •2.3.3. Кодирование
- •2.3.4. Синдромный метод декодирования
- •2.3.5. Кодирующее и декодирующее устройства
- •2.3.6. Матричное представление линейных кодов
- •2.3.7. Циклические коды
- •2.3.8. Выбор образующего многочлена
- •2.3.9. Формирование разрешенных кодовых комбинаций
- •2.3.10. Декодирование циклических кодов
- •2.3.11. Схемы деления на образующий многочлен
- •2.3.12. Примеры решения задач
- •2.3.13. Пример задания по контрольной работе – часть 3
- •3. Оформление контрольной работы
- •3.1. Пример оформления отчета по контрольной работе
- •4. Варианты заданий
2.3.5. Кодирующее и декодирующее устройства
Линейные корректирующие коды наиболее часто используются для исправления и обнаружения ошибок в цифровых устройствах обработки и хранения информации, где надежность кодирующих и декодирующих устройств соизмерима с надежностью самого вычислительного канала. В связи с этим кодирующее и декодирующее устройства здесь должны:
иметь минимальную сложность;
иметь минимальные задержки.
В наиболее полной степени эти требования выполняются при параллельной передаче информации, что в таких системах является приемлемым вследствие сравнительно малых расстояний между взаимодействующими блоками. Именно на этот способ передачи информации и ориентированы рассматриваемые ниже устройства. Схемы построены для контрольной матрицы (2.19).
Кодирующее устройство (кодер).
Кодирующее устройство реализует следующие уравнения для выполнения проверочных символов:
(2.20)
Рис. 2.2. Функциональная схема кодера
На вход кодера подается безизбыточная -значная () комбинация. В кодере с помощью сумматоров по модулю 2 () в соответствии с (2.19) вычисляются контрольные символы,,и присоединяются к информационным. В результате на выходе появляетсяn-значная () комбинация линейного кода. Задержка между моментом появления входной комбинации и окончанием формирования выходной определяется только временем распространения сигнала в одном сумматоре(сумматоры работают параллельно).
Декодирующее устройство (декодер).
Декодер выполняет следующие функции:
вычисляет синдром ошибки в принятом КВ;
дешифрирует синдром ошибки;
инвертирует ошибочный разряд.
Функциональная схема декодера представлена на рис. 2.3.
Рис. 2.3. Функциональная схема декодера
На вход декодера подается подлежащий декодированию КВ.
Схема вычисления синдрома собрана на сумматорах по модулю 2 и реализует следующие уравнения:
(2.21)
Если ошибка отсутствует, вектор синдрома состоит из одних нулей. На всех выходах дешифратора ДШ при этом будут нули.
При наличии ошибки вектор синдрома будет совпадать с одним из столбцов контрольной матрицы (2.19) и 1 появится только на выходе ДШ, соответствующем ошибочному разряду. В целом состояния выходов ДШ определяются следующей таблицей:
Входы |
Выходы | |||||
1 |
2 |
3 |
4 | |||
0 0 0 0 1 1 1 1 |
0 0 1 1 0 0 1 1 |
0 1 0 1 0 1 0 1 |
0 0 0 0 0 0 1 0 |
0 0 0 1 0 0 0 0 |
0 0 0 0 0 0 0 1 |
0 0 0 0 0 1 0 0 |
Исправление (инвертирование) искаженного информационного разряда осуществляется с помощью сумматоров по модулю 2 , выполняющих функции управляемых инверторов. Возможность такого использования сумматоров видна из таблицы его состояний:
Вход |
Выход | ||
0 1 0 1 |
0 0 1 1 |
0 1 1 0 |
Если рассматривать вход в качестве управляющего, а– информационного, то из таблицы видно, что приинформационный сигнал передается на выход без инверсии, а при– инвертируется. В рассматриваемой схеме декодера роль управляющих сигналов выполняют сигналы, поступающие с выходов ДШ.
Минимальная задержка между моментом появления КВ на входе декодера и моментом, когда исправленная информационная часть КВ может быть передана на обработку, определяется выражением: , где– время распространения сигнала в 4-хвходовом сумматоре ();– время распространения сигнала в ДШ;– время распространения сигнала в 2-хвходовом сумматоре ().