- •Оглавление
- •1.1 Информатика
- •1.2 Информация
- •1.3 Кодирование информации. Мера информации
- •1.4 Преобразование информации
- •1.5 Формы представления информации
- •1.6. Передача информации
- •Глава 2. Общие принципы организации и работы компьютеров
- •2.1 Принцип построения компьютера, структура компьютера
- •2.2 Команда, форматы команд
- •2.3 Эвм как автомат
- •2.4 Архитектура эвм
- •2.5 Классы компьютеров. Классификация компьютеров
- •Глава 3. Алгоритмы. Алгоритмизация
- •3.1 Абстрактные автоматы и понятие алгоритма
- •3.2 Формы записи алгоритмов.
- •3.3 Характеристики алгоритма
- •3.4 Исполнители алгоритма
- •Глава 4. Арифметические основы эвм.
- •4.1 Системы счисления
- •4.2 Перевод чисел из одной системы счисления в другую.
- •4.3 Перевод из 10-ной системы счисления в р-ную.
- •4.4 Перевод чисел из р-ичной системы счисления в десятичную.
- •4.5 Системы счисления с основаниями, являющимися степенью 2.
- •Двоично-шестнадцатеричная система счисления.
- •Глава 5. Представление данных в памяти эвм.
- •5.1 Проблемы представления данных
- •5.2 Формы представления чисел в эвм.
- •5.3 Прямой, обратный и дополнительный коды.
- •5.4 Представление чисел с плавающей точкой.
- •5.5 Кодирование текстовой и графической информации .
- •Глава 6. Логические основы эвм
- •6.1 Основные понятия алгебры логики.
- •6.2 Основные логические операции.
- •6.3 Основные законы и соотношения алгебры логики.
- •6.4 Логические функции двух переменных.
- •6.5 Свойства функций алгебры логики
- •6.6 Аналитическое представление логических функций.
- •6.7 Системы функций алгебры логики.
- •Рассмотрим практическое применение изложенного материала.
- •Решение логических задач с помощью таблиц истинности.
- •Задачи для самостоятельного решения.
- •6.8 Понятия о комбинационных схемах и цифровых автоматах
- •Пример 1.
- •Пример 2.
- •Пример 3.
- •Пример 4.
- •Глава 7. Контроль работы цифрового автомата
- •7.1 Кодирование информации как средство обеспечения контроля работы автомата
- •7.2 Методы эффективного кодирования информации
- •7.3 Кодирование по методу четности-нечетности
- •7.3 Коды Хэминга
- •Глава 8. Прикладное программное обеспечение
- •9.1 Текстовые редакторы
- •9.2 Электронные таблицы
- •9.3 Система управления базами данных (субд) Основные функции субд
- •Глава 9. Методические рекомендации по решению задач в курсе информатики
- •9.1 Измерение информации. Вероятностный подход.
- •9.2 Арифметические основы эвм.
- •9.3 Представление числовых данных в памяти эвм.
- •9.4 Логические основы эвм.
- •9.5 Алгоритмизация
- •Список литературы
7.3 Коды Хэминга
Коды, предложенные американским ученым Р. Хэмингом, способны не только обнаружить, но и исправить одиночные ошибки. Эти коды — систематические.
Основная идея состоит в добавлении к информационным битам несколько битов чётности, каждый из которых контролирует определённые информационные биты. Если пронумеровать все передаваемые биты, начиная с первого слева направо ( напомним, что информационные биты нумеруются с нуля и справа налево), то контрольными оказываются биты, номера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8 – разрядного информационного кода контрольными окажутся разряды с номерами 1,2,4,8.
Номера контролируемых битов для каждого проверочного приведены в табл. 7.2.
Таблица 7.2.
Проверочные биты |
Контролируемые биты |
1 |
1,3,5,7,9,11,13,15, 17, 19, 21,… |
2 |
2,3,6,7,10,11,14,15,18,19,22,… |
4 |
4,5,6,7,12,13,14,15,20,21,22, 23,… |
8 |
8,9,10,11,12,13,14,15,24,25, 26,… |
16 |
16, 17, 18, 19,20, 21, 22, 23, 24, 25, 26,… |
32 |
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, … |
Легко усматривается принцип выделения контролируемых разрядов: для любого номера проверочного разряда (n), начиная с него, n разрядов подряд оказываются проверяемыми, затем группа n непроверяемых разрядов,далее происходит чередование групп.
Пример 7.2. Пусть вместо последовательности 0 0 0 1 1 1 0 1 1 1 0 1 пришла следующая:
0 0 0 1 0 1 0 1 1 1 0 1
1 2 3 4 5 6 7 8 9 10 11 12
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
Анализируем состояния контрольных битов в соответствии с табл. 7.2.
Бит 1 – неверно, т.е. ошибка находится в каком – либо бите с нечётным номером.
Бит 2 – верно, следовательно, биты с нечётными номерами 3, 7, 11 – верны (т.е. – ошибка в 5 или 9).
Бит 4 – неверно, значит ошибка может содержаться только в 5- м бите.
Таким образом, однозначно устанавливается, что ошибочным является 5 –й разряд, остаётся исправить его значение на противоположное и, тем самым, восстановить правильную последовательность.
На основании сказанного можно сформулировать простой алгоритм проверки и исправления передаваемой последовательности бит в представлении Хемминга:
произвести проверку всех битов чётности;
если все биты чётности верны, то перейти к п.5;
вычислить сумму номеров всех неправильных битов чётности;
инвертировать содержимое бита, номер которого равен сумме, найденной в п.3;
исключить биты чётности, передать правильный информационный код.
Избыточность кодов Хемминга для различных длин передаваемых последовательностей приведена в табл. 7.3.
Таблица 7.3.
Число информационных битов |
Число контрольных битов |
Избыточность |
8 |
4 |
1.50 |
16 |
5 |
1.31 |
32 |
6 |
1.06 |
Из сопоставления видно, что выгоднее передавать и хранить более длинные последовательности битов. Безусловно, данный способ кодирования требует увеличения объёма памяти компьютера приблизительно на одну треть при 16 – битной длине машинного слова, однако, использование кодов Хемминга позволяет автоматически исправлять одиночные ошибки.