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

Имеются следующие разновидности систематических кодов. Кодами Хемминга называются обычно

1) коды с расстоянием d=3, исправляющие все одиночные ошибки,

2) коды с расстоянием d=4, исправляющие все одиночные ошибки и обнаруживающие двойные.

Коды первого вида имеют проверочную матрицу, n=2r1 столбцов которой представляют собою все возможные ненулевые rзначные векторы. Коды второго вида получаются из первого добавлением одного проверочного символы, равного сумме (по модулю 2) всех остальных символов.

Метод декодирования проверки на четность. Число проверок равно числу проверочных символов, т.е. r=nk.

Код Голея, исправляющий все одиночные, двойные и тройные ошибки (d=7).

Код строится на основе матрицы с m строками, столбцы которой представляют со бой все m значные двоичные числа. Остальные кодовые векторы получаются перемножением строк во всех комбинациях по две, по три, ..., по r.

Код МакДоналда, интересный тем, что он имеет наибольшее расстояние, соответствующее пределу Плоткина,

 

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

Проверке подвергаются также и проверочные знаки. Такой код способен исправить все одиночные ошибки. Эта идея может быть обобщена на случаи многомерной таблицы проверок.

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

Коды Галлагера, называемые иначе кодами с малой плотностью проверок на четность, декодируются при помощи проверок на четность, каждая из которых охватывает фиксированное небольшое число v принимаемых символов, а каждый символ участвует также в фиксированном и небольшом числе проверок u (3<u<v). Проверочная матрица кода Галлагера (обозначаемого (n, u, v)) содержит u единиц в каждом столбце и v единиц в каждой строке. Кодовое расстояние для этих кодов растет с увеличением n линейно; иначе говоря, отношение d/n, при n → ∞, стремится к постоянному пределу (тогда как у всех других известных систематических кодов это отношение стремится к нулю).

Процедура декодирования своеобразна. Она выполняется последовательными шагами. После первой проверки исправляется (т.е. заменяется на обратный) символ, входящий в наибольшее число невыполненных проверочных соотношений, после чего проверка производится повторно, пока все проверочные соотношения не будут удовлетворены.

Большую и важную группу систематических кодов составляют циклические коды. Их основное свойство состоит в том, что каждый вектор, получаемый из кодового вектора путем циклической перестановки составляющих, также является кодовым вектором. Принято описывать циклические коды при помощи порождающих полиномов g(x) степени r = n k. Умножение на х соответствует циклической перестановке на один шаг. При этом хr заменяется на единицу. Это записывается так:

g(x) = g0 + g1 x + g2 x2 + ... + gr1 xr1.

xg(x) = gr1 + g0 x + g1 x2 + ... + gr2 xr1.

Запись g(x) = g0 + g1 x + ... + gr1 xr1 соответствует вектору g = (g0, g1, ..., gr1).

В двоичном случае gk могут принимать значение нуль или единица, так, что, например, g(x) = 1 + x2 + x4 + x5 соответствует вектору 101011. В качестве первой строки порождающей матрицы записываются составляющие вектора g(x) с добавлением k нулей; остальные строки получаются из первой вышерассмотренной циклической перестановкой.

Архитектура ОС, файловые системы ОС (24, 25)

Xenix OS (операционная система семейства UNIX) операционная система MS-DOS 1.0 появилась годом позже Основой для создания MS-DOS стала 16-разрядная операционная система SCP-DOS, разработанная Тимом Паттерсоном в компании Seattle Computer Products Первая версия MS-DOS была установлена на IBM PC вместе с Microsoft Basic, Microsoft Cobol, Microsoft Fortran и некоторыми другими программами Microsoft. Всего было выпущено 12 версий MS-DOS: 1.0 (1.1) -2.0-3.0-3.3-4.0 (4.01)-5.0-6.0(6.2, 6.21,6.22). И каждая версия имела свои особенности. Так, MS-DOS 2.0 была ориентирована на обеспечение совместимости с приложениями, разработанными для других операционных систем. В MS-DOS 3.0 основное внимание было уделено сетевым возможностям и работе с дисками больших объемов (больше 1 Гб), в MS-DOS 5.0 была реализована поддержка расширенной памяти (больше 640 кб). MS-DOS 6.0 (и ее подверсии) собрала воедино все, что было сделано, и в то же время стала последней операционной системой семейства MS-DOS. На этой системе в Microsoft закончилась эпоха MS-DOS. Первые идеи о построении операционной системы, отличающейся от привычной текстовой MS-DOS и имеющей новый графический интерфейс, были высказаны Биллом Гейтсом в конце 1982 г. Толчком к этому послужи; целый ряд причин: работа над графическими модулями для Basic, реализация графического интерфейса в компьютерах, выпускаемых компанией Xerox, a также работы, проводимые в институте Карнеги-Меллона. Впервые Microsoft Windows была представлена на выставке Comdex 10 ноября 1983 г., тогда она позиционировалась как графическое расширение для MS-DOS. Даже известные Microsoft Windows 3.x и Microsoft Windows for Workgroups 3.x не являлись операционными системами в чистом виде, а представляли собой надстройки или расширения MS-DOS. Основными новшествами, реализованными в Microsoft Windows, стали появление графического интерфейса пользователя и использование наряду с клавиатурой другого устройства - графического манипулятора "мышь", без которого теперь трудно представить любой современный персональный компьютер.


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