Двоичные данные

Символьные данные

Символьные данные наиболее распространённые. Для них существует несколько методов контроля. Перечислим некоторые из них.

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

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

По допустимым пределам. Некоторые данные принимают значения из ограниченного диапазона. Например, номер месяца не может быть больше 12, возраст сотрудника меняется от 17 до 60 лет и т.д. Если введённое значение вне установленных пределов, то фиксируется ошибка ввода. Этот метод прост в реализации, но малоэффективен; используется, поскольку не требует дополнительных затрат при вводе.

По типу. Данные делятся по типам: целые, вещественные, логические и т.п. Если тип вводимых данных заранее известен, можно проверять вводимые данные на соответствие указанному типу.

По шаблону. Этот метод близок к контролю по типам, только типы здесь определяет пользователь с помощью шаблона. Шаблон - это последовательность символов, где каждый символ определяет некоторый класс символов или только самого себя, т.е. класс, состоящий из единственного символа. Трудность задания в том, что нужно отличать задание класса от задания символа. Эту трудность обходят, вводя дополнительно целочисленный вектор-маску. В маске компонента 0 означает непосредственное задание символа, а 1 означает, что символ на соответствующем месте обозначает не себя, а класс символов. Например, если символом Z обозначать цифры, то шаблон ZZZZZ.ZZ и маска 11111011 будут обозначать целое число с 6 целыми и 2 десятичными разрядами.

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

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

Будем рассматривать в качестве данных двоичные последовательности. Основная идея кодирования проста. Разобьем исходную последовательность на блоки длиной k, символы которых назовем информационными, и припишем к ним r проверочных символов, получив расширенный блок из n = k + r символов, готовый для ввода или передачи. Указанный код называется блоковый и имеет тип [ n, k ].

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

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

Существует 2 ⁿ различных блоков длиной n, но только 2 ^k из них являются кодословами и совокупность их образует код.

В результате передачи данных по каналу связи или другой операции над кодословом может быть получена любая последовательность из n знаков. По полученным n символам необходимо определить, какое из 2 ^k возможных кодослов на самом деле было передано. Это задача декодирования. В результате декодирования можно:

обнаружить и исправить ошибку, если она есть, или правомерно определить её отсутствие;

обнаружить ошибку, но не иметь достаточной информации, чтобы её исправить;

не обнаружить сделанную ошибку или неправильно декодировать принятое слово.

Вероятность появления не обнаруживаемой ошибки одна их количественных характеристик кода. Другая характеристика - скорость передачи данных, которая для блоковых кодов равна k/n.

Перечислим некоторые популярные в практике методы кодирования.

Коды с повторением. Если нам необходимо передать символ 0 или 1, мы передаём его несколько раз подряд (n раз). При декодировании принятые данные разбиваются на блоки длиной n и, если в данном блоке единиц больше, чем нулей, то блок заменяется 1, а, если единиц меньше, то блок заменяется 0. В том случае, если число единиц и нулей в принятом блоке совпадают, декодирование невозможно (отказ от декодирования).

Для кодов с повторением k = 1, а n произвольно. Значение каждого проверочного символа совпадает со значением информационного символа. Если n достаточно велико, вероятность ошибки декодирования мала. Однако трудоёмкость метода слишком велика, она возрастает в n раз.

Коды с проверкой на чётность. Другим примером простых кодов являются коды с проверкой на четность, содержащие только один проверочный символ. Число единиц в кодослове (x₁,...,x_n, x_n+1) всегда четно, поскольку проверочный символ определяется формулой х_n+1 = (x₁ +... + x_n) mod 2.

При использовании этого метода ошибки обнаруживаются, если их чётное число и, в частности, обнаруживаются одиночные ошибки. Трудоёмкость этого метода невелика, и он используется для контроля правильности преобразования данных в компьютере. Обнаруживаемая при использовании этого метода ошибка называется «ошибка чётности».

Конечные поля. Для изложения теории линейных кодов и далее при изучении методов шифрации нам понадобятся элементы теории конечных полей.

Рассмотрим конечное множество М = { e₀,e₁,...,e_m-1 }. Определим на M операции сложения и умножения его элементов, полагая

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

Имеется нулевой элемент, а именно e₀, для которого e₀ + e_i = е₀, и единичный элемент e₁, для которого e₁*e_i = е_i, для любых i =0,..., m - 1.

Для сложения имеется обратная операция - вычитание: е_i - e_j = е_i + (- e_j), где - -e_j элемент обратный к e_j, т.е. такой, что e_j + (-е_j) = е₀. Легко проверить, что обратные элементы можно вычислить по формуле –е₀ = е₀, -е_i = е_m-i при i > 0.

Деление существует не всегда. В частности, деление существует, если порядок m множествам простое число: 2,3,5,7,11 и т.д. В этом случае множество М называется полем характеристики m

Пример. Пусть М = {0,1}. В соответствии с определением

0+0=0; 0+1=1; 1+0=1; 1+1=0;

0*0=0;0*1=0;1*0=0; 1*1 =1.

Кроме того, -0 = 0, -1 = 1. Поэтому при операциях с двоичными данными минус перед константой или переменной можно отбросить.

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

Построим код с блоковой длиной n = 6, имеющий k = 3 информационных символов, т.е. код типа [6,3], определив его уравнениями:

X₁=Z₁;

X₂=Z₂;

Х₃ = Z₃;

Х₄ = Z₁ + Z₂;

X₅ = Z₁ + Z₃;

X₆= Z₂+Z₃,

где Z₁, Z₂, Z₃ - передаваемые разряды, X₁, X₂, Х₃ - информационные разряды, Х₄, Х₅, Х₆ - контрольные разряды. Все операции здесь и далее производятся над двоичными Данными как элементами поля характеристики 2.

Пример. Пусть необходимо передать блок z = (1,1,1). Тогда получим блок для передачи по каналу связи: (1,1,1,0,0,0).

Кодослово (х₁,...,x₆) удовлетворяет проверочным уравнениям

x₁ + x₂ + x₄ = 0;

x₁ + x₃ + x₅ = 0;

x₂ + x₃ + x₆ = 0

или в матричной записи

Hx^T = 0,

где х^T - вектор-столбец;

0 = (0,0,0);

Н - проверочная матрица,

Н =

Любое кодослово, т.е. слово, передаваемое по каналу связи, удовлетворяет этому условию. Следовательно, решая указанную систему линейных уравнений, найдём все кодослова, т.е. построим код. В нашем случае число решений будет равно 2³=8, тогда как общее число слов длины 6 составляет 2⁶=64. Перечислим все 8 кодослов: 000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000. Именно с этими словами совершают операции ввода или пересылки. Если принятое слово не совпадает ни с одним из перечисленных кодослов, то имеет место ошибка.

Введём вектор ошибок (е_i = 1,...,6), где e_i = 1, если при передаче i -гo символа возникла ошибка, в противном случае положим е_i = 0. Обозначим принятое слово (y₁,...,y₆). Тогда у_i = (х_i + e_i), i = 1,...,6.

Вектор-столбец s, определенный уравнением s = Ну^T, называется синдромом.

Поскольку Ну^T = Нx^T + Не^T = Не^T, синдром ошибки е и синдром переданного слова у одинаковы и равны s.

В классе всех решений уравнения Не^T = s, где s синдром полученного слова выбираем вектор е с минимальным число единиц и считаем, что это - вектор ошибок.

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

Допустим, что ошибки единичные, т.е. в векторе е только одна компонента 1, а остальные 0, и обозначим (h₁,...,h₆) столбцы матрицы Н₆.

Дата добавления: 2014-01-13