Ограничение доступа к данным

Тогда

He^T = (h^l,..,h⁶)(e^l,..,e⁶) ^T = e¹h¹ +... + е⁶h⁶.

Если вектор е имеет 1 на i -ом месте, то Не^T = hⁱ т.е. для того, чтобы локализовать единичную ошибку, необходимо и достаточно, чтобы все вектора h_i были различными и ненулевыми. Всего имеется 23 - 1 = 7 различных ненулевых векторов. Следовательно, в данном случае построение проверочной матрицы, обнаруживающей место, на котором случилась единичная ошибка, возможно.

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

Все рассуждения справедливы в случае любого линейного кода [ n, k ]. Для обнаружения единичных ошибок необходимо и достаточно, чтобы 2 r -1 n, где r - число проверочных условий или, что тоже, контрольных разрядов, r=n-k.

Потребуем, чтобы линейные коды, обнаруживающие единичные ошибки, имели максимальную кодовую длины n при фиксированном числе контрольных разрядов r, Из предыдущего неравенства следует n = 2 r -1.

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

Код Хэмминга с блоковой длиной n = 2 r -1 обеспечивает при больших n скорость передачи данных, близкую к максимальной. Эти коды относят к категории высокоскоростных кодов.

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

Шифрация данных. Для ограничения доступа к данным используется их защита с помощью криптографии. Криптография - это преобразование открытого текста к виду, понятному только тому, кто имеет законное право доступа к тексту, с помощью обращения преобразования и восстановления исходного текста.

В криптографии используются два типа преобразований открытого текста: перестановки и подстановки.

Для применения перестановок текст делится на части (блоки) заданной длины, и символы внутри блока переставляются.

При подстановке символы открытого текста заменяют символами из другого или из того же самого алфавитов.

Пусть А и В алфавиты открытого и закрытого текстов, соответственно. Если f() - взаимно однозначное отображение из А в В, то текст a (i₁) a (i₂) ...a (i_n) переходит в текст f(a (i₁) a (i₂) ...a (i_n)). Например, пусть А = { а, b, с }, В = {0,1,2}, а функция f (a) = 0, f (b) = 1, f (c) = 2. Тогда текст abbac будет зашифрован как 01102.

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

Более надёжно использование для шифрации не одной единственной функции, а последовательности функций: f ₁(), f₂ (),…, f_n (). Этот способ шифрации рассмотрен далее.

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

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

Перестановкой называют взаимно однозначное отображение некоторого конечного множества М в себя. Примером такого множества может служить любой конечный алфавит.

Перестановку, соответствующую суперпозиции f (g ()) двух отображений f () и g (), называют произведением соответствующих перестановок. Операция умножения перестановок не обладает свойством коммутативности (перестановочности), т.е. fg gf.

Умножение перестановок ассоциативно, т.е. f (gh) = (fg) h = fgh. Есть единица, роль которой играет перестановка е, любой элемент множества в себя самого, ef=fe=f.

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

Пусть х элемент из множества М, a f - некоторая перестановка. Множество O (x, f) = { х₀ = х, x₁ = f (x₀),..., x_n = f (x_n-1),...}, являющееся подмножеством множества М, назовём орбитой элемента х для перестановки f. Другими словами, орбита образуется при последовательном действии на фиксированный элемент х множества М некоторой перестановки f.

Перестановку можно представить графически, если элементам М сопоставить точки на плоскости и соединить дугой пары точек (x,f (x)). В силу требования взаимно однозначности каждая точка будет иметь ровно одну выходящую и одну входящую дуги. Следовательно, множество М будет представлено как сумма непересекающихся орбит O₁, О₂,...О_m, и каждая орбита может быть порождена любым своим элементом, т.е. O (x,f)= O (y,f), если х и у принадлежат одной и той же орбите.

Перестановка f будет представлена в этом случае, как произведение перестановок f₁, f₂,...,f_m, где перестановка f, есть сужение перестановки f на орбиту О_i. Каждая перестановка f, циклически переставляет элементы орбиты О_i, причём в том же порядке, что и перестановка f, оставляя остальные элементы множества М на месте. Перестановки f_i называют циклическими.

Пример. Пусть перестановка f действует на множестве М ={ е₀, e₁, е₂, е₃, е₄ }, так, что отображает М в множество { е₂, е₄, е₃, е₀, e₁ }. Множество М может быть разложено в сумму двух орбит М = O₁ + О₂, где O₁ = { е₀, е₂, е₃ }, О₁ = { e₀, e₂, e₃ } - орбиты перестановки f. Перестановка f = f₁f₂, где циклическая перестановка f₁ отображает М в { e₂, e₁, е₃, е₀, e₄ }, a f₂ - в { е₀, e₄, e₂, е₃, e₁ }. Отображение f₁ действует на множестве O₁ аналогично f, а элементы множества О₂ оставляет на месте. Циклическая перестановка f₂ оставляет на месте элементы из O₁, а на О₂ действует одинаково с f.

Заметим, что циклические перестановки fi являются коммутативными.

Представление f=f₁f₂…f_m, называется циклическим и напоминает разложение натурального числа в произведение простых чисел.

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

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

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

Циклические перестановка, определяемая орбитой длины 2, называется транспозицией. Транспозиция - простейшая перестановка - меняет местами только два элемента, а остальные оставляет на месте. Транспозиции составляют систему образующих симметрической группы. Это следует из того, что любой цикл можно представить как произведение транспозиций: (е₀, e₁, e₂,…,e_s) = (е₀, e₁)(e₁, e₂)...(e_s, e₀).

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

Если число элементов в множестве М есть простое число, то на М можно ввести структуру конечного поля, т.е. определить обратимые операции сложения и умножения элементов М. Любой фиксированный элемент множества М - е, может порождать перестановки f (x)= х + е и g (x)= x*e, заданные аналитически.

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