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

Пример. Рассмотрим процедуру преобразования произвольной порождающей матрицы (5,3)кода к канонической форме:

Первые строки матриц соответствуют канонической форме, вторая строка формируется путем сложения первой и третьей строк, а третья первой и второй строк исходной матрицы.

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

Другой способ матричного описания групповых кодов основан на формировании проверочной матрицы H(n, k), канoническая фoрма которой имеет вид: Н(n, k) = [I(n k) / R’(nk)*k ], гдe I(n k) единичная матрица размерности nk, которая располагается на месте проверочных элементов, а R¢(nk)*k прямоугольная матрица размерности (nk)k, составленная из информационных символов, участвующих в определении проверочных элементов.

Проверочная матрица может быть построена на основе системы проверочных соотношений (1). При этом каждой строке матрицы соответствует одно линейное уравнение. Систему уравнений (1) в данном случае удобнее переписать в следующей форме:

Единичная матрица I(n k) формируется из коэффициентов при элементах

аk,..., аn1, а матрица R из коэффициентов hi, j (i=0...k1; j¢=r...r+k1).

Пример.

Для рассматриваемого выше (5,3)кода проверочная матрица строится на основе системы (2,2) и имеет вид:

Свойство 4.

Скалярное произведение любой кодовой комбинации на транспонированную матрицу проверок НТ(n, k) дает в результате ненулевой вектор размерности (n k).

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

Следует отметить, что ни одна запрещенная комбинация не обладает свойством 4.

Пример. Пусть разрешенная комбинация имеет вид V1 = 11010.

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

Справедлив вывод: некоторая произвольная nэлементная комбинация zi, принадлежит (n, k)коду тогда и только тогда, когда она ортогональна каждой строке матрицы проверок H(n, k).

Результат произведения некоторой комбинации zi, на транспонированную матрицу проверок H(n, k) называется синдромом и обозначается Si = zi * HT(n, k). С учетом введенного понятия принадлежность комбинации коду определяется видом синдрома: zi ÎV ® Si = 0, zi ÏV ®Si ¹0.

Между порождающей и проверочной матрицами группового кода в канонической форме существует взаимно однозначное соответствие, задаваемое следующим свойством.

Свойство 5.

Пусть G(n, k) = [Rk*(n, k)*Ik] и H(n, k) = [I(nk)*R(nk)*k] соответственно порождающая и проверная матрицы (n, k)кода, тогда

R¢(nk)*k = RkT * (nk).

Поскольку любая кодовая комбинация при умножении на транспонированную проверочную матрицу дает (nk)разрядный нулевой синдром, то этот же результат дол жен быть получен при умножении каждой строки порождающей матрицы на НТ(n, k). Следовательно, произведение G(n, k) на НТ (n, k) представляет собой нулевую матрицу размерности k*(nk), т.е. G(n, k)*HТ(n, k) = 0.

Решение этого матричного уравнения и позволяет установить вид проверочной матрицы:

G(n, k*НТ(n, k) = [Ik * Rk*(nk)] * [R¢(nk)*k Ink] =

= Ik * R¢Т(nk)*k + Rk(nk) * IТnk = R¢Т(nk)*k + Кk*(nk) = 0

Отсюда следует, что R¢(nk)*k = RТk*(nk). Вид проверочной матрицы позволяет оценивать корректирующую способность группового кода.

Свойство 6.

Минимальное расстояние Хэмминга dmin(n, k)кода равно минимальному числу линейно зависимых столбцов матрицы проверок. Вычисление dmin пo

H(n, k) осуществляется в следующей последовательности:

 определяется наличие в Н(n, k) двух одинаковых столбцов, при обнаружении которых dmin=2;

 определяется наличие в Н(n, k) трех столбцов, сумма которых равна нулю, и если они имеются, то dmin=3;

 последовательно отыскиваются четыре, пять и т.д. линейно зависимых столбцов, при которых dmin соответственно равно 4, 5 и т.д.

Пример.

В проверочной матрице (5,3)кода Н(5,3) имеются одинаковые столбцы (1 и 3, 2 и 4), а значит dmin = 2, что соответствует результатам вычисления минимального кодового расстояния другими способами.

Сравнение способов задания кодов.

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

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

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

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

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

Похожий подход оказался продуктивным и в области программного подключения устройств ввода-вывода. Подобно тому, как Линнею удалось заложить основы систематики растительного и животного мира, разделив все живое в природе на относительно небольшое число классов и отрядов, мы можем разделить устройства на относительно небольшое число типов, отличающихся по набору операций, которые могут быть ими выполнены, считая все остальные различия несущественными. Мы можем затем специфицировать интерфейсы между ядром операционной системы, осуществляющим некоторую общую политику ввода-вывода, и программными частями, непосредственно управляющими устройствами, для каждого из таких типов. Более того, разработчики операционных систем получают возможность освободиться от написания и тестирования этих специфических программных частей, получивших название драйверов, передав эту деятельность производителям самих внешних устройств. Фактически мы приходим к использованию принципа уровневого или слоеного построения системы управления вводом-выводом для операционной системы (см. рис. 13.1).


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