екекркер. Кодирование. Основы теории кодирования. Кодирование. Основные понятия

• Название: Основы теории кодирования. Кодирование. Основные понятия
• Анкор: екекркер
• Дата: 02.05.2022
• Размер: 0.93 Mb.
• Имя файла: Кодирование.doc
• Тип: Глава; #507638
• страница: 4 из 4

2.10. Некоторые методы построения блочных корректирующих кодов

1. Коды, построенные на основе увеличения кодового расстояния

Идея обнаружения и исправления ошибок в таких кодах заключается в следующем. Для передачи символов сообщения используют не все N возможных комбинаций элементов символов кода длиной n, а только часть из них N₀, которые называются разрешенными символами кода. Оставшиеся ΔNкомбинаций (ΔN = N – N₀)называют запрещенными. Ошибка обнаруживается тогда, когда приемник получает запрещенную комбинацию элементов символов кода. Всякий код, у которого ΔN> 0, способен обнаруживать ошибки в ΔNслучаях из N. Доля обнаруживаемых ошибок (s) определяется выражением:

.

По формуле (2.9) легко определить избыточность такого корректирующего кода (R_k):

,

где H(N₀ )—энтропия кода с объемом алфавита N₀ ;

H(N)—энтропия кода с объемом алфавита N;

n— число элементов в кодовом символе;

m_k— основание кода.

Исправление ошибок в корректирующих кодах заключается в том, что, обнаружив ошибку, определяют кодовое состояние от полученной запрещенной комбинации k_iдо всех разрешенных символов кода k_j(j=1, 2, ..., N₀) и в качестве переданного символа кода считается тот из разрешенных символов кода, до которого расстояние минимально. Таким образом, исправление ошибок корректирующими кодами производится с помощью трех последовательных операций:

- определения кодового расстояния между принятой кодовой комбинацией и разрешенными кодовыми символами;

- отыскания минимального кодового расстояния;

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

Например, в трехзначном равномерном двоичном коде число возможных кодовых комбинаций 8:

000, 001, 010, 011, 100, 101, 010, 111,

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

Если увеличить кодовое расстояние (d_ij=2), т.е. сделать разрешенными кодовые символы отличающимися в двух элементах (001, 111, 010, 100), то помехозащищенность кода увеличивается. Действительно, если в процессе передачи возникает ошибка только в одном элементе любого разрешенного символа, то эта комбинация превращается в запрещенную, что свидетельствует о появлении одиночной ошибки в символе кода, хотя и неизвестно какой именно. Такой код не позволяет выяснить какой конкретно из передаваемых элементов искажен, а значит и не позволяет исправить ошибку.

Если еще больше увеличить кодовое расстояние (d_ij=3), т. е. сделать разрешенными кодовые символы отличными друг от друга в трех элементах (напри­мер, 111, 000), то помехозащищенность кода еще более возрастает.

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

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

d_ij = 1 + p + q ,

где p ≥ q;

p— количество обнаруживаемых ошибок в символах;

q— количество исправляемых ошибок в символах кода.

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

Таблица 2.7

Характеристика кодов			Свойства кодов
d	p	q
1	0	0	Отличает одну кодовую комбинацию от другой.
2	1	0	Обнаруживает одну ошибку.
3	1	1	Обнаруживает и исправляет одну ошибку.
	2	0	Обнаруживает две ошибки.
4	2	1	Обнаруживает две ошибки и исправляет одну.
	3	0	Обнаруживает три ошибки.
5	2	2	Обнаруживает и исправляет две ошибки.
	3	1	Обнаруживает три ошибки и исправляет одну.
	4	0	Обнаруживает четыре ошибки.
			и т. д.

2. Коды, построенные на основе проверки на четность.

Этот метод построения помехозащищенных кодов заключается в том, что в каждый кодовый символ двоичного кода добавляется для проверки один избыточный элемент (0 или 1) так, чтобы общее количество единиц в каждом символе кода было четным. Построение такого кода на примере двухэлементного двоичного кода представлено в Таблице 2.8.

Таблица 2.8.

Неизбьггочные кодовые символы.	Kонтрольный избыточный элемент.	Полные кодовые символы, обнаруживающие единочную ошибку.
00	0	000
01	1	011
10	1	101
11	0	110

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

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

3. На основе защиты сдвоенными элементами.

В этом коде количество элементов в символах двоичного кода удваивается, причем к каждому элементу «0» приписывается «1», а к каждому элементу «1» приписывается элемент «0». Например, исходный кодовый символ 11010 по этому методу кодируется следующим образом:



Рис. 2.7. Метод построения корректирующего кода на основе защиты сдвоенными элементами.

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

2.11. Кодирование как средство защиты информации от несанкционированного доступа.

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

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

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

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

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

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

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

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

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

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

Представляет интерес рассмотрение некоторые из них на примере шифрования текстов.

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

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

а б в г д ъ э ю я

г д е ё ж я а б в

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

В художественной литературе классическим примером шифра простой подстановки является шифр «Пляшущие человечки» (К. Дойль).

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

Ещё одним примером шифра подстановки может служить, так называемый, квадрат Полибия. Шифрование в этом случае заключается в следующем. В квадратную матрицу с числом элементов равным или большему объёму алфавита на место каждого элемента в произвольном порядке вписываются все буквы алфавита. Шифруемая буква заменяется её координатами в матрице. При расшифровке каждая пара чисел определяла соответствующую букву сообщения. Ключом является расположение букв в исходной матрице. Отметим, что при произвольном расположении букв в матрице возникает некоторое затруднение: либо надо помнить отправителю и получателю сообщения заданное расположение букв в матрице (ключ шифра), что затруднительно, либо иметь при себе запись этого ключа, что представляет опасность ознакомления с ключом посторонних лиц. Поэтому в ряде случаев ключ представляют следующим образом. Берётся какое-либо «ключевое слово», которое легко запомнить, удаляют из него повторы букв и записывают его в начальных элементах матрицы. На место остальных элементов записывают остальные буквы алфавита в естественном порядке. Разновидностью такого шифра является, так называемый, «тюремный шифр» при котором матрица заполняется буквами в порядке их следования в алфавите.

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

Шифры перестановки. Суть этого шифра заключается в следующем: берётся некоторое число n и записывается в строку ряд чисел 1, 2 … n затем под ними записываются те же цифры в произвольном порядке. Например, для n = 5:

1 2 3 4 5

4 3 2 5 1

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

Шифр Вижинера. Шифрование по этому методу заключается в следующем. Каждая буква алфавита нумеруется, скажем, для русского языка ставятся в соответствие цифры от 1 (А = 1) до 33 (Я = 33).

А	Б	В	…	Я
1	2	3	…	33

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

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

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

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

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

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