Концепция организации сетей

Коды Хэмминга.

Кодом Хэмминга называется (n, k) код, который задается матрицей проверок H(n, k), имеющей r=nk строк и 2r1 столбцов, причем столбцами H(n, k) являются все различные ненулевые двоичные последовательности длины г (rразрядные двоичные числа от 1 до 2r1).

Таким образом, код Хэмминга полностью задается количеством проверочных разрядов, n=2r1, k=2r r 1.

Зная вид матрицы Н(n, k), можно определить корректирующие свойства (n, k)кода Хэмминга. Так как при любых параметрах кода всегда найдутся три линейно зависимых столбца, а все столбцы различны, то dmin = 3. Следовательно, код может гарантийно исправлять одиночные и обнаруживать двукратные ошибки.

Код Хэмминга является совершенным кодом, т.е. исправляет все образцы ошибок первой кратности, число которых равно Сnl = n = 2r 1, и совпадает с количеством смежных классов в таблице кодирования.

При фиксированном r можно построить код Хэмминга любой длины (n2r 1) путем укорочения (n, k) кода.

Параметры кодов Хэмминга полной длины для различных значений r представлены в таблице 2. Очевидно, что минимальная длина кода Хэмминга, имеющая практическое значение, n = 3. С ростом n скорость передачи кода стремиться к 1.

Пример. Проверочная матрица кода Хэмминга (7,4) согласно определению равна

 0 1 1 1 1 0 0 0

Н(7,4) = 0 1 1 0 0 1 1 0

 0 1 0 1 0 1 0 1

dmin= 3, т.к. имеются три столбца, сумма которых равна нулю. Если проверочная матрица представляет собой упорядоченную запись различных десятичных чисел (т.е. 1, 2, ..., 2nk) в двоичной форме, то исправление однократных ошибок осуществляется в соответствии со следующим свойством: вычисленный синдром, представленный в десятичной форме, однозначно определяет номер позиции искаженного элемента.

Пример. Пусть передавалась кодовая комбинация (7,4)кода вида v=1100001, которая под воздействием ошибок трансформировалась в комбинацию z=1110001, т.е. возникла ошибка на пятой позиции.

 1 1 1 1 0 0 0 T 

Синдром S имеет вид S = z*Н T(n, k) = [1110001] * 1 1 0 0 1 1 0 = 101.

 1 0 1 0 1 0 1

Комбинация s =101 соответствует десятичному числу 5, поэтому, инвертируя элемент на пятой позиции комбинации z, получим передаваемую кодовую комбинацию v.

При использовании записи столбцов Н(n, k) в упорядоченной форме в качестве проверочных элементов целесообразно выбирать позиции с номером 2i (i=0, 1, К), в противном случае проверочные элементы должны соответствовать столбцам, имеющим в своем составе одну единицу. При таком выборе каждая строка матрицы соответствует проверочному соотношению.

Кодирующее устройство (7,4)кода Хэмминга представлено на рис. 19.13. Информационная комбинация поступает во входной регистр, после заполнения которого параллельно считывается в выходной регистр с одновременным формированием проверочных элементов с помощью сумматоров по модулю 2. Сформированная таким образом кодовая комбинация последовательно считывается с регистра.

Схема декодирующего устройства (7,4) кода Хэмминга в режиме исправления ошибок представлена на рис. 19.14. Принятая комбинация поступает в приемный регистр, затем параллельно считывается в вычислитель синдрома, представляющий собой совокупность nk сумматоров. Сформированный синдром поступает в дешифраторы, количество которых равно 2nk 1. Если синдром ненулевой, то на выходе одного из дешифраторов появляется 1, которая заносится в соответствующий разряд регистра исправления. Затем осуществляется одновременное считывание информации с приемного регистра и регистра исправления с поразрядным суммированием по модулю 2. В результате с выхода снимается комбинация, записанная в приемный регистр, с инверсированным элементом на позиции искаженного символа.

Схема декодера (7,4)кода Хэмминга в режиме обнаружения ошибок представлена на рис. 19.15а. Принятая комбинация записывается в приемный регистр, после заполнения которого считывается в вычислитель синдрома. Если комбинация искажена, то ей будет соответствовать нулевой синдром, а на выходе формируется сигнал “Ошибка”.

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

Практическое использование кодов Хэмминга часто связано с применением к ним операций расширения и укорочения. При реализации операции расширения вводится, как правило, дополнительная проверка на четность, при этом в проверочной матрице появляется строка, состоящая из n+1 единицы, и минимальное кодовое расстояние становится равным dmin= 4, т.е. улучшается обнаруживающая способность кода. При укорочении (n, k) кода Хэмминга получают (ni, k1) код, корректирующая способность которого не меняется по сравнению с исходным кодом.

Микропроцессоры

   Центральный процессор (CPU, от англ Central Processing Unit) — это основной рабочий компонент компьютера, который выполняет арифметические и логические операции, заданные программой, управляет вычислительным процессом и координирует работу всех устройств компьютера. Центральный процессор в общем случае содержит в себе: -арифметико-логическое устройство;  -шины данных и шины адресов; -регистры; -счетчики команд; -кэш — очень быструю память малого объема (от 8 до 512 Кбайт); -математический сопроцессор чисел с плавающей точкой. Современные процессоры выполняются в виде микропроцессоров. Физически микропроцессор представляет собой интегральную схему — тонкую пластинку кристаллического кремния прямоугольной формы площадью всего несколько квадратных миллиметров, на которой размещены схемы, реализующие все функции процессора. Кристалл-пластинка обычно помещается в пластмассовый или керамический плоский корпус и соединяется золотыми проводками с металлическими штырьками, чтобы его можно было присоединить к системной плате компьютера. В вычислительной системе может быть несколько параллельно работающих процессоров; такие системы называются многопроцессорными. Первый микропроцессор был выпущен в 1971 г фирмой Intel (США) - МП 4004 В настоящее время выпускается несколько сотен различных микропроцессоров, но наиболее популярными и распространенными являются микропроцессоры фирмы Intel и AMD. Структура микропроцессора. Устройство управления является функционально наиболее сложным устройством ПК. Оно вырабатывает управляющие сигналы, поступающие по кодовым шинам инструкций во все блоки машины. Оно содержит: -Регистр команд - запоминающий регистр, в котором хранится код команды: код выполняемой операции и адреса операндов, участвующих в операции.


Беспроводные сети