Лекции, страница 3

так, что первые k=4 столбцов образуют единичную матрицу E. Таким образом матрицу g можно записать как g=(E,P), где P –остальные столбцы матрицы g.

При кодировании некоторого числа x , например i=0110 (число 6 в десятичной системе счисления), мы получим новое число y=i*g=(0110110). Сравнив x и y, можно заметить, что первые 4 символа числа y совпадают с числом x, они называются информативными, оставшиеся – проверочными. Коды, у которых кодируемое слово содержится в его коде называются разделимыми.

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

y*H=0, где H=(P/E) – проверяющая матрица.

В данном случае Н=

Если это условие выполняется, то слово передано без ошибок.

Действительно, y*H=x*(E,P)*(P/E)=P+P=0 (P+P=0 из условия, что 1+1=0). На самом же деле получится строка, состоящая из трех элементов, каждый из которых равен нулю, если ошибок нет.

Рассмотрим кодовое слово a вида ( a₁, a₂ , a₃ , a₄ , a₅ , a₆ , a₇ ) и строку b=(b₁ , b₂ , b₃ ) как результат a*H. По правилу умножения матриц получим 3 уравнения:

a₁+ a₂ + a₄ + a₅ = b₁

a₁+ a₃ + a₄ + a₆ = b₂

a₂+ a₃ + a₄ + a₇ = b_3.

Допустим теперь, что a₁ ошибочен, тогда b=(110)

Если a₂ , то b=(101).

Если a₃ , то b=(011).

Если a₄ , то b=(111).

Если a₅ , то b=(100).

Если a₆ , то b=(010).

Если a₇ , то b=(001).

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

Такая строка, в общем случае не равная нулю, называется синдромом ошибки.

Вопрос: сколько необходимо синдромов, чтобы исправить q>1 ошибок?

Если n длина кодового слова, то

n+C_n¹+ C_n²+ C_n³+…+ C_n^q=Q.

Условие: Q<=2^n-k.

Для совершенного кода должно выполняться: Q+1=2^n-k.

Пример:

Пусть n=15, q=2, тогда Q=15+ C₁₅²=120, т.е. для обнаружения двух ошибок необходимо 120 синдромов, т.е. 7 проверяющих символов.

Циклические коды.

В качестве порождающего элемента берется полином g(x).

Пример для кода с параметрами (7,4).

Пусть g(x)=x³+x+1, этот полином соответствует двоичному числу 0001011.

Циклическим код называется потому, что при умножении g(x) на x разряды сдвинуться:

g(x)*x=x⁴+x²+x 0010110

g(x)*x²=x⁵+x³+x² 0101100

Поскольку, для n=7 максимальная степень полинома = 6, то

g(x)*x⁴=x⁵+x⁴ +1 0110001, т.е. степень берется по модулю 6 (в общем случае n-1).

Возьмем i = 6₁₀=0110₂, т.е. i(x)= x²+x .Тогда i закодируется как y(x)=i(x)*g(x)=(x²+x)*(x³+x+1)=x⁵+x⁴+x³+x. Числу i соответствует код y=0111010-как видно код неразделимый.

Для раскодирования применяют обратную операцию: i(x)=y(x)/g(x).

Если на выходе приемного устройства имеем полином y(x)= x⁵+x⁴+x³+x (0111010), то остаток от деления естественно будет =0, т.е. слово передано без ошибок.

Если же произошла ошибка (на выходе имеем, например, y(x)= x⁵+x⁴+x³+x+1, т.е. 0111011), тогда остаток от деления r(x) =1 и, очевидно, что ошибка в первом разряде кода. Вообще, если остаток от деления содержит одно слагаемое х^к, то надо изменить соответствующий разряд а принятом слове, т.е. исправленное слово будет y(x)+ х^к.

Если r(x) равен какому-то полиному, то осуществляем сдвиг разрядов влево до тех пор пока r(x) не будет содержать одно слагаемое, что соответствует одной ошибке.

Например: на выходе y(x)= x⁶+x⁵+x⁴+x³+x (1111010), r(x)= x²+1. Осуществим сдвиг и получим новый полином y(x)= x⁶+x⁵+x⁴+x²+x+1 (1110101), остаток от деления которого r(x)=1, что говорит о том, что ошибка была в последнем разряде исходного кода. Исправив ее , осуществляем сдвиг полинома вправо и получаем верное слово.

На основе циклического кода можно построить разделимый код:

Циклический код c параметрами n и k и порождающим полиномом g(x) можно свести к коду Хэмминга, матрица g тогда будет

Где S_i= остатку от деления X^n-I на g(x) .

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

Хⁱ- разряд , с которого начинается область ошибок. ( с учетом цикличности). Очевидно , что для обнаружения и исправления ошибок , группирующихся в пакет , надо меньше синдромов , чем при их произвольном расположении. Например, при n=15

Q = 15 * 4 = 60.

Адаптивное кодирование.

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

Кодирование с целью сокрытия информации.

Принципы классификации:

I.

1. Непрерывный код: сообщение кодируется обычным способом (например, двоичный код), далее складывают этот основной код со скрамблером ( от англ. «scramble»-свалка)-псевдослучайный код (генерируется программой).

Например: мы имеем непрерывную последовательность обычного кода (11001110010) и скрамблер (1001), тогда

11001110010

10011001100

01010111110 передаваемый код.

(правила суммирования смотри выше).

Для раскодирования получатель должен иметь точно такую же программу.

1. Блочная кодировка ( сообщение кодируется блоками 1001 0101 1010).

II.

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

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

Несимметричный ключ.

Наиболее известен код RSA

Пусть шифруется некоторое число А в число В, а расшифровывается другим ключом.

Открытый ключ состоит из (n, S):

Пусть

Пусть

Закрытый ключ:

Чтобы создать ключ необходимо взять произведение двух простых чисел:

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

Для ускорения этой процедуры предложен «Алгоритм Шора».

Пусть требуется разложить n на простые множители:

Возьмём любое a, которое не является делителем числа n.

Тогда, найдём периодичность значений, получающихся из выражения:

a ^x/ mod n, где x=0, 1, 2,……, другими словами, мы имеем последовательность остатков: m1, m2, m3, m4, m5, m1, m2,……, которые

r=6

имеют некоторый период равный r значений. Зная значение r, мы можем найти y1 и y2:

После чего находим НОД от y1 и y2:

НОД(y1, n); НОД(y2, n). Это и будут простые сомножители n.

Рекордные цифры о записи, чтении, скорости передачи и стоимости информации.

• Скорость передачи информации по кабелю между Японией и США составляет 80 Гб/с;

• Плотность магнитной записи ρ_м=10⁹ бит/см²;

• Плотность оптической записи ρ_о=10⁹ бит/см^{2 -}10¹⁰ бит/см²;

Оптическая запись осуществляется многослойно: с одной стороны просвечивают с частотой ν1, а с другой с частотой ν2, как раз на пересечении ν1 и ν2 и образуется слой информации:

• Скорость обработки информации

в электронном процессоре ;, в оптическом процессоре можно осуществлять 10²⁰ не элементарных операций в сек.

• Минимальная цена единицы информации это переход кванта с одного энергетического уровня на другой, при этом должно выполняться условие:

E1 (N₁)

d

E2 (N₂)

Где d – расстояние между уровнями должно быть больше kT хотя бы в

два раза. При этом . 2кТ-это и есть минимальная энергетическая цена единицы информации.