Основные характеристики корректирующих кодов

Почти все блочные коды относятся к разделимым кодам, кодовые комбинации которых состоят из двух частей: информационной и проверочной. При общем числе n символов в блоке число информационных символов равно k, а число проверочных символов

(3.4)

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

1) Число разрешенных и запрещенных кодовых комбинаций.

Для блочных двоичных кодов с числом символов в блоках, равным n, общее число возможных кодовых комбинаций определяется значением

. (3.5)

Число разрешенных кодовых комбинаций при наличии k информационных разрядов в первичном коде равно

. (3.6)

Число запрещенных комбинаций равно

, (3.7)

а , (3.8)

где r – число избыточных (проверочных) разрядов в блочном коде.

2) Избыточность корректирующего кода.

Избыточностью корректирующего кода называют величину

æ_и, (3.9)

откуда следует:

æ_и, (3.10)

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

Если производительность источника информации равна H' символов в секунду, то скорость передачи после кодирования этой информации окажется равной

, (3.11)

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

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

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

3) Минимальное кодовое расстояние d _min .

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

Кодовым расстоянием между двумя кодовыми комбинациями является количество разрядов (символов), которыми они отличаются. Для определения этого расстояния нужно сложить две кодовые комбинации по mod 2 и подсчитать число единиц в полученной сумме. Кодовое расстояние d(X_i, X₀) между комбинацией X_i и нулевой X₀ = 00..0 называется весом комбинации X_i, т.е. вес X_i равен числу «1» в ней.

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

В безызбыточном коде все комбинации являются разрешенными, и, следовательно, его минимальное кодовое расстояние равно единице (d _min = 1). Поэтому достаточно исказиться одному символу, чтобы вместо переданной комбинации была принята другая разрешенная комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух d _min > 2. Минимальное кодовое расстояние является важнейшей характеристикой помехоустойчивых кодов, указывающей на гарантируемое число обнаруживаемых или исправляемых заданным кодом ошибок.

4) Число обнаруживаемых или исправляемых ошибок.

При применении двоичных кодов учитывают только дискретные искажения, при которых единица переходит в нуль или нуль переходит в единицу. Переход или только в одном элементе кодовой комбинации называется единичной ошибкой (единичным искажением). В общем случае под кратностью ошибки подразумевают число позиций кодовой комбинации, на которых под действием помехи одни символы оказались замененными другими. Возможны двукратные (g = 2) и многократные (g > 2) искажения элементов в кодовой комбинации в пределах.

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

. (3.12)

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

. (3.13)

Чтобы можно было исправить все ошибки кратностью g _и и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию:

. (3.14)

В этом случае любая кодовая комбинация с числом ошибок g _и отличается от каждой разрешенной комбинации не менее чем в g _и + 1 позициях. Если это условие не выполнено, возможен случай, когда ошибки кратности g _и исказят переданную комбинацию так, что она станет ближе к одной из разрешенных комбинаций, чем к переданной или даже перейдет в другую разрешенную комбинацию. В соответствии с этим, условие исправления всех ошибок кратностью не более g _и можно записать в виде:

(3.15)

Для исправления всех ошибок кратности g _и и менее и одновременного обнаружения всех ошибок кратности g _о (g _о g _и) и менее минимальное хэммингово расстояние нужно выбирать из условия

. (3.16)

Из (3.14) и (3.16) следует, что если код исправляет все ошибки кратностью g _и, то число ошибок, которые он может обнаружить, равно g _о = 2 g _и. Следует отметить, что соотношения (3.14) и (3.16) устанавливают лишь гарантированное минимальное число обнаруживаемых или исправляемых ошибок при заданном d _min и не ограничивает возможностей обнаружения ошибок большей кратности. Например, простейший код с проверкой на чётность с d _min = 2 позволяет обнаруживать не только одиночные ошибки, но и любое нечетное число ошибок в пределах g _о < n.

5) Корректирующие возможности кодов.

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

Граница Плоткина даёт верхнюю границу кодового расстояния d _min при заданном числе разрядов n в кодовой комбинации и числе информационных разрядов k для двоичных кодов:

, (3.17)

или

, при. (3.18)

Верхняя граница Хемминга устанавливает максимально возможное число разрешенных кодовых комбинаций (2 ^k) любого помехоустойчивого кода при заданных значениях n и d _min:

, (3.19)

где – число сочетаний из n элементов по i элементам.

Отсюда можно получить выражение для оценки числа проверочных символов:

. (3.20)

Для значений разница между границей Хемминга и границей Плоткина сравнительно невелика.

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

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

. (3.21)

На рис. 3.4 представлены кривые, соответствующие верхней границе Плоткина и нижней границе Варшамова-Гильберта, как функции скорости от аргумента. В отличие от границы Плоткина граница Варшамова – Гильберта означает, что всегда существуют коды, имеющие скорость, лежащую на соответствующей кривой, а возможно и выше этой кривой. Параметры наилучших реализуемых кодов могут лежать только в заштрихованной области между верхней и нижней границами.

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

для d _min = 3; для d _min = 4.

Рис. 3.4. Границы Плоткина и Варшамова-Гильберта

Блочные коды с d _min = 3 и 4 в литературе обычно называют кодами Хемминга.

Все приведенные выше оценки дают представление о верхней границе числа d _min при фиксированных значениях n и k или оценку снизу числа проверочных символов r при заданных k и d _min.

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

3.3. Блочные линейные коды

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

3.3.1. Систематические коды

Примерами систематических кодов являются коды Хемминга и циклические. Последние реализуются наиболее просто, что и привело к их широкому использованию. Для систематического кода применяетсяобозначение (n, k) – код, где n – число элементов в комбинации; k – число информационных элементов.

Код Хемминга. Рассмотрим в качестве примера построениесис­тематического кода с кодовым расстоянием и числом передаваемых сообщений N ₀ = 16. В этом случае число информационных элементовОдним из возможных способов задания исходного (просто­го) кода является табличный, представляющий все 16 кодовых комбинаций, включая нулевую (0000). Другой способ заключается в выписывании только четырех кодовых комбинаций простого кода в виде матрицы, называемой еди­ничной I_k размером k x k:

I_k =. (3.22)

Суммируя по модулю два в различном сочетании кодовыекомби­нации, входящие в единичную матрицу, можно получить 15 кодовых комбинаций, 16-я – нулевая. Кодовые комбинации, составляющие единичную матрицу (3.22), линейно независимы. Ненулевые комбинации а ₁, а ₂, а ₃, а _4, линейно неза­висимые, если, где, при усло­вии, что хотя бы один из коэффициентов. Дополним каждую ко­довую комбинацию в (3.22) проверочными элементами так, чтобы обеспечивалось. При этом необходимо учитывать, что к чис­лу разрешённых комбинаций корректирующего кода принадлежит и комбинация 00... 0, называемая нулевой. Тогда матрица примет вид:

G_(7,4) = = ||I_k С_{( r,k )}||. (3.23)

Добавляемые проверочные элементы могут быть записаны и в дру­гом порядке. Необходимо лишь обеспечить.

Матрицу (3.23)называют производящей, или порождающей, мат­рицей кода (7, 4),содержащего семь элементов, из которых четыре информационных. Обычно матрицу обозначают буквой G с индексом, указывающим, к какому коду она относится (в нашем случае G_(7,4)). Производящая матрица состоит из двух матриц – единичной I_k размер­ности k x k и С_{( r,k )}, содержащей r столбцов и k строк. Суммируя в различном сочетании строки порождающей матрицы (3.23), получаем все (кроме ну­левой) комбинации корректирующего кода с.

Обозначим элементы комбинации полученного семиэлементного кода a ₁, а ₂, а ₃, а ₄, r ₁, r ₂, r ₃, из которых a ₁, а ₂, а ₃, а ₄ – информационные и r ₁, r ₂, r ₃ – проверочные. Последние могут быть получены путем суммирования по модулю два определенных информационных элемен­тов. Правило формирования проверочного элемента r _i для любой кодовой комбинации одинаково.

Пользуясь порождающей матри­цей (3.23), найдем значения элемента r _i (в суммировании участвуют только элементы, имеющие в i -ом столбце порождающей матрицы «1»):

;

;

.

Алгоритм формирования проверочных элементов r ₁, r ₂, r ₃ может быть задан матрицей, называемой проверочной. Эта матрица содержит r строк и n столбцов. Применительно к сформированному нами коду (7,4) она имеет вид:

H_(7,4) =.

Единицы, расположенные на местах, соответствующих информа­ционным элементам матрицы Н_(7,4) указывают на то, какие инфор­мационные элементы должны участвовать в формировании прове­рочного элемента. Единица на месте, соответствующем проверочно­му элементу, указывает, какой проверочный элемент получается при суммировании по модулю два информационных элементов. Из первой строки следует равенство для r ₁, из второй – для r ₂ и т.д.

Процедура обнаружения ошибок основана на использовании про­верок r ₁, r ₂, r ₃. Очевидно, что проверочные элементы, сформи­рованные из принятых информационных, при отсутствии ошибок должны совпадать с принятыми проверочными.

Пример 1. Переданная кодовая комбинация имеет вид 1000111 (первая строка порождающей матрицы (3.23)). В результате действия помех на приём­ном конце имеем а' ₁, а' ₂, а' ₃, а' ₄, r' ₁, r' ₂, r' ₃ = 1100111. Произведем про­верки r ₁, r ₂, r ₃:

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

Комбинация называется синдромом (проверочным векто­ром). При числе проверочных символов r = 3 имеется восемь возможных синдромов (2³ = 8). Нулевой синдром (000) указывает на то, что ошибки при приёме отсутствуют или не обнаружены или кодовая комбинация принята с ошибками, которые превратили её в другую разрешённую. Последние события имеет существенно меньшую вероятность, чем первое. Всякому ненулевому синдрому соответствует определённая конфигурация ошибок, которая и исправляется. Вид ненулевого синдрома определяется характером ошибок в ко­довой комбинации. В рассматриваемом случае вид синдрома зависит от место­положения одиночной ошибки. В табл. 3.6 отражено соответствие между местоположением одиночной ошибки для кода, заданного порождающей мат­рицей G_(7,4) (3.23) и видом синдрома.

Таблица 3.6

Ненулевые синдромы и соответствующие конфигурации ошибок кода (7,4)

№ элемента, в котором произошла ошибка
Вид синдрома

Таким образом, зная вид синдрома, можно определить позицию, в которой произошла ошибка, и исправить принятый элемент на противоположный.

Пример 2. Передавалась кодовая комбинация 1000111. При­нята кодовая комбинация 0000111. Синдром S имеет вид 111. В соот­ветствии с табл. 3.6 исказился первый элемент (а ₁). Изменим первый элемент на противоположный

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

Рассмотренный код (7,4) гарантированно обнаруживает двукрат­ные ошибки, а исправляет только однократные ошибки.

Структурная схема системы передачи с кодом (7,4) представлена на рис. 3.5.

Рис. 3.5. Структурная схема системы передачи с кодом (7,4)

Циклические коды. В теории циклических кодов кодовые комби­нации обычно представляются в виде полинома. Так, n -элементная кодовая комбинация записывается в виде:

где а_i = {0,1}, причем а _i = 0 соответствуют нулевым элементам ком­бинации, а а _i = 1 – ненулевым.

Например, комбинациям 1101 и 1010 соответствуют многочлены и

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

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

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

– циклический сдвиг раз­решенной комбинации тоже приводит к разрешенной кодовой комби­нации;

– все разрешенные кодовые комбинации делятся без остатка на полином Р (х), называемый образующим.

Эти свойства используются при построении кодов, кодирующих и декодирующих устройств, а так­же при обнаружении и исправлении ошибок.

Найдем алгоритмы построения циклического кода, удовлетворяю­щего перечисленным выше условиям. Задан полином определяющий корректирующую способность кода, и задан исходный простой код, который требуется преобразовать в корректирующий циклический. Обозначим многочлен, соответствующий комбинации простого ко­да, Q (x). Возьмём произведение Q (x) х^r и разделим его на Р (х). В ре­зультате получим многочлен G (x) и остаток R (х)/ Р (х):

(3.24)

Умножим левую и правую части на Р (х) и перепишем (3.24) в виде

(3.25)

Перепишем равенство (3.25) в виде

(3.26)

Левая часть этого равенства (3.26) делится без остатка на, следовательно и правая часть делится без остат­ка. Из (3.26) вытекают два способа форми­рования комбинаций циклического кода:

1) путём умножения многочлена на;

2) путём деления на и приписывания к остатка от деления R (x).

Пример 3. Задан полином, соответствующий комбинации простого кода. Требуется сформировать комбинацию цикличе­ского кода (7,4) с производящим полиномом. Комбинацию циклического кода можно получить в виде: Однако в полученной комби­нации нельзя отделить информационные элементы от проверочных, и код получается неразделимым.

Проделаем необходимые операции по получению ком­бинации циклического кода по второму способу, который чаще всего применяется на практике:

1);

2) х ⁶ + х ⁴ х ³ + х ² + 1

х ⁶ + х ⁵ + х ³ х ³ + х ² + 1

х ⁵ + х ⁴ + х ³

х ⁵ + х ⁴ + х ²

х ³ + х ²

х ³ + х ² + 1

R (x) = 1

3) – комбинация циклического кода, полученная методом деления на производящий полином. Она может быть перепи­сана в виде 1010001. Первые четыре элемента – информационные, последние три – проверочные, т.е. полученный код – разделимый.

Для обнаружения ошибок в принятой кодовойкомбинации доста­точно поделить её на производящий полином.Еслипринятая комби­нация разрешённая, то остаток от деления будет нулевым. Ненуле­вой остаток свидетельствует о том, чтопринятая комбинация содер­жит ошибки.По виду остатка (синдрома)можно внекоторых случаях также сделать вывод о характере ошибки и исправить её.

Циклические коды достаточно просты в реализации, обладают вы­сокой корректирующей способностью (способностью исправлять и обнаруживать ошибки) и поэтомурекомендованы МСЭ-Т дляприме­нения в аппаратуре ПД.Согласнорекомендации V.41 в системах ПД с ОС рекомендуется применять код с производящим полиномом

3.3.2. Подклассы линейных двоичных кодов

Коды с общей проверкой на чётность. Это класс кодов с параметрами (п, k) = (k + 1, k), k = 1, 2, ..., когда имеется лишь один проверочный символ, ко­торый образу­ется как сумма по mod 2 всех информационных символов. Оче­видно, что минимальное расстояние для данных кодов всегда равно 2 и поэтому они могут гарантированно обнаруживать лишь одну ошибку. Комбина­ции данного кода имеют лишь чётные веса.

Коды Хэмминга. Данный класс кодов имеет параметры (п, k) = ( 2 ^s – 1, 2 ^s –1– s), s – целое. Код определяется проверочной матрицей Н, ко­торая должна содержать все 2 ^s – 1 ненулевых двоичных векторов. Дан­ный класс кодов имеет при любых s минимальное кодовое рас­стояние, равное 3. Это пример совершенного кода, исправляющего все однократные ошибки и ничего более. Коды Хэмминга могут гарантированно обнаруживать ошибки кратности 1 и 2.

М-последовательности. Это класс кодов с параметрами (n, k) = (2 ^s – 1, s), s – целое, ко­торые определяются как дуальные к кодам Хэмминга той же самой длины. Данный класс кодов может быть определён также иначе, как совокуп­ность выходных последовательностей при различных начальных заполнениях линейного регистра длины s со связями, выбранными так, чтобы период вы­ходной последователь­ности оказался равным 2 ^s – 1. Поэтому они получили на­звание после­до­вательностей максимальной длины или М-последовательно­стей. Все комбинации данного кода, кроме нулевой, имеют одина­ковый вес 2 ^s – 1 и, следовательно, для такого кода d = 2 ^s – 1. Коды Хэмминга и М- последовательности являются крайними слу­чаями кодов с малой и большой величиной минимального кодо­вого расстояния. Они не всегда удобны для практического исполь­зования, поскольку исправление только однократных ошибок обычно оказывается недостаточным для обеспечения высокой верно­сти передачи, а высокая исправляющая способность М -по­следовательно­стей покупается за счёт их весьма низкой кодовой скорости R. Поэтому необходимо иметь класс кодов с промежу­точными значениями скорости R. Это может быть достиг­нуто при переходе к определённым подклассам циклических кодов.

Полиномиальные коды. Циклические коды. Коды Боуза-Чоудхури-Хоквингема (БЧХ). Кодовые слова двоичного линейного кода могут быть пред­ставлены в виде полиномов x(D) = x ₀ + + x ₁ D + x ₂ D ² +...+ x_{n- 1} D ^{n- 1} степени п – 1 от не­которой формальной переменной D, двоичные коэффициенты х за­дают символы кодового слова. Полиномиальный код определяется как множест­во полиномов (кодовых слов) степени п – 1, получаемых умножением инфор­мационного полинома b (D) степени k – 1 на порождающий полином кода g (D) степени п – k

x (D) = b (D) g (D). (3.27)

Это уравнение (3.27) задаёт процедуру кодирования полиномиального кода: со­общение дискретного источника кодируется примитивным кодом длины k, символы примитивного кода становятся коэффициентами информационного полинома b (D) = b ₀ + + b ₁ D +...+ b_{k- 1} D ^{k- 1}; последний умножается на порождающий полином кода g(D) = g ₀ + g ₁ D +...+ g _n-kD ^n-k и после приведения подобных членов определяются п коэффициентов полинома x (D), являющихся символами кодо­вого слова.

Из уравнения (3.27 видно, что любой из полиномов x (D), соответствую­щий кодовым словам полиномиального кода, должен делиться без остатка на порождающий полином g (D). Остаток от деления полинома y (D), соответст­вующего принятой из канала комбинации, на порождающий полином кода g (D) называется синдромным полиномом s (D). Если синдромный полином равен нулю (т.е. деление произошло без остатка), то принятая комбинация является кодовым словом. В противном случае принятая комбинация не является кодо­вым словом. Таким образом, для полиномиальных кодов процедура обнаруже­ния ошибок (вычисление синдрома) состоит в делении принятой комбинации на порождающий многочлен.

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

Циклические коды значительно упрощают описание линейного кода, по­скольку для них вместо задания k (n – k) элементов двоичной порождающей матрицы G требуется задать (n – k + 1) двоичных коэффициентов многочлена g (D). Кроме того, они упрощают процедуру кодирования и декоди­рования для обнаружения ошибок. Для обнаружения ошибок достаточно разделить многочлен, соответствующий принятому слову y (D), на порождающий многочлен g (D) и проверить, будет ли остаток от деления равен нулю. Эта процедура осуществляется на линейных сдвиговых регистрах с обратными связями. Более важное преимущество циклических кодов состоит в том, что они могут быть сконструированы как коды с некоторым га­рантированным значением минимального кодового расстояния. Для этого не­обходимо определённым образом выбрать порождающий многочлен кода g (D). Циклические коды, которые имеют порождающий многочлен, заданный свои­ми определёнными корнями, называются кодами Боуза-Чоудхури-Хоквингема (кратко БЧХ-кодами).

Коды БЧХ, являющиеся результатом обобщения кодов Хэмминга, позволяют исправлять множественные ошибки. Они составляют мощный класс циклических кодов, обеспечивающий свободу выбора длины блока, степени кодирования, размеров алфавита и возможностей коррекции ошибок. При длине блоков порядка нескольких сотен символов коды БЧХ превосходят своими качествами все другие блочные коды с той же длиной блока и степенью кодирования. В наиболее часто применяемых кодах БЧХ используется двоичный алфавит и блок кодового слова длиной где m = 3, 4, …

Коды Рида – Соломона (Р – С) – это недвоичные циклические коды, символы которых представляют собой m – битовые последовательности, где m > 1 – положительное целое число. Рида – Соломона коды (n, k) являются подмножеством кодов БЧХ, определённых на m – битовых символах при всех n и k, для которых

где k – число информационных бит, подлежащих кодированию, а n – число кодовых символов в кодируемом блоке.

Для большинства свёрточных Р – С кодов (n, k):

где g – количество ошибочных бит в символе, которые может исправить код, а – число контрольных символов.

Коды Рида – Соломона обладают наибольшим минимальным кодовым расстоянием, возможным для линейного кода с одинаковой длиной входных и выходных блоков кодера:

.

Замечательное свойство Р – С кодов заключается в том, что они могут исправлять любой набор искажённых символов в блоке. Наибольшей привлекательностью обладают Р – С коды с низкой избыточностью. Коды Рида – Соломона очень эффективны при исправлении пакетов ошибок, т.е. в каналах связи с памятью.

3.4. Свёрточные коды

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

3.4.1. Структура и основные характеристики

Свёрточный код образуется в результате прохождения передаваемой информационной последовательности через линейный сдвиговый регистр с конечным числом состояний. В общем случае, регистр сдвига состоит из К k – разрядных ячеек (рис. 3.6). Рис. 3.6. Структурная схема свёрточного кодера Входные информационные символы продвигаются вдоль регистра по k бит за такт. Число выходных бит, соответствующих каждой k – битовой входной информационной последовательности и передаваемых в канал связи за один такт, равно n. Следовательно, относительная кодовая скорость Эти биты формируются с помощью n сумматоров по модулю 2 (функциональных генераторов), на входы которых подаются информационные символы с выходов определённым образом выбранных ячеек регистра сдвига. Коммутатор осуществляет последовательное считывание поступающих на его входы (контакты) символов и устанавливает на выходе очередность посылки кодовых символов в канал связи. Тактовая частота переключения и число контактов коммутатора в сверточных кодерах определяется относительной скоростью кода Параметр К называется кодовым ограничением.

Рассмотрим наиболее часто используемые двоичные свёрточные коды с k = 1. Для кодера с k = 1 информационные биты за один такт смещаются в регистре сдвига на один разряд. Степень кодиро вания в этом случае (относительная кодовая скорость) равна 1 /n. В качестве примера рассмотрим свёрточный кодер, структурная схема которого представлена на рис. 3.7.

Рис. 3.7. Структурная схема свёрточного кодека

(кодовое ограничение K = 3, k =1)

В данном кодере имеется трёхразрядный регистр (кодовое ограничение K =3), n = 2 сумматора по модулю 2 (mod 2), относительная скорость кодирования На каждом такте очередной информационный бит поступает в первую ячейку регистра (левую), а все предшествующие ему биты – смещаются на одну позицию в право. Затем коммутатор считывает выходы всех сумматоров по mod 2 (сначала верхний, затем нижний), в результате чего формируется пара кодовых символов, образующих кодовое слово, связанное с очередным поступившим символом. Выбор связи между сумматорами и разрядами регистра сдвига определяет характеристику кода. Всякое изменение связей приводит в результате к различным кодам. Задача выбора связей, оптимизирующих кодовое расстояние, сложна и в общем случае не решается. В связи с этим для всех значений кодового ограничения К ≤ 20 расчётным путём были найдены хорошие коды.

Один из методов описания свёрточного кода сводится к заданию его порождающей матрицы по аналогии с блочными кодами. В общем случае порождающая матрица свёрточного кода полубесконечная, поскольку входная последовательность полубесконечная. Можно использовать эквивалентное представление кода, в котором для каждого из n сумматоров по mod 2 определяется вектор размерности К, содержащий в себе информацию о соединениях регистра сдвига кодера с сумматорами по mod 2. «1» в i – ой позиции вектора указывает на наличие связи соответствующей ячейки (разряда) регистра с сумматором по mod 2, а «0» – на её отсутствие. Для кодера, изображённого на рис. 3.7, можно записать вектор связи для верхнего сумматора по mod 2, и – для нижнего:

Считаем, что все ячейки регистра в исходном состоянии находятся в нулевом состоянии, а вектор сообщения. Последовательность кодирования представлена на рис. 3.8.

В моменты времени и для очистки регистра в него вводятся (К – 1) = 2 нуля, что в результате приводит смещению конечного участка на всю длину регистра, т.е. его обнуления. Последовательность на выходе кодера выглядит следующим образом

11 10 00 10 11,

где крайний левый символ соответствует первому переданному символу.

Рис. 3.8. Последовательность свёрточного кодирования

В момент времени на выходе появляется нулевая комбинация, т.е. после пятого такта () регистр возвращается в исходное состояние.

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

а) Полиномиальное представление.

Свёрточный кодер можно представить в виде набора n полиномиальных генераторов, по одному для каждого из n сумматоров по mod 2. Каждый полином имеет порядок К – 1 или меньше и описывает связь кодирующего регистра с соответствующим сумматором по mod 2, почти также как и вектор связи. Коэффициенты перед каждым из слагаемых полинома порядка (К – 1) равны либо 1, либо 0 в зависимости от наличия связи между регистьром сдвига и сумматором по mod 2. Для рассмотренного выше кодера:

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

U(X) = (1,1) (1,0) X (0,0) X ² (1,0) X ³ (1,1) X ⁴ U = 11 10 00 10 11

б) Диаграмма состояний.

Свёрточный кодер относится к классу конечных автоматов (система с ограниченным числом состояний, обладающая памятью). Для свёрточного кода со степенью кодирования 1/ n состояние представлено содержимым К – 1 правых крайних разрядов регистра сдвига. Знание состояния и кодируемых данных является необходимым и достаточным условием для определения выходных данных кодера. На рис. 3.9 представлена диаграмма состояний кодера, представленного на рис. 3.7.

Рис. 3.9. Диаграмма состояний кодера (степень кодирования 1/2, К = 3)

Состояния регистра выбраны следующими: а = 00, b = 10, с = 01 и d = 11. Диаграмма показывает все возможные смены состояний кодера. Существует всего два исходящих из каждого состояния перехода, соответствующих двум возможным входным битам. Для каждого пути между состояниями указано кодовое слово на выходе кодера, связанное с переходами между состояниями. За один такт невозможен переход из одного состояния в любое произвольное.

в) Древовидные диаграммы.

Диаграмма состояний не отображает динамику изменений. Это позволяет сделать древовидная диаграмма. Древовидная диаграмма свёрточного кода представлена на рис. 3.10. Процедура кодирования описывается перемещением по диаграмме слева направо, каждой ветви дерева соответствует кодовое слово на выходе кодера. Правило ветвления для нахождения последовательности кодовых слов следующее: поступающему на вход символу «0» соответствует кодовое слово, определяемое путём перемещения в следующую правую ветвь по направлению вверх; символу «1» – путём перемещения в следующую правую ветвь по направлению вниз. Предполагается, что в исходном состоянии кодер содержит одни нули. Следуя этой процедуре, входной последовательности 11011, представленной на рис. 3.10 жирной линией, соответствует последовательность кодовых слов 11 01 01 00 01.

г) Решётчатая диаграмма

Исследование древовидной диаграммы на рис. 3.10 показывает, что в этом приме­ре после третьего ветвления в момент времени t ₄ структура повторяется (в общем случае древовидная структура повторяется после К ответвлений, где К — длина ко­дового ограничения). Пометим каждый узел в дереве (рис. 3.10), ставя в соответствие четыре возможных состояния в регистре сдвига: а = 00, b = 10, с = 01 и d = 11. Пер­вое ветвление древовидной структуры в момент времени t ₁ дает пару узлов а и b. При каждом последующем ветвлении количество узлов удваивает­ся. Второе ветвление в момент времени t ₂ дает в результате четыре узла а, b, с и d. После третьего ветвления всего имеется восемь узлов: два – а, два – b, два – с и два – d. Таким образом, все ветви выходят из двух узлов одного и того же состояния, образуя идентичные ветви последовательностей кодовых слов. В этот момент дерево делится на идентичные верхнюю и нижнюю части (когда четвертый входной бит входит в кодер слева, первый входной бит справа выбрасывается и больше не влияет на кодовые слова на выходе. Следовательно, входные последовательности 110ху... и 000ху..., где крайний левый бит является самым ранним, после (К = 3) - го ветвления генерируют одинаковые кодовые слова ветвей. Это означает, что любые состояния, имеющие одина­ковую метку в один и тот же момент t _i, можно соединить, поскольку все последующие пути будут неразличимы.

Рис. 3.10. Древовидное представление кодера

Проделав это для древовидной структуры, показан­ной на рис. 3.10, получим диаграмму, называемую решетчатой. Решетчатая диа­грамма, использующая повторяющуюся структуру, дает более удобное описание ко­дера, по сравнению с древовидной диаграммой. Решетчатая диаграмма для свёрточного кодера, изображенного на рис. 3.7, показана на рис. 3.11. Узлы решетки представляют состояния кодера; первый ряд узлов соответствует состоянию а = 00, второй и последующие – состояниям b = 10, с = 01 и d = 11. В каждый момент времени для представления 2 ^{К- 1} возможных со­стояний кодера требуется 2 ^{К- 1} узлов решётки. В рассматриваемом примере после достижения глуби­ны решетки, равной трем (в момент времени t ₄), решетка имеет фиксиро­ванную периодическую структуру. В общем случае фиксированная структура реализует­ся после достижения глубины К. Следовательно, с этого момента в каждое состояние можно войти из любого из двух предыдущих состояний. Также из каждого состояния можно перейти в одно из двух состояний. Из двух исходящих ветвей одна соответствует нулевому входному биту, а другая – единичному входному биту. На рис. 3.10 кодовые слова на выходе соответствуют переходам между состояниями, показанными как метки на ветвях решетки.

Рис. 3.11. Решётчатая диаграмма кодера

Один столбец временного интервала сформировавшейся решётчатой структуры ко­дирования полностью определяет код.

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

1. Они не требуют синхронизации по блокам, а лишь синхронизации коммута­торов на передаче и приёме.

2. Если кодовое ограничение К выбрать равным длине блокового кода, то ис­правляющая способность свёрточного кода оказывается больше, чем исправляющая способность такого блокового кода (при наилучшем выборе обоих кодов).

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

4. Свёрточные коды допускают простое объединение кодирования и модуляции (так называемая кодированная модуляция или сигналъно-кодовые конструкции СКК), что особенно важно при построении энергетически эффективных систем связи для каналов с ограниченной полосой частот.

3.4.2. Декодирование

Оптимальный свёрточный декодер, минимизирующий вероятность ошибки, реализуется на основе принципа максимального правдоподобия. При декодировании бит данных, закодированных свёрточным кодом, применение этого принципа заключается в выборе наиболее вероятной последовательности на основе сравнения функций правдоподобия. В качестве переданной последовательности декодер выбирает одну из возможных последовательностей, если правдоподобие является наибольшим из всех возможных (здесь Z – принятая последовательность). Функция правдоподобия задаётся или вычисляется исходя из характеристик канала. Для канала без памяти с аддитивным белым гауссовским шумом и степени кодирования свёрточного кода 1/ n правдоподобие можно представить в виде

где – i -я ветвь принятой последовательности Z, – ветвь отдельной последовательности кодовых слов, – j -й кодовый символ, – j -й кодовый символ, а каждая ветвь состоит из n кодовых символов. Задача декодирования заключается в выборе пути сквозь решётчатую диаграмму кодера (каждый возможный путь определяет последовательность кодовых слов) таким образом, чтобы было максимальным.

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

Существует несколько алгоритмов, дающих приблизительное решение задачи декодирования на основе критерия максимального правдоподобия. Оптимальным алгоритмом является алгоритм Витерби. Преимущество декодера Витерби заключается в том, что его сложность не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычисление меры подобия (или расстояния) между сигналом, принятым в момент времени, и всеми путями решётки, входящими в каждое состояние в этот момент времени. В алгоритме Витерби не рассматриваются те пути решётки, которые в соответствии с принципом максимального правдоподобия заведомо не могут быть оптимальными. Из всех путей, входящих в одно и то же состояние, выбирается путь с лучшей метрикой. Такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Декодер углубляется в решётку, принимая решение путём исключения менее вероятных путей. В отличие от решётки кодера в решётке декодера каждая ветвь за каждый временной интервал отмечают расстоянием Хэмминга между полученным кодовым символом и кодовым символом, соответствующим той же ветви из решётки кодера (рис. 3.11).

Рис. 3.12. Решётчатая диаграмма декодера (степень кодирования 1/2, К = 3)

На рис. 3.12 показана последовательность сообщений m = 11011, соответствующая её кодовая последовательность = 11 01 01 00 01 и искажённая последовательность Z = 11 01 01 10 01. Из решётки кодера следует, что переход между состояниями 00 → 00 порождает на выходе ветви слово 00. Однако получено 11. Следовательно, на решётке декодера переход 00 → 00 пометим расстоянием d = 2. Далее, по решётке кодера переходу 00 → 10 соответствует кодовое слово 11, точно соответствующее полученному в момент времени. Таким же образом отмечаются ветви решётки декодера по мере получения символов в каждый момент времени. Следовательно, переходу 00 → 10 по решётке декодера соответствует кодовое расстояние d = 0. Таким образом, метрика входящих в решётку декодера ветвей описывает разницу (расстояние) между реально полученным и тем, что должно было поступить. В алгоритме декодирования Витерби расстояния Хэмминга используются для нахождения наиболее вероятного (с минимальным расстоянием) пути через решётку.

В каждый момент времени в решётке существует состояний, в каждое из которых может войти два пути. Декодирование Витерби состоит в вычислении метрики двух входящих в каждое состояние путей, и исключение наименее вероятного из них. Такие вычисления проводятся для каждого из состояний или узлов в момент времени; затем декодер переходит к моменту времени, и процесс повторяется. Первые несколько шагов декодирования приведены на рис. 3.13. В моменты времени, и из каждого состояния выходят по две ветви (рис. 3.13, а – в). В момент времени (рис. 3.13, в) в каждое состояние входят два пути. Выжившие на этот момент пути показаны на рис. 3.13, г. В этой точке процесс декодирования имеет только один выживший путь, который называется полной ветвью. Следовательно, декодер может решить, что между моментами времени и произошёл переход 00 → 10. Поскольку переход вызывается единичным входным символом, на выходе декодера первым символом будет единица. Первый символ (бит) не декодируется, пока вычисление метрики пути не пройдет далее вглубь решётки.

До момента нельзя принять решение относительно второго переданного символа, поскольку остаются ещё два пути, исходящих в момент времени из состояния в узле 10. В момент единственным оставшимся путём между точками и (рис. 3.13, ж, з), следовательно, декодер принимает решение, что вторым декодированным символом является «1». Аналогичным образом декодер продолжает углубляться в решётку и принимать решения относительно информационных бит, устраняя все пути, кроме одного.

Рис. 3.13. Выбор выживших путей:

а) выжившие пути на момент времени; б) выжившие на момент времени; в) сравнение метрик в момент времени; г) выжившие на момент; д) сравнение метрик в момент; е) выжившие на момент; ж) сравнение метрик в момент; з) выжившие на момент; Г _а, Г _b, Г _с, Г _d – суммарная метрика путей.

3.5. Теоретико-информационные основы криптозащиты сообщений в телекоммуникационных системах

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

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

В криптоанализе предметом изучения и разработки являются прямо противоположные задачи, а именно: методы, приёмы и способы «взлома» шифрсистем.

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

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

3.5.1. Модель и основные понятия секретной связи

На рис. 3.14 представлена модель секретной связи, предложенная Шенноном. В этой модели имеются:

– источник сообщений, создающий непрерывный или дискретный случайный процесс X (t) = { x (t)};

– источник ключей, создающий дополнительную информацию y _j, называемую ключом и необходимую для работы шифратора. Ключ Ψ _j представляет собой реализацию псевдослучайного процесса со значениями во множестве Y = {Ψ₁ , Ψ₂ , …, Ψ _N };

– шифратор, преобразующий сообщение в криптограмму в соответствии с ключом, выбранным источником ключей; криптограмма – это случайный процесс Y (t) = { y (t)}, однозначно связанный с процессом X и ключом Ψ _j;

– открытый канал для передачи криптограммы Y,

– закрытый канал для передачи ключа Ψ _j.

Источник сообщений

Шифратор

Открытый канал

Дешифратор

Адресат

Источник ключей

Закрытый канал

Y

X (t)

Y (t)

[Y ^-1]

утечка

помехи

Рис. 3.14. Модель секретной связи

На приемной стороне имеется дешифратор, преобразующий криптограмму Y, полученную из открытого канала, в соответствии с ключом Ψ _j, полученным по закрытому каналу, в сообщение X, предназначенное для адресата (иногда его называют конфидентом, т.е. законным получателем криптограммы).

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

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

Модель рис. 3.14 неявно предполагает, что передача криптограммы и ключа осуществляется одновременно. В действительности передача в открытом и закрытом каналах разнесены во времени: ключ всегда передаётся заблаговременно. Как следствие, требования к тактико-техническим, информационным и потребительским характеристикам этих двух каналов (например, оперативность связи, скорость передачи и т.п.) могут быть настолько различны, что вопрос об их взаимозаменяемости становится некорректным.

3.5.2. Оператор шифрования: общие свойства и общие требования

Любой конструктивный способ преобразования сообщения X в криптограмму Y называется оператором шифрования F:

F: X®Y=F (X, Y),

где Y – процесс, создаваемый источником ключей.

Оператором дешифрования F ^-1 называется обратное преобразование:

F ^-1: Y®X=F ^-1(Y, Y ^-1),

где Ψ ^-1 – процесс, обратный процессу Y, создаваемому источником ключей.

Пара [ F, F ^-1] называется алгоритмом криптопреобразования (или просто криптоалгоритмом), а ее компоненты прямым криптопреобразованием (или прямым криптоалгоритмом F) и обратным криптопреобразованием (или обратным криптоалгоритмом F ^-1).

Криптоалгоритм [ F, F ^-1 ] обладает общими свойствами:

– обратимостью: F ^-1 F=I (тождественный оператор); при этом предполагается, что ключи Ψ^-1 и Ψ во вполне определенном смысле согласованы. Это свойство можно записать в следующем виде F^{- 1} [ F (X, Ψ), Ψ^-1 ] = X;

– параметричностью (многовариантностью): оператор F должен допускать представление в виде множества его реализаций, отличающихся параметром (ключом Ψ _j, j = 1,2, …, N). Число N называется мощностью множества ключей.

Обычно под ключом понимают сами индексы j («номера») реализаций оператора F, образующих конечное множество, которые всегда можно упорядочить желаемым образом.

Сказанное в полной мере относится и к обратному оператору криптопреобразования F ^-1.

К криптоалгоритму [ F, F ^-1] предъявляются общие требования:

– для дискретных сообщений оператор F не должен расширять алфавит источника и требовать увеличения скорости передачи криптограммы в открытом канале;

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

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

В дискретном канале передачи применяются M разных сигналов, т.е. каждому символу a_i соответствует свой сигнал s_i. Шифратор в дискретном канале не меняет сигналов, он меняет лишь соответствие символов сигналам. Это означает, что в качестве криптограммы можно рассматривать тоже последовательности символов, выбираемых, в общем случае, из некоторого P- ичного алфавита С = { c₁ , …, c_k, …, c_P } (рис. 3.15):

сообщения источника X криптограмма Y

…a_ia_ja_ka_la_m… …c_fc_gc_hc_ec_l …

(" a Î A) (" c Î C)

Рис. 3.15. Преобразование сообщения источника

в криптограмму

В общем случае алфавиты A и C могут не совпадать ни по изображению, ни по названию, ни по значению (семантике) их символов. Принципиально важным является лишь ограничение, налагаемое на мощности (т.е. число символов) алфавитов A и C. Оператор F не должен расширять алфавит источника, следовательно: P £ M. Из условия обратимости криптопреобразования (F ^-1 F=1) следует: P ³ M. Отсюда вытекает: P = M, т.е. алфавиты A источника сообщений и криптограммы C должны иметь одинаковое число символов (быть равномощными). Следовательно, алфавиты A и C просто совпадают, т.е. A = C. Таким образом, любой оператор шифрования F реализует какое-то взаимно однозначное отображение конечного множества A (алфавита источника) на себя.

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

Подстановку на конечном множестве можно задать и описать разными способами:

– направленным графом;

– перестановкой на исходном стандартно упорядоченном алфавите A;

– таблицей соответствия.

Множество подстановок Y совпадает с множеством ключей. Каким бы ни был способ задания подстановки Ψ _j (т.е. прямого ключа), он всегда однозначно определяет подстановку Ψ _j ^-1 (т.е. обратный ключ). По этой причине рассматриваемые криптосистемы называют одноключевыми (или с имметричными, или классическими).

В конечном множестве с числом элементов (мощностью) M существует ровно M! подстановок, включая тождественную. Общее число ключей шифрования (числа реализаций оператора F) равно

где – мощность множества подстановок на множестве А мощности | A | = M.

3.5.3. Совершенная секретность и случайные ключи

По определению, криптоалгоритм обладает свойством совершенной секретности, если p (a_i / c_k) = p (a_i) для всех i, k = 1, 2, …, M, где p (a_i), p (a_i / c_k) – соответственно априорная и апостериорная (при известной криптограмме) вероятности сообщения a_i, c_k – полученная с помощью ключа Ψ _j криптограмма.

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

Необходимым и достаточным условием совершенной секретности является независимый (от сообщения) и случайный выбор ключа. Ключ называется случайным, если вероятность выбора в качестве ключа подстановки Ψ _j одинакова для всех j = 1, …, M!

.

3.5.4. Свойства криптопреобразования со случайным ключом. Информационная цена криптозащиты

Число ключей, переводящих сообщение a_i в сообщение c_k, равно (M- 1)!. Следовательно, при случайном ключе вероятность преобразования сообщения a_i в криптограмму c_k одинакова для всех i, k:

.

Это означает, что в потоке криптограмм все символы появляются одинаково часто, независимо от распределения символов в потоке сообщений, потому что:

.

Энтропия потока криптограмм при случайном ключе максимальна и равна информационной ёмкости алфавита источника:

Энтропия случайного ключа Ψ _j также максимальна и тоже равна информационной ёмкости M- множества:

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

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

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

3.5.5. Первая криптотеорема Шеннона

Абсолютная избыточность источника равна:

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

Средняя взаимная информация между криптограммой и ключом равна абсолютной избыточности источника сообщений: = R _ист (первая криптотеорема Шеннона).

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

Принципиальное значение первой криптотеоремы Шеннона определяется двумя обстоятельствами:

1) для криптографии она указывает пути повышения криптостойкости криптоалгоритмов,

2) для криптоанализа она обосновывает оптимальную (в смысле минимума затрат ресурсов) стратегию «силовой атаки» на криптосистему.

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

Целью «взлома» криптосистемы является поиск ключа Ψ _j. С вероятностью единица это можно сделать только методом перебора различных комбинаций сообщений и ключей, приводящих к данной криптограмме. Необходимым условием при этом является наличие критерия успеха. Если источник избыточен, то естественным критерием успешности перебора является апостериорная вероятность сообщения при данной криптограмме и очередном подбираемом ключе.

В одном предельном случае R _ист = H _max = log₂ M и H _ист = 0 взаимная информация между ключом и криптограммой максимальна и равна log₂ M. Это означает, что источник «почти всегда» создает лишь одно какое-то сообщение a_i, оно «почти наверное» известно криптоаналитику. Поэтому, перехватив криптограмму c_k, можно сразу, не перебирая все M сообщений (потому что M – 1 из них практически никогда не возникают на выходе такого источника), определить применяемый ключ (точнее, подмножество из

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