что такое блочный код

Блочный код

Главная характеристика блочного кода состоит в том, что это – канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана, и в отличие таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование) ). Обычно, система блочного кодирования получает на входе k-значное кодовое слово W, и преобразовывает его в n-значное кодовое слово C(W). Это кодовое слово и называется блоком.

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

Содержание

Формальное определение

Компромисс между эффективностью (большей скоростью передачи информации) и способностями исправления может также быть виден при попытке задать фиксированную длину ключевого слова, и фиксированную возможность исправления (представленную расстоянием Хемминга d) и максимизируют общее количество ключевых слов. [n, d] — максимальное число ключевых слов для данной длины ключевого слова n и расстояния Хемминга d.

Информационные нормы

.

.

Сферические упаковки и решетки

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

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

Источник

Что такое блочный код

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

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

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

Пример 149. Построить (3,5)-код, используя следующую 355 матрицу:

Решение. Полный список кодирования таков:

Этот список показывает преимущество матричного кодирования: достаточно запомнить кодовых слов вместо слов.

где в качестве выбирается слово наименьшего веса, называемого лидер ом этого класса.

Пример 150. Составить таблицу декодирования для (3,5)-кода из предыдущего примера.

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

Вопросы для самоконтроля

1. Как определяется вес слова?

2. Какая связь между кодовым расстоянием и весом слова?

3. Существует ли связь между вероятностью принятия переданного слова и расстоянием между переданным и принятым словами?

4. Необходимые и достаточные условия обнаружения ошибок.

5. Назовите условия исправления ошибок.

6. В чем заключается методика матричного кодирования?

7. Какой код называется групповым?

8. Геометрические интерпретации кодирующих и декодирующих систем.

I 291. Докажите, что если расстояние между кодовыми словами равно 5, то код способен обнаруживать до четырех ошибок и исправлять до двух ошибок.

292. Какова вероятность того, что не будет обнаружена ошибка при пере-даче слова в (6,7)-коде с проверкой на четность?

293. Вычислите вероятность пропуска ошибок в таком (4,8)-коде, что минимальное расстояние между кодовыми словами равно 4.

294. Рассмотрите (3,4)-код с проверкой на четность и (3,6)-код с двукратной передачей. При вычислите вероятность того, что ошибочно переданное слово не будет обнаружено.

295. Найдите кодирующую матрицу для (3,4)-кода с проверкой на четность.

296. Найдите кодирующую матрицу для (2,6)-кода с трехкратной передачей.

II 297. Код задан матрицей

Какова вероятность того, что слово будет принято как правильное, тогда как на самом деле остались необнаруженными ошибки?

298. Постройте стандартную матрицу, порождающую код, эквивалентный коду с матрицей

III 299. Покажите, что следующие операции над кодирующей матрицей приводят к эквивалентному коду:

а) перестановка строк,

б) перестановка столбцов,

в) замена одной строки суммой ее с другой строкой.

Источник

Кодирование для чайников, ч.1

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

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

0. Начало

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

1.1 Речь, мимика, жесты

1.2 Чередующиеся сигналы

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

1.3 Контекст

2. Кодирование текста

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».

2.1 Блочное кодирование

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

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Раздел создан при поддержке компании

Кодирование

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

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

Шеннон [1] показал, что имеется принципиальная возможность использования дискретного зашумленного канала для передачи информации со сколь угодно большой степенью надежности и с любой скоростью, не превосходящей пропускную способность канала. Он также показал, что задачу надежной коммуникации можно разложить на две подзадачи:

Приведенная выше схема детализируется:

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

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

Пример. Конспектирование студентом лекции можно считать кодированием лектора как источника звуковых сигналов и изображений (на доске или презентации).

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

Типы кодов

Блочные коды

Пример 1. Пусть алфавит языка состоит из пяти букв:

Этот пример служит примером кода, исправляющего ошибки — в данном случае одну ошибку.

декодирование всегда производить в «ближайший» кодовый блок.

Подробнее — в разделе ☞ КОД ХЭММИНГА.

Префиксные (древовидные) коды

Пример. Пусть кодирование производится по правилу:

Пример. Код

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

Приведите пример непримитивного префиксного кода.

Граф кода называется его деревом, отсюда идет другое название префиксных кодов — древовидные.

Источник

RC6. От простого к сложному

В этой статье вы узнаете

Кто этот ваш блочный шифр.

Каких принципов придерживались создатели алгоритма.

Как выглядит процесс подготовки ключа.

И причем тут вообще RC5?

Введение в RC6.

Для начала разберемся с терминологией:

Что значит симметричный?

Есть два типа людей шифров:

Симметричные (то, что нам нужно)

Ассиметричные (как-нибудь в другой раз, бро)

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

Алгоритмы симметричного шифрования:

AES (Advanced Encryption Standard)

3DES (Triple Data Encryption Algorithm )

RC4, RC5, RC6 (Rivest cipher)

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

Алгоритмы ассиметричного шифрования:

DSA (Digital Signature Algorithm), DSS (Digital Signature Standard)

Что значит блочный?

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

Чтобы стало яснее, рассмотрим один из методов построения блочных шифров: сеть Фестеля.

Какая, какая сеть?

Фестеля. Это конструкция из ячеек. На вход каждой ячейки поступают данные и ключ. А на выходе каждой из них изменённые данные и изменённый ключ.

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

Каждый из блоков делится на два подблока одинакового размера — левый и правый.

Правый подблок скармливается функции .

После чего умножается по модулю 2 (операция xor) с левым блоком .

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

А правый подблок (без изменений) выступит в роли левого подблока.

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

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

Замечание. Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке.

Выглядит это примерно так:

Параметры алгоритма

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

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

Все основные вычисления, которыми оперирует алгоритм, имеют битные машинные слова в качестве входа и выхода. Как мы уже выяснили, RC6 блочный шифр. Причем входной и выходной блоки имеют 4 регистра A, B, C, D каждый размером по бит. Обычно . Тогда размер блока будет бит.

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

размер слова в битах. Каждое слово содержит слов в байтах. Блоки открытого текста и шифротекста имеют длину по бит (т.к. 4 регистра).

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

секретный ключ размеров байт: .

Чтобы было ясно, о каком алгоритме идем речь принято писать .

Схема подготовки ключа

Алгоритм подготовки ключа состоит из трех простых этапов и использует две магические константы:

Генерация констант

Для конкретного мы определяем две величины:

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

Например, если взять , то значения получатся такие:

Теперь рассмотрим основные этапы. Их три:

1 этап. Конвертация секретного ключа

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

2 этап. Инициализация массива ключей

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

3 этап. Перемешивание

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

На этом схема подготовки ключа закончена и хочется поскорее узнать, как работает сам алгоритм RC6. Но мы не будем спешить и для того, чтобы было проще понять принцип его работы, рассмотрим предыдущию версию RC5. А также рассмотрим шаги развития этого алгоритма, которые привели Рональда Ривеста к конечному варианту шифра RC6:

Немного про RC5

RC5 блочный шифр, разработанный Рональдом Ривестом в 1994 году. Одно из отличий от RC6 это то, что он имеет два регистра на входе и на выходе вместо четырех. Второе отсутствие операции умножения в процессе вычислений.

Рональд Ривест писал, что при создании этого шифра он придерживался нескольких правил:

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

RC5 должен использовать только примитивные операции, реализованные на большинстве процессоров.

RC5 должен быть адаптирован к процессорам с разной длиной машинного слова. Например, когда станут доступны 64-битные процессоры, RC5 сможет на них работать.

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

RC5 должен иметь переменное количество раундов. Чтобы пользователь мог выбирать между более высокой скоростью вычислений и более высокой безопасностью.

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

RC5 должен быть простым в реализации и иметь невысокие требования к памяти.

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

Процесс подготовки ключа у RC5 точно такой же, как и у RC6. А вот сам алгоритм шифрования и расшифровки проще. Cхема шифрования RC5:

А псевдокод буквально состоит из пяти строчек:

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

Путь от RC5 к RC6

Возьмем от RC5 все самое лучшее:

Рассмотрим основные шаги, которые привели Рональда Ривеста к конечному варианту RC6.

Начнем с базового полу-раундового(переменные обновляются поочередно) алгоритма RC5:

Запустим параллельно две копии RC5. Первую на регистрах A и B, а другую на C и D:

Вместо того, чтобы менять местами A на B и C на D, поменяем регистры (A, B, C, D) = (B, C, D, A). В этом случае вычисления на блоке AB перемешиваются с вычислениями на блоке CD:

Далее еще раз смешаем AB и CD переставив циклические сдвиги:

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

Частный случай такого преобразования функция , за которой следует сдвиг влево на пять битовых позиций:

И на десерт сделаем так, чтобы операции, используемые на начальном шаге первого раунда и заключительном шаге последнего раунда отличались от преобразований всех остальных раундов(такая операция, называются pre- и post-whitening):

Теперь после того, как мы тут все замиксовали, посмотрим еще раз на то, что имеем:

Шифрование

Еще раз напомним, что RC6 работает с четырьмя битными регистрами A, B, C, D. Они содержат исходный входной открытый текст, а также выходной шифротекст. Причем первый байт открытого текста или шифротекста помещается в младший байт A, а последний байт в самый старший байт D. Ниже приведен псевдокод:

Схема одного раунда в алгоритме RC6 выглядит так:

Дешифрование

Для полноты картины еще немного псевдокода по дешифровке:

Что по атакам?

Для варианта алгоритма RC6-128/20/b никаких атак не выявлено. Атаки слева были обнаружены только для варианта алгоритма с числом раундов

Полагается, что лучший вариант атаки на RС6 полный перебор байтового ключа шифрования. Для него потребуется операций. Однако, было замечено, что за счет значительной памяти и предварительного вычисления можно организовать атаку встреча посередине, которая потребует операций. Что тоже очень много.

Для таких типов атак, как дифференциальный и линейный криптоанализ, приведем следующую таблицу:

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

Таким образом, приходим к выводу, что RC6 с 20 раундами защищен от дифференциальных и линейных криптоаналитических атак.

Выводы

Так же существуют улучшения алгоритма RC6, такие как RC6_en, но о нем как-нибудь в другой раз.

Источник