WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 11 | 12 ||

Сущность кода Хэмминга заключается в том, что местоположение контрольных и информационных битов определяется по правилу, которое устанавливает зависимость, позволяющую в случае ошибки определить ее местоположение, т.е. номер бита.

Основные положения для получения кода Хэмминга состоят в следующем:

1. Число, составленное из контрольных разрядов, должно указывать номер бита, в котором произошла ошибка, или 0, если нет ошибки. Исходя из этого, если произошла ошибка, проверочное С – битовое число – должно быть в диапазоне от 1 до 2С – 1. Из этого следует, что 2С – 1N; тогда 2СN+1; умножим левую и правую части на 2M, получим 2M*2С2M*(N+1), откуда 2(M+C)2M*(N+1), тогда 2N2M* (N+1); делим левую и правую части на (N+1), получаем условие (2N/(N+1))2M.

С использованием этого условия и определяется минимально необходимое число контрольных битов для передачи заданного количества информационных.

2. Контрольные биты в коде Хэмминга занимают позиции с номерами, равными 2n, где n=0,1,3,… и т.д. Причем позиции кода номеруются справа налево, начиная с 1. Информационные биты располагаются в остающихся позициях справа налево по возрастанию весов разрядов.

3. Значение каждого контрольного бита получается сложением по модулю 2 тех информационных битов, для которых в номере кодовой позиции информационных битов, записанном через контрольные разряды, значение бита равно 1. Эта формулировка будет более понятна, если посмотреть ее использование по табл. 6.1 или 6.2.

Вначале построим код Хэмминга для передачи четырехбитового кода.

Условие 1. Это условие будет выполняться при N=7:

{27/(7+1)=128/8=16}{24=16}.

Таким образом, для четырех информационных битов (М=4) требуются три контрольных бита (С=3).

Условие 2. Определяем местоположение информационных и контрольных битов в коде.

Положение информационных М4 М3 М2 С3 М1 С2 Си контрольных битов Номер позиции кода 7 6 5 4 3 2 Условие 3. Определяем логические выражения для вычисления контрольных битов. Для этого построим таблицу.

Таблица 6.Вычисление контрольных битов для кода (7,4) Контрольные биты Позиция кода С3 С2 С3 (бит М1) 0 1 5 (бит М2) 1 0 6 (бит М3) 1 1 7 (бит М4) 1 1 Суммируемые по модулю 2 биты М2 М1 ММ3 М3 ММ4 М4 МТаким образом, передатчик вычисляет значения контрольных разрядов по следующим логическим выражениям:

С1=М1^М2^М4;

С2=М1^М3^М4;

С3=М2^М3^М4.

Приемник проверяет правильность принятого кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4;

С12=С2^М1^М3^М4;

С13=С3^М2^М3^М4.

Построим код Хэмминга для передачи семибитового кода.

Условие 1. Это условие будет выполняться при N=11:

{211/(11+1)=2048/12170}{27=128}.

Таким образом, для семи информационных битов (М=7), требуются четыре контрольных бита (С=4).

Условие 2. Определяем местоположение информационных и контрольных битов в коде.

Положение информационных М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 Си контрольных битов Номер позиции 11 10 9 8 7 6 5 4 3 2 кода Условие 3. Определяем логические выражения для вычисления контрольных битов. Для этого построим таблицу.

Таблица 6.Вычисление контрольных битов для кода (11,4) Контрольные биты Позиция кода С4 С3 С2 С3 (бит М1) 0 0 1 5 (бит М2) 0 1 0 6 (бит М3) 0 1 1 7 (бит М4) 0 1 1 9 бит (М5) 1 0 0 10 (бит М6) 1 0 1 11 (бит М7) 1 0 1 Суммируемые по модулю 2 М5 М2 М1 Мбиты М6 М3 М3 ММ7 М4 М4 ММ6 ММ7 МТаким образом, передатчик вычисляет значения контрольных разрядов по следующим логическим выражениям:

С1=М1^М2^М4^М5^М7;

С2=М1^М3^М4^М6^М7;

С3=М2^М3^М4;

С3=М5^М6^М7.

Приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4^М5^М7;

С12=С2^М1^М3^М4^М6^М7;

С13=С3^М2^М3^М4;

С14=С4^М5^М6^М7.

Рассмотрим примеры передачи информации с использованием кода Хэмминга для случаев, когда ошибки при передаче нет и когда есть.

Начнем с кода (7,4).

Пример. В канал связи нужно передать следующий блок информации:

1101(2).

Передатчик формирует код Хэмминга:

М4 М3 М2 С3 М1 С2 С1 1 0 * 1 * * С1=М1^М2^М4=1^0^1=0;

С2=М1^М3^М4=1^1^1=1;

С3=М2^М3^М4=0^1^1=0, тогда код, передаваемый в канал, будет:

М М М С М С С 4 3 2 3 1 2 1 1 0 0 1 1 Рассмотрим случай, когда не было ошибки при передаче кода.

Тогда точно такой же код принял приемник. Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4=0^1^0^1=0;

С12=С2^М1^М3^М4=1^1^1^1=0;

С13=С3^М2^М3^М4=0^0^1^1=0.

Поскольку значение, составленное из контрольных битов, равно нулю, ошибки нет, и код передается от приемника далее.

Рассмотрим случай, когда была ошибка при передаче кода.

Пусть ошибка произошла в третьем бите, т.е. принят код:

М4 М3 М2 С3 М1 С2 С1 1 0 0 0 1 Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4=0^0^0^1=1;

С12=С2^М1^М3^М4=1^0^1^1=1;

С13=С3^М2^М3^М4=0^0^1^1=0.

Поскольку, значение, составленное из контрольных разрядов, равно 011(2), ошибка в бите № 3. Приемник меняет значение этого бита на противоположное.

Теперь рассмотрим код (11,7).

Пример. В канал связи нужно передать следующий блок информации:

1101010(2).

Передатчик формирует код Хэмминга:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 1 0 * 1 0 1 * 0 * * С1=М1^М2^М4^М5^М7=0^1^1^0^1=1;

С2=М1^М3^М4^М6^М7=0^0^1^1^1=1;

С3=М2^М3^М4=1^0^1=0;

С4=М5^М6^М7=0^1^1=0, тогда код, передаваемый в канал, будет:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 1 0 0 1 0 1 0 0 1 Рассмотрим случай, когда не было ошибки при передаче кода.

Тогда точно такой же код принял приемник. Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4^М5^М7=1^0^1^1^0^1=0;

С12=С2^М1^М3^М4^М6^М7=1^0^0^1^1^1=0;

С13=С3^М2^М3^М4=0^1^0^1=0;

С14=С4^М5^М6^М7=0^0^1^1=0.

Поскольку значение, составленное из контрольных битов, равно нулю, ошибки нет, и код передается от приемника далее.

Рассмотрим случай, когда была ошибка при передаче кода.

Пусть ошибка произошла во втором бите, т.е. принят код:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 1 0 0 1 0 1 0 0 0 Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4^М5^М7=1^0^1^1^0^1=0;

С12=С2^М1^М3^М4^М6^М7=0^0^0^1^1^1=1;

С13=С3^М2^М3^М4=0^1^0^1=0;

С14=С4^М5^М6^М7=0^0^1^1=0.

Поскольку значение, составленное из контрольных битов, равно 0010(2), ошибка во втором бите. Приемник меняет значение этого бита на противоположное.

Код Хэмминга является равномерно защищенным, исправляет ошибки как в информационных, так и в контрольных битах. С его помощью возможно исправление одиночной и обнаружение двойной ошибки. Для того чтобы обнаружить двойную ошибку, в код Хэмминга вводят дополнительный контрольный бит E0. Значение E0 вычисляется как сумма по модулю 2 всех разрядов кода Хэмминга, т.е.

он дополняет код Хэмминга по четности. На стороне приемника, кроме получения контрольных разрядов, которые определяют позицию с ошибкой, вычисляется контрольный разряд E10:

E10=Е0^<сложенные по модулю 2 все остальные биты принятого кода>.

Если E10=0, то ошибок нет. Если значение, полученное из контрольных разрядов, не равно 0 и E10=1, то имеет место одиночная ошибка, позиция которой определяется значением контрольных разрядов. Если значение С0 и E10=0, то имеет место двойная ошибка.

Рассмотрим пример для кода, исправляющего одиночную ошибку и обнаруживающего двойную.

Для кода (11,7) формат блока информации:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 ЕПример. В канал связи нужно передать следующий блок информации:

1101010(2).

Передатчик формирует код Хэмминга:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 Е1 1 0 * 1 0 1 * 0 * * * С1=М1^М2^М4^М5^М7=0^1^1^0^1=1;

С2=М1^М3^М4^М6^М7=0^0^1^1^1=1;

С3=М2^М3^М4=1^0^1=0;

С4=М5^М6^М7=0^1^1=0;

Е0=С1^С2^М1^С3^М2^М3^М4^С4^М5^М6^М7=1^1^0^0^1^0^1^0^0^1^1=0, тогда код, передаваемый в канал, будет:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 Е1 1 0 0 1 0 1 0 0 1 1 Рассмотрим случай, когда не было ошибки при передаче кода.

Тогда точно такой же код принял приемник. Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4^М5^М7=1^0^1^1^0^1=0;

С12=С2^М1^М3^М4^М6^М7=1^0^0^1^1^1=0;

С13=С3^М2^М3^М4=0^1^0^1=0;

С14=С4^М5^М6^М7=0^0^1^1=0;

Е10=Е0^С1^С2^М1^С3^М2^М3^М4^С4^М5^М6^М7= =0^1^1^0^0^1^0^1^0^0^1^1=0.

Поскольку значение, составленное из контрольных битов, равно 0, и Е10=0, ошибки нет, и код передается от приемника далее.

Рассмотрим случай, когда была одиночная ошибка при передаче кода. Пусть ошибка произошла во втором бите (не считая Е0, т.е. в С2) и принят код:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 Е1 1 0 0 1 0 1 0 0 0 1 Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4^М5^М7=1^0^1^1^0^1=0;

С12=С2^М1^М3^М4^М6^М7=0^0^0^1^1^1=1;

С13=С3^М2^М3^М4=0^1^0^1=0;

С14=С4^М5^М6^М7=0^0^1^1=0;

Е10=Е0^С1^С2^М1^С3^М2^М3^М4^С4^М5^М6^М7= =0^1^0^0^0^1^0^1^0^0^1^1=1.

Поскольку значение Е10=1 и значение, составленное из контрольных разрядов, равно 0010(2), то ошибка во втором бите. Приемник меняет значение этого бита на противоположное.

Рассмотрим случай, когда была двойная ошибка при передаче кода. Пусть ошибка произошла во втором (т.е. в С2) и в пятом битах (т.е. М2) и принят код:

М7 М6 М5 С4 М4 М3 М2 С3 М1 С2 С1 Е1 1 0 0 1 0 0 0 0 0 1 Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:

С11=С1^М1^М2^М4^М5^М7=1^0^0^1^0^1=1;

С12=С2^М1^М3^М4^М6^М7=0^0^0^1^1^1=1;

С13=С3^М2^М3^М4=0^0^0^1=1;

С14=С4^М5^М6^М7=0^0^1^1=0;

Е10=Е0^С1^С2^М1^С3^М2^М3^М4^С4^М5^М6^М7= =0^1^0^0^0^0^0^1^0^0^1^1=0.

Поскольку значение Е10=0 и значение, составленное из контрольных разрядов, равно 0111(2)0, то произошла двойная ошибка. Приемник не передает код далее, а запрашивает от источника повторную передачу этого блока информации.

Заключение При создании пособия авторы руководствовались идеей, что предлагаемый теоретический материал, иллюстрированный подробными практическими примерами, окажет существенную помощь читателю в изучении основ арифметики цифровых процессоров. Именно основ, так как в современных процессорах используются более сложные алгоритмы выполнения арифметических операций. Но чтобы разобраться в них, надо получить базовые знания, которые и дает это пособие.

Авторы надеются, что после изучения пособия читатель будет уверенно чувствовать себя в таких вопросах, как форматы представления операндов, кодирование операндов, алгоритмы арифметических операций, контроль арифметических операций, контроль передачи данных. Надеемся, что полученные знания будут успешно использованы для решения практических задач.

Авторами тщательно выверялись все примеры пособия, но если внимательный читатель обнаружит ошибки или сделает замечания по структуре пособия, мы примем и рассмотрим их для исправления в возможных последующих изданиях.

Список литературы 1. Борисова, М. В. Основы информатики и вычислительной техники / М. В. Борисова. – М. : Феникс, 2006. – 544 с.

2. Каймин, В. А. Информатика / В. А. Каймин. – М. : ИНФРА-М, 2006. – 284 с.

3. Цилькер, Б. Я. Организация ЭВМ и систем : учеб. для вузов / Б. Я. Цилькер. – СПб. : Питер, 2006. – 668 с.

4. Хамахер, К. Организация ЭВМ / К. Хамахер, З. Вранешич, С. Заки. – 5-е изд. – СПб. : Киев : Питер; Издательская группа BHV, 2003. – 848 с.

5. Гук, М. Аппаратные средства IBM PC : энциклопедия / М. Гук. – СПб. : Питерком, 1999. – 816 с.

6. Сергеев, Н. П. Основы вычислительной техники / Н. П. Сергеев, Н. П. Вашкевич. – 2-е изд. – М. : Высш. шк., 1988. – 360 с.

7. Майоров, С. А. Структура электронных вычислительных машин / С. А. Майоров, Г. И. Новиков. – Л. : Машиностроение, 1979. – 384 с.

8. Соловьев, Г. Н. Арифметические устройства ЭВМ / Г. Н. Соловьев. – М. : Энергия, 1978. – 176 с.

9. Соренков, Э. И. Точность вычислительных устройств и алгоритмов / Э. И. Соренков, А. И. Телича, А. С. Шаталов. – М. : Машиностроение, 1976. – 200 с.

10. Кнут, Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы / Д. Кнут. – М. : Мир, 1977. – 724 с.

11. Карцев, М. А. Вычислительные системы и синхронная арифметика / М. А. Карцев, В. А. Брик. – М. : Радио и связь, 1981. – 360 с.

12. Рабинер, Л. Теория и применение цифровой обработки сигналов / Л. Рабинер, Б. Гоулд. – М. : Мир, 1978. – 848 с.

Учебное издание Вашкевич Николай Петрович, Калиниченко Евгений Иванович Основы арифметики цифровых процессоров Учебное пособие Редактор О. Ю. Ещина Технический редактор Н. А. Вьялкова Корректор Н. А. Сидельникова Компьютерная верстка М. Б. Жучковой Сдано в производство 22.01.10. Формат 60x841/16.

Усл. печ. л. 9,3. Уч.-изд. л. 11,1.

Тираж 50. Заказ № 19.

Издательство ПГУ.

440026, Пенза, Красная, 40.

Pages:     | 1 |   ...   | 11 | 12 ||






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.