Системи кодування інформації:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук
Для ФІН

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Зміст

Ентропiя,як мiра невизначеностi.Довести,що ентропiя набуває максимального значення на рiвномiрному розподiлi.

ξ - випадкова величина


ξ x1 x2 x3 ... xn
p1 p2 p3 ... pn


\sum_{i=1}^n p_i =1


Інформаційна Ємність (content)

h( x=xi ) = -logb(pi) = logb(1/pi)

Якщо b = 2, то Ємність називається бітовою

Означення

Ентропія - середнє значення Інформаційної Ємності наших результатів.


H(\xi) = - \sum_{i=1}^n p_i*\log_{2}p_i

Ентропія міряє невизначеність

Властивості ентропії:

1. H(\xi) \ge 0; H(\xi) = 0 \Leftrightarrow \exists i: p_i = 1

2. H(ξ) ≤ H( ξ(рівномірна) )


H(ξ) ≤ H( ξ(рівномірна) ) - ентропiя набуває максимального значення на рiвномiрному розподiлi

Доведення

Нерівність Йєнсена
X - random value
H(\xi) = - \sum_{i=1}^n p_i*\log_{2}p_i
Для рівномірного розподілу : pi = 1/n , маємо :
H(X_{uniform}) = - \sum_{- \infty}^{\infty} \frac{1}{n}* \log(1/n);
Сума від 0 до n числа A - це N*A. log(1/n) = -log(n). Тепер:
H(X) = N * ( 1/n * log(n) ) = log(n).
log(n) - maximum.


Довести, що умовна ентропiя не перевищує абсолютної.

[відповідальний Крячко Макс]


Є важлива нерівність:

H(_eta)[ksi] <= H(ksi)


Доведення:


(доводиться за допомогою нерівності Енсона)

Беремо функцію f(x)=-x*log(_2)[x]

lambda(_i)=q(_i)

x(_i)=p(x(_k) | y(_i))

-SUM(_i=1)(^n)[q(_i)*x*l] <= SUM(_i=1)(^n)[ q(_i)*p( x(_k) | y(_i)) ]

Нерiвнiсть Гiбса.

[відповідальний Крячко Макс]


До якої межі мона стискати інформацію?

Нерівність Гіббса: SUM(_i=1)(^n)[ p(_i)*log(^2)[1/q(_i)] ] >= SUM(_i=1)(^n)[ p(_i)*log(^2)[1/p(_i)] ]

SUM(_i=1)(^n)[q(_i)]=1


Відомо, що нерівність і враховуючи: L(c)=SUM(_i=1)(^n)[ l(_i)*p(_i) ] q(_i)=2*((l(_i))/(SUM(_i=1)(^n)[2(^l)]))=2*(-l/Z)

-l(_i)=(log(_2)[1/q(_i)])*log(_2)[Z]

L(c)=SUM(_i=1)(^n)[log(_2)[1/q(_i)]]-log(_2)[Z] За нерівністю Гіббса: SUM(_i=1)(^n)[log(_2)[1/q(_i)]]-log(_2)[Z] >= SUM(_i=1)(^n)[ p(_i)*log(_2)[p(_i)] ]-log(_2)[Z] >=H(ksi) Ми довели,що l має бути не довшим і ближчим до log(_2)[p(_i)

5. Символьне кодування, префiкснi коди. Нерiвнiсть Крафта-Макмiлена для символьного бiнарного кода з однозначним декодуванням ???

[відповідальний RST]

/*ми хочемо означити переведення алфавіту А в алфавіт В таким чином, шоб це переведення було однозначне для кожного символа.*/

A={a_1,a_2,…a_n}; B={b_1,b_2….b_n} /*частковий випадок – {0,1}*/

A* э S |= S->B* /*ми тоді говорили про якесь включення у якісь більші алфавіти… а, хоча, хз шо це. Так написано… */

А->B* /*переводимо А в якийсь алфавіт В, але не символ->символ, а символ –> слово. */

A_(1)->b_(i1)b_(i2)…b_(in) A_(2)-> b_(j1)b_(j2)…b_(jn) /*тобто, кожному символу співтавляємо якесь слово з симовлів з алфавіту B*/

Код є префіксним, якщо жоден префікс елементарного кодового слова не є сам елементарним кодом

Нерівність Крафта-Макмілена

Теорема: нехай є шифрувальна схема кодування, яка допускає однозначне декодування. e_i iє1..n – довжина елементарного коду.

SUM(_i=1)(^n)[2^(-e_i)]<=1.

Позначимо за Ню(n,t) – кількість доданків (e_(i1)+e_(i2)+…+e_(in))=t.

(SUM(_i=1)(^n)[2^(-e_i)])^n=SUM(_i=1)(^n)[2^(-e_(i1)+e_(i2)+…+e_(in))]= SUM(_t=1)(^n)[2^(-t)*Ню(n,t)]., а оскільки Ню(n,t)<=2^(t), то теорема доведена./*2^(-t)*2^(t)=1. тобто, всі члени суми<=1.*/

/*не питайте чого, сам не шарю ні букви з того шо тут накатано… тому, ті хто шарять –перевірте. Як все це буде аппрувед – мої коменти можна стирати.*/

Довести iснування префiксного бiнарного кода для заданого розподiлу довжин елементарних кодiв,що задовольняють нерiвнiстi Крафта-Макмiлена. ???

[відповідальний Сосо Івоса]

Символьне кодування-кодується кожен символ Є алфавіт A={a,b,c...} {0,1} A^*-множина слів {0,1}^* Код С - це відображення : A -> {0,1}^* Вимога: w_1,w_2 єA^*, w_1не=w_2 => c(w_1)не= c(w_2) Префіксний код є таким якщо жоден префікс кодового слова не є кодовим словом. Множина кодових слів складається з таких a та b: a->c(a)=(0....) b->c(b)=(....) Теорема. Префіксним код є кодом з однозначним декодуванням. Якщо l_i - довжина ітогокоду слова p_i - імовірність появи слова в тексті L(c)=сума(знизу i=1, зверху n)p_i l_i - середня довжина n-к-сть елементів в алфавіті Крафта-Макмiлен: сума(знизу i=1, зверху n)2^(-l_i)<=1 Якщо код є кодом з однозначним кодуванням, то довжини l_i мають задовільняти нерівність Доведення: (сума(знизу i=1, зверху n)2^(-l_i))^n=сума 2^(-(l_i_1+l_i_2+...+l_i_n))=сума(знизу t=1, зверху l_max=n)v(n,t)*2^(-t) l_max - max довжина; v(n,t)-к-сть речень Яка максимальна к-сть таких повторень? не більше 2^t сума(знизу t=1, зверху l_max=n)v(n,t)*2^(-t)<=сума(знизу t=1, зверху l_max=n)2^t * 2^(-t)=n*l_max сума(знизу i=1, зверху n)2^(-l_i)<= корінь n-ого степеня з n*l_max прямує до 1 => сума(знизу i=1, зверху n)2^(-l_i)<=1 Теорема.Завжди існує префіксний код C для якого має місце Н(ксі)<=L(c)< H(ksi)+1

7. Середня довжина кодування. Застосування нерiвностi Гiбса для доведення нерiвностi H(C) <= L(C) для символьного коду C. ???

[відповідальний RST]

a_1,… a_n – літери алфавіту.

p_1,p_2,…p_n – ймовірності зустрічі літери в тексті.

l_1,…l_n – довжини елементарних кодів./*l – L маленька…*/

H(c) – ентропія.

ТЕОРЕМА: L(c) = \sum_{i=1}^n l_i * p_i \ge H(c)

Доведення:

z = \sum_{i=1}^n 2^{-l_i} \le 1 /*бо l_i >1, бо це довжини елементарних кодів => 2^(- l_i)<1; тоді log (z) < 0*/

q_i = \frac {2^{-l_i}} {z}

\sum_{j=1}^n q_j = 1

L(c) = \sum_{i=1}^n p_i * l_i \,\! = - \sum_{i=1}^n p_i * log_2 2^{-l_i} = - \sum_{i=1}^n p_i * log_2 (q_i * z) = - \sum_{i=1}^n ( p_i * log_2 q_i + p_i * log_2 z ) \ge - \sum_{i=1}^n p_i * log_2 p_i - log_2 z = H(c) - log_2 z \ge H(c)

SUM(_i=1)(^n) [ l_i * p_i ]>=- SUM(_i=1) (^n) [ p_i * log2(p_i) ]

P_i=q_i=(2^(l_i)/( SUM (_j=1) (^n) [2^(-l_j)]). )/( SUM (_j=1) (^n) [2^(-l_j)])=z.

/*шось типу цього… перегляньте хтось свої конспекти…бо шось я не бачу логіки тут…*/

8. Для даного розподiлу ймовiрностей символiв алфавiту,довести iснування символьної схеми кодування C : L(C)<=H(C)+1 ???

[відповідальний RST] A={a_1,a_2,…,a_n}

a_1 – p_1 /*співвідноситься, напевно… */ a_2 – p_2 … a_n – p_n.

ТЕОРЕМА: Існує префіксий код С: H(c) =< L(C) =<H(C)+1.

/*позначення % х% -- заокруглення до верху..*/

l_i= %log2(1/ p_i)%

SUM(_i=1)(^n) [2^ (-l_i)]=SUM (_i=1)(^n) [ %log2 ( 1/p_i )% ] =< SUM (_i=1) (^n) [2^log2 (p_i)] = 1

L(c) = SUM (_i=1)(^n) [ l_i * p_i ] = SUM (_i=1) (^n) [ p_i * %log2 (1/(p_i) ) % ] = H(c)+1

9. Алгоритм Фано. $

[відповідальний RST] Алгоритм фано – це алгоритм префіксного символьного кодування, в основі якого лежить принцип співставлення символам з меншою частосою появи довших кодів.

Алгоритм побудови коду полягає у наступному: (переведення символів з множини символів A ={a_1,a_2,a_3….a_n} до мнодини B*, що складається зі слів алфавіту B={b_1,b_2,…b_n}, якщо є ймовірності появи символів P(a_i)=p_i.)

1) збирається інформація про частоти появи символів у тексті повдомлення (або використовуються якісь універсальні наперед пораховані частоти)

2) за алгоритмом Фано співставляється кожному символу a_i набір символів b_j1,b_j2…b_jk.

3) символи з алфавіту A заміняються наборами символів з алфавіту B. Отже, в чому полягає алгоритм Фано? По-перше, формується масив пар, який складається з літер алфавіту А і ймовірностей їх появи: 

S:=
| a_1 а_2 а_3… а_n|
| p_1 p_2 p_3 …p_n|

Далі ця матриця сортується відносно спадання ймовірностей появи символів. 

S:=
| a_i1 а_i2 а_i3… а_in|
| p_і1 p_і2 p_і3 …p_іn|

Після цього відбувається вертикальний поділ таблиці на дві половини так, щоб сума ймовірностей у кожній половині була найближча до рівності. Тоді, за алгоритмом, _елементам в правій частині матриці S_ в матриці кодів(С) присвоюється 0, а лівій – 1. /*якщо B={0,1} перевірте, бо, можливо, в тому варіанті що давав бондарчук, навпаки – лівій 0, а правій – 1.*/

Далі алгоритм продовжується рекурсивно в обох частинах, а в кінці, якщо подальший поділ неможливий, то отримані набори символів алфавіту B, і є кодами Фано для цього розподілу. Спробуємо на прикладі: 

S:=
| a    b    c    d  |
|0.1  0.2  0.4   0.3|

Сортуємо і ділимо 

S:=
| с   | d    b    a  |
|0.4  |0.3  0.2  0.1|
 0.4     0.6   /*бо альтернативне розбиття – 0.7 0.3 є гіршим*/ 
С:=
| a   b   c   d  |
| 1   1   0   1  |

Продовжуємо розбиття в S[2], бо в S[1] ={c} більше нічого розбивати. 

S[2]:=
| d  |  b    a  |
|0.3 | 0.2   0.1|
 0.3    0.3

С:=
| a     b   c     d  |
| 11   11   0   10  |

Тепер розбиваємо S[2][2]. 

S[2][2]:=
|  b |   a  |
|0.2 |  0.1 |

C:=
| a       b   c     d  |
| 111   110   0    10  |

/*всьо. Хеппі енд.*/

10. Алгоритм Хафмана. $

[відповідальний RST]

Алгоритм кодування Хафмана – це стискаючий префіксний символьний алгоритм, який виник після алгоритму Фано і грунтується на ньому. Вважається кращим від алгоритму Фано.

Так само, як і алгоритм Фано, алгоритм Хафмана переводить літери алфавіту A в набори літерів алфавіту B, відповідно до частоти ймовірної появи символів у тексті.

Основа алгоритму Хафмана полягає також у сортуванні масиву з елементів, але тут є певні відмінності. На початку роботи алгоритму, створюється масив S, який складається з символів алфавіту А і ймовірностей їх появи. 

S:=
| a_1 а_2 а_3… а_n|
| p_1 p_2 p_3 …p_n|

Далі цей масив сортується відносно спадання ймовірності символів /*частоти появи символа*/ і тоді останні два елементи зливаються, а їх кодам у таблиці кодів присвоюються відповідні елемнти з алфавіту В (/*при роботі з B={0,1} їх кодам присвоюються 0 і 1.*/) Для стандартизації буде вважати, що елементу з більшою ймовірністю приписується 1, а з меншою – 0, хоч це і не є важливо. Тобто, після цієї дії матриця S і C набувають такого вигляду: 

S:=
| a_1 а_2 а_3… a_(n-1)а_n|
| p_1 p_2 p_3 …p_(n-1)+p_n|

C:=
| a_1   a_2   a_3  … a_(n-1) … a_n  |
|                      1          0 |

Далі масив S знову сортується, і алгоритм повторюється доти, доки весь масив буде складатися з одного елемента. Після цього коди з масиву C розвертаються, і отримані C* і будуть відповідними словами з B* для символів з алфавіту А.

Розглянемо це на прикладі. 

S:=
| a    b    c    d  |
|0.1  0.2  0.4   0.3|

Сортуємо. 

S:=
| с    d    b    a  |
|0.4   0.3  0.2  0.1|

Тепер зливаємо два останні елементи, змінюючи значення їх кодів. 

S:=
| с    d      ab  |
|0.4   0.3    0.3 |

С:=
| a   b   c   d  |
| 0   1          |

Знову сортуємо масив, і з’єднуємо два останні елементи. 

S:=
| с    abd  |
|0.4   0.6 |

С:=
| a     b   c   d  |
| 00   10       1  |

…І ще раз… 

S:=
| abcd  |
|   1   |

С:=
| a     b    c   d    |
| 000  100   1   10   |

Тепер розвертаємо елементи матриці C: 

С*:=
| a     b    c   d    |
| 000  001   1   01   |

Отже, елементи матриці C* -- це і є співставлення елементів алфавіту А словам з алфавіту B={0,1}.

Як видно з кодів, вони є префіксними, оскільки ніякий початок якогось коду не є одночасно кодом іншого символа.

Арифметичнi коди,як приклади потокових схем кодування(неадаптивний випадок).

[відповідальний Луценко Ігор]

Маємо алфавіт A{x0,x1...,xk} та відповідні ймовірності появи P{p(0),p(1),..p(k)}.

Кожен символ кодується у залежності, що було перед цим.

1. Ділимо відрізок [0,1] на k підвідрізків пропорційно до P.

Тобто об'єдняння цих відрізків Y(0) V Y(1) V Y(2) v...V Y(k-1)=[0,1], а перетин Y(0) Л Y(1) Л Y(2) Л ... Л Y(k-1)=1.

2. Індукційний крок: Ми перейшли до Y(u), де u=x0,x1...xk;

робимо розбиття: Y(u0),Y(u1),..,Y(uk-1)

Вони попарно не перетинаються.

3 Розбиваємо так, маємо A{x0,x1...,xk} P{p(0),p(1),..p(k)} : Y(0)=[0,p(0)],Y(1)=[p(0),p(0)+p(1)], ..., Y(j)=[ SUM(_i=0)(^(j-1))p(i), SUM(_i=0)(^(j))p(i)p(1)]; |Y(j)|=p(j)

4. Замість безумовн. ймовірн. інтервалів працюємо з умовними. p(0|u),p(1|u),..p(k-1|u)

Тепер Y(u)=[a,b]

a0=a,

b0=a+(b-a)p(0|u),

aj=a+(b-a)SUM(_i=1)(^j)p((i-1)|u),

bj=aj+(b-a)p(j|u).

Далі розбиваємо новоутворений інтервал у необх. пропорціях. Зрештою отримуємо певний інтервал.

Берем середину цього інтервалу,тобто це буде якесь число c, переводимо його у двійкове представлення, також нехай довжина останнього отриманного відрізка =t. Кодом повідомлення буде перші (-log[2](t)) символів після коми числа c у двійковому вигляді.

Неадаптивна схема - вважається, що ймовірності не залежать від u.

Ентропiя як нижня межа для середньої довжини кодування арифметичного коду.Пояснити перевагу перед символьним кодуванням.

[відповідальний Луценко Ігор] Ентропія - символа a(_i) визначається як Н=-P(_i)*log(_2)[P(_i)], где P(_i) - ймовірність появи символа a(_i). Ентропія a(_i) - найменьше число біт необхідних, у середньому, для представлення символа a(_i). Сама ж середня довжина кодового повідомлення вираховується за формулою L(b)=SUM(_i=1)(^n)(P(_i)L(_i)(b_i)), де L(b(_i))- довжина коду і-го символу у бітах.

При арифметичному кодуванні текст зазвичай зображується дійсними числами у інтервалі від 0 до 1. Основна процедура кодування це розбиття відрізку на підвідрізки відповідно до ймовірностей символів з алфавфту. Та подальший вібір для наступного розбиття підвідрізка, номер якого дорівнює номеру в алфавіті символа, що оброблюється на даному кроці. Тобто фактично довжини відрізків залежать від ймовірностей появи символів, а саме |Y(i))|=p(i), де Y(i) і-тий підвідрізок,p(i) - ймовірність появи символа. Тобто всі наступні символи тексту скорочують величину інтервалу виходячи з значень їх ймовірностей. Більш ймовірні символи роблять це у меншій мірі, ніж менш ймовірні, і, відповідно, додають меньше бітів до результату.

Середня довжина кодування арифметичного коду при великій кількості символів у алфафіті, наближається до значення ентропії, але L(c)=>H(ksi), тобто вона є нижнею межею.

Принципова різниця арифметичного кодування від символьного у його неперервності. Код знаходиться не для окремих символів, чи їх груп фіксованого розміру,а для всього попереднього повідомлення вцілому. Як вже зазначалося, ефективність арифметичного кодування зростає з ростом довжини повідомлення,а для символьного кодування це не відбувається.

Унiверсальний Lempel-Ziv алгоритм стискання.

[відповідальний Луценко Ігор] Lempel-Ziv

розглянемо роботу Алгоритму на прикладі. Закодуємо 0101111001011 Будемо формувати дві умовні множини словник та власне код. У словник будемо записувати пари: елемент словника(частинка повідомлення) - його порядковий номер у словнику(у бінарному представленні). Кожний крок складається з двох етапів: перший - беремо відрізок з повідомлення(такий якого ще нема в словнику) та заносимо його в словник під певним порядковим номером, другий етап - додаємо до коду інформацію стосовно цього відрізку повідомлення, таким чином "(порядковий номер у словнику відрізку, що розглядається зараз без крайнього правого символу ; крайній правий символ відрізку, що розглядається ка даному кроці)". Спочатку у словник заносимо порожній символ його порядковий номер 0, тобто * - 0(це в бінарному представленні!!!!) Далі проглядаємо з початку повідомлення і беремо найменший перший відрізок, якого ще нема в словнику. У нашому випадку це 0. Додаємо до словника 0 під порядковим номером 1. А до коду додаєм, (*,0).

Далі проглядаємо повідомлення без першого обробленного відрізка і беремо найменший перший відрізок, якого ще нема в словнику. У нашому випадку це 1. Додаємо до словника 1 під порядковим номером 10. А до коду додаєм, (0,1).

Далі проглядаємо повідомлення без першого та другого обробленних відрізків і беремо найменший перший відрізок, якого ще нема в словнику. У нашому випадку це 01. Додаємо до словника 01 під порядковим номером 11. А до коду додаєм, (01 //враховуєм необхідну кількість бітів!!,1). І так далі, аж поки не закінчиться повідомлення. Якшо останній відрізок повідомлення містить в собі менше біт ніж необхідно , щоб однозначно його закодувати, то просто в код додаємо порядковий номер у словнику відповідного відрізку. Так ми кодуємо повідомлення.

Розкодувати 0010111010100. Маємо порожній словник. До нього записуємо порожній символ під номером 0. Далі розглядаємо код з початку. Крайній лівий символ, це є перший символ закодованого повідомлення. Його ми просто записуєм у словник під номером 1. У нашому випадку це символ 0. До розкодованого повідомлення додаєм цей символ. Далі проглядаємо код без першого обробленного відрізка і беремо найменший перший відрізок, якого ще нема в словнику. У нас це 01. Беремо крайній правий символ цього відрізку і записуємо його до розкодованого повідомлення, а те що залишилось заносимо до словника під наступним порядковим номером. Тобто 1 додаємо до розкодованого повідомлення, а 0 заносимо у словник під номером 1. Повторюємо цю процедуру, для інших відрізків. Якшо останній відрізок коду містить в собі менше біт ніж необхідно , щоб однозначно його декодувати, то це значить, що це записаний лише код якогось елемента зі словника, тому шукаємо який елемент у словнику має такий код і додаємо цей елемент до розкодованого повідомлення. Процедура декодування завершена.

Скiнченнi поля,як векторнi пiдпростори над простим пiдполем i як множини коренiв полiномiв x^(p^m)-x=0 $

[відповідальна Журавльова Оксана]

Z(_n) - кільце лишків за модулем n є полем, якщо n - просте число.

|F| < +infinity - скінченне поле.

1 є F э {0,1,2,...,p-1}

1+1+...+1 = 1+1+...+1

n одиничок m одиничок

n < m

1+...+1 = 0

n - m = k одиничок

Наменше k називається характеристикою поля Хі(F) - /* хі - тут кирилічна буква 'х'. */

F э F(_p) = Z(_p)

F - векторний простір над F(_p)

Властивості векторного простору:

введено операції:

1. V x F -> V - множення на скаляр

2. V x V -> V - додавання векторів.

Простір є скінченновимірним, коли в нього скінченний базис.

e1, e2, ..., en є F

a = alpa1*e1 + ... + alpan*en, alpa1,...,alpan є F(_p)

|F| = p^n = q /* p в степені n */

До F(_p) додаємо всі корені рівняння.

Твердження. Корені полінома утворюють поле.

F* - мультиплікативна група поля.

F* = F\{0} - циклічна група.

Група G називається циклічною, якщо

Э a є G : G = {a^k | k = 0,+-1,+-2, ...}

x^q-x - поле розкладу полінома збігається з множиною коренів.

F(^+) = {0,1,S,S+1} - адитивна група (S - корінь полінома x^2+x+1)

F* = {1,S,S+1} S^2 = -(S+1) = (S+1)

F(_2)[x] / m(x) F (_2)[x]

всі кратні поліномові m(x) утворюють ідеал кільця

S - корінь m(x)

F(_8) = {a*S^2 + b*s + c | a,b,c є F(_2)}

F(_8) = {0, S, S^2, S^3=S+1, S^4=S^2+S, S^5=S^2+S+1, S^6=S^2+1, S^7=S^3+S=1}

Довести, що мультиплiкативна група скiнченного поля є циклiчною. хз, що тут треба писати :-(

[відповідальна Журавльова Оксана] Циклічні мультиплікативні групи Мультиплікативна група Z(^*)(_n )є циклічною групою тоді і тільки тоді, коли n = 2, n = 4, n = p*m, або n = 2*m для довільного непарного простого p і довільного m > 0. Циклічна група завжди має породжуючий елемент; породжуючий елемент мультиплікативної групи за модулем n називається примітивним коренем з n.

Наприклад, Z(^*)(_9 ) містить 6 елементів {1, 2, 4, 5, 7, 8} і є ізоморфною до циклічної групи С6. Вона генерується або з елементів 2 чи 5, отже 2 і 5 - примітивні корені 9.

[by mr from wikipedia but it is not proof]

Основнi поняття кодування з виправленням помилок. Простiр кодування над скiнченним полем, поняття коду, розмiру коду, швидкостi передачi. $

[відповідальна Журавльова Оксана]

W(_n) - векторний простір розмірності n над полем з двох елементів.

W(_n) = {(*,...,*) /*- n зірочок */ | * є F(_2)} - кодовий простір

Кодові слова - вектори довжини n.

Означення. Кодом C називається довільна підмножина W(_n)

W(_n) = {0,1}^n

Характеристики:

  • Розмір коду - |C| - кількість елементів (кодових слів)
  • Швидкість передачі (information rate) R = (log(2)[|C|])/n

/* В загальному випадку логарифм береться за основою q - у цьому прикладі q=2 */

Ймовiрносна модель передачi iнформацiї з помилками. Метрика Хемiнга(перевiрити виконання аксiом метрики). Принцип максимальної правдоподiбностi та його обгрунтування.

[відповідальний Щепінський Паша]

Ймовiрносна модель передачi iнформацiї з помилками. При передачі інформації часто виникають помилки. Сигнал->encoder->modem->decoder. Вважатимемо, що в канал поступає код. Код – послідовність бітів – (*,*,…*), де *=0,1. *є F(_q) Ймовірнісна модель: ймовірність помилки в кожному символі одна й та ж - Р<<1.Ймовірність помилки в кожному біті не залежить від того, чи були помилки попередньо - схема Бернуллі.

Ймовірність отримати k помилок - С(_n^k)*p^k*(1-p)^(n-k)

Метрика Хемінга. Метрика — функція, яка визначає відстані в метричному просторі.

Є деяка множина Х. Є функція ро:Х*Х->R. При цьому повинні виконуватись три аксіоми:

1) ро(x,y)>=0, при чому ро(x,y)=0 <=> x=y;

2) po(x,y)=po(y,x)

3) нерівність трикутника: для будь-яких x,y,z: po(x,y)<=po(x,z)+po(z,y)

Перевірка.

F(_q)^k={(*,*,...*)|*єF(_q)}, F(_q)^k=F(_q)*F(_q)*...*F(_q)

po(x,y)=SUM(_i)(^n)[x+y] - кількість позицій в яких вектори відрізняються (+ - побітове додавання).

x=(*,*,...,*), y=(*,*,...,*), z=(*,*,...,*).

Аксіома 1 і 2 - очевидно.

Аксіома 3. Якшо * в x,y на однакових позиціях різні, то буде ненульова сума. Тоді * z різна з * x або y. Тому або в po(x,z), або в po(z,y) буде одиничка.

Принцип максимальної правдоподібності. Якщо отримано вектор x, то правильним декодуванням є вектор с*єС, якшо метрика Хемінга po(x,c*)=min(po(x,c)) - мінімум по с.

Мiнiмальна вiдстань коду, зв"язок з кiлькостями помилок, що можна виявити та можна виправити за принципом максимальної правдоподiбностi.

[відповідальний Щепінський Паша]

Мінімальною відстанню коду називається число d*=min d(c_1,c_2), c_1,c_2 є С, с_1!=с_2 ,іншими словами, d* - мінімальна відстань серед усіх відстаней d між будь-якими двома кодовими словами.

r – максимальна кількість помилок, які можна зробити, щоб помилка була виявлена

t – максимальна кількість помилок, що можуть бути виправлені

r,t – універсальні параметри

пов’яжемо d*,r,t:

r=d*-1

t= |_ (d*-1)/2 _|

d*=2t+1

Поняття лiнiйного коду. Вага коду. Поняття породжуючої та перевiрочної матрицi, синдрому помилок. Технiка матричного кодування.

[відповідальний Щепінський Паша]

Код С є W_n називається лінійним, якщо він є векторним підпростором.

(0,0,…,0) – нульовий вектор

Нульовий вектор завжди є словом

Властивість метрики Хеммінга: d(x,y) = d(x+a,y+a) – метрика інваріантна відносно зсуву

Вага кодового слова це відстань між словом і нульовим вектором:

За означенням w(c)=d(0,c)

w - мінімальна вага серед ваг кодових слів:

w=w(c)=min w(c), c є С

зв’язок між d* і w: мінімальна відстань = мінімальна вага

d(x+x,y+x)=d(0,y+x)

Техніка матричного кодування:

С – простір кодових слів.

a_1 !є С, а_1+С={a_1+c | c є С}

a_1 і С не мають спільних елементів

Тепер беремо a_2: a_2 !є С \/ a_1+C

|---------------------------------------------------------|

|-------C-------|----a_1+C------|------a_2+C----|

|---------------------------------------------------------|

|-----a_3+C--|----a_4+C------|------a_5+C----|

|---------------------------------------------------------|

Зрештою так заповнимо весь простір.

Отримані великі клітинки є елементами фактор-простору.

a_i – представники класів еквівалентності.

Переоберемо представників: оберемо ті, в яких найменша вага, тобто кількість одиничок – це будуть лідери класів

|---------------------------------------------------------

|----(0,0,…)----|------с_1------|------с_2------|---і тд

|---------------------------------------------------------

|-----еr_1--------|--еr_1+с_1--|--еr_1+с_2--|---і тд

|---------------------------------------------------------

|-----еr_2--------|--еr_2+с_1-|--еr_2+с_2--|---і тд

|---------------------------------------------------------

|------і тд-------|------і тд-------|------ і тд------|


По рядках – всі кодові слова, у першому стовпчику – лідери класів

Декодувальник:

1. Шукає слово у табличці

2. еr – помилки, відкидаємо еr і отримуємо слово


Векторний простір можна задати:

1. Через базис або породжуючи множину

2. Через розв’язки системи однорідних лінійних рівнянь


Кодувальник:

Будує кодуючу матрицю E = [ [e_1] [e_2] [e_3]….[e_k]]


е_1,е_2,е_3 …e_k – базисні кодові слова

повідомлення m = (m_1,m_2,….,m_k) кодується множенням на кодуючу матрицю: m -> m*E, на виході маємо вектор довжини m


Інший спосіб – через систему однорідних лінійних рівнянь

Будується перевірочна матриця V: вектор x є С <-> x*V = 0

Якщо отримали y=x*V, y!=0, то y називається синдромом.

Двiйковi коди Хемiнга. Кодування, декодування, властивостi. $

[відповідальний Жебряков Сашко] Коди Хемінга

Дано: (n,k,d), n-довжина коду, к - довжина повідомлення, d-кодова відстань в повідомленні.

-->Кодова відстань дорівнює мінімальній відстані Хемінга між різними кодовими словами. -->Хемінгова відстань d(x,y) між векторами x,y- це число різних координат 2-ох векторів.

! Код Хемінга- це такий код, який виправляє тільки 1-ну помилку.

Для коду Хемінга задається (n,k,d)=(2^r,2^r-r-1,3).

Задається перевірочна матриця V розмірності [n,n-k], де кожний рядок задається двійковим розкладом свого номеру.

Припускаємо,що сталась помилка в якійсь позиції.Нехай повідомлення:u=(u1,u2...,uk). Задаємо кодове слово c=(c1,...,cn),яке складається з символів самого повідомлення (інформаційних символів) і контрольних символів,які вибираються таким чином,щоб кодові слова задовільняли рівняння: c*V=0. Контрольні символи у вихідному коді займають позиції, що є степенями 2(двійки).

Декодування: Перемножується закодоване повідомлення x (в якому міститься одна помилка)на перевірочну матрицю V і ми в результаті отримуємо двійкове представлення позиції у якій була зроблена помилка. Оскільки ми працюємо в полі F(_2), то достатньо хибне значення змінити на протилежне: 

    x*V =position. x[position]:=x[position]+1.

Побудова узагальнених кодiв Хемiнга. $

[відповідальний Жебряков Сашко] Побудова узагальнених кодів Хемінга

Дано: (n,k,d), n-довжина коду, к - довжина повідомлення, d-кодова відстань в повідомленні.

-->Кодова відстань дорівнює мінімальній відстані Хемінга між різними кодовими словами. -->Хемінгова відстань d(x,y) між векторами x,y- це число різних координат 2-ох векторів.

Працюємо у довільному полі F(_q), де q>2.

m- к-сть контрольних символів(відповідно, к-сть стовпчиків).

V- перeвірочна матриця (n x m).

У перевірочній матриці не повинно бути пропорційних рядків. Тому ми не можемо брати усі ненульові вектори довжини m. Вирішення: брати усі ненульові вектори, перша ненульова координата якого дорівнює 1. Кількість векторів з такою властивістю довжини m над полем F(_q) дорівнює (q^m-1)/(q-1).

Отже, маємо (q^m-1)/(q-1) рядочків у перевірочній матриці V. Звідси маємо, що довжина q-значного коду: n=(q^m-1)/(q-1).


Припускаємо,що сталась помилка в якійсь позиції. Задамо код с=(x1,x2,...,xk), код складається з символів самого повідомлення та контрольних символів.Памятаємо, що контрольні символи обираються таким чином, щоб задовільнялось рівняння с*V=0.

Робимо помилку: с+E. При множенні (с+E)*V отримуємо двійкове представлення позиції у якій була зроблена помилка.

Нерiвнiсть Хемiнга. Досконалi коди.Коди Хемiнга, як приклади досконалих кодiв. $

[відповідальний Жебряков Сашко] Нерівність Хемінга

Якщо код дозволяє виправляти r помилок,то розмір коду задовільняє нерівність Хемінга: --> Нерівність(границя) Хемінга: |c|<=2^n/|B(c,r)|, де B(c,r)-куля, де: с- двійковий код, n- довжина двійкового коду с , d-кодова відстань.

r=((d-1)/2), де r- радіус кулі описаної навколо кодового слова. Оскільки кодова відстань дорівнює d, то кулі,описані навколо кодових слів х, не перетинаються.

--> Код наз. досконалим, якщо |c|=2^n/|B(c,r)|

-->Код Хемінга є досконалим кодом, що виправляє одну помилку Доведення(від Соловьйової): За побудовою потужність коду Хемінга дорівнює: |H|=2^(n-m)=(2^n)/n+1 , де m=log(_2)[n+1]. Відповідно код Хеммінга досягає границі Хеммінга і тому є досконалим.

Доведення(від Боднарчука): для кодів Хемінга r=1. Всі кулі однакові.Тому к-сть ел-тів у кулі: |B(c,r)|=1+(2^r-1)=2^r. n=2^(2^r-r-1). |c|=2^(2^r-r-1). Тепер, видно,що виконується нерівність: 2^(2^r-r-1)*2^r=2^(2^r-1).

Коди Ріда-Маллера

[відповідальний Сосо Івоса] Використовували при передачі інфо Марсу.Було дуже багато помилок.Використовували rm(5,1)Припустимо є векторний простір V_d={(x_1,x_2...x_d)|x_i є F_2}

Розглянемо множину функціоналів f:V_d -> F_2 (це просто булеві функції) V(к-сть булевих функцій)=(V_d)^*=2^2^d |c|=2^2^d

Якщо є множина MєV_d, то їй можна поставити у відповідь індикаторну функцію X_m[(x)]={1,xєM;0,xнеєM} M_f={uєV_d|f(u)=1} <- f

V(з хвилястою рисочкою зверху) значно більше за V_d

F(V_d,F_2)=V(з хвилястою рисочкою зверху)

c входить в V(зверху хвиляста рисочка)

Розглянемо гіперплощини P_1,P_2..P_i P_i={u|[u]_i=o}

Будуємо кодові слова. Перше кодове слово (1,1,..1)

Будуємо матрицю i.Як кодові слова виписуємо X гіперплощин X_i=X_P_i -> великі матричні дужки і в них всередині пишемо: "1 або 0 залежно від x".В матриці d рядків

Потім вводимо операцію на векторах: покоординатний добуток (x_1,x_2...x_m)/\(y_1,y_2...y_m)=(x_1y_1,x_2y_2...)

Далі X_i /\ X_j (i<j)-характеристичні функції перетинів цих двох гіперплощин P_i/\P_j

Далі розглядаємо X_i /\ X_j/\ X_k

Зупиняється це все на якомусь кроці r

RM(d,r)

Двійковий код Ріда-Малера RM(d,r) порядку r, 0<=r<=m, -це сукупність векторів довжини 2^m, що відповідають поліномам від m змінних степеня не більше r.

Теорема. Мінімальна відстань коду RM(d,r)порядку r,0<=r<=m, рівна d=2^(m-r)

Два коди наз. еквівалентними, ЯКЩО вони однакові за своїми метричними співвідношеннями

/*АЛГОРИТМ РОБОТИ дивися в 24.*/

24. Алгоритм Ріда декодування на прикладі RM(5,1) $

[відповідальний RST]

Коди ріда-маллера (Reed–Muller code) – це коди сім’ї лінійних виправляючих кодів, еквівалентні кодам Хеммінга.

Позначення: RM(D,R), де:

R – ранг коду. D=параметр, пов’язаний з довжиною _коду_ -- n = 2^D.

При частковому випадку RM(D,0) коди ріда-маллера перетворюються в повторювані коди (один символ кодується повторюванням його ж певну кількість разів).

Ранг матриці – це показник розширення кодуючої матриці.

При R=0, кодуюча матриця – вектор з 2^D

{1,1,1…. 1}=E_0

При R=1, кодуюча матриця включає E_0, але розширюється на:

|0 0 0 0…| значення кожного _стовбчика_ матриці – це порядковий номер стовбчика

|… . … | поданий у двійковому форматі, починаючи з 0.

|0 0 1 1…|

|0 1 0 1…|


Ширина матриці – довжина коду – 2^D. Висота – log2(2^D)=D.

Тому довжина повідомлення при використанні схеми RM(D,1) =D+1 (E_0+E_1).

/*при збільшенні R, збільшується довжина повідомлення, яке може бути закодоване тою самою кількістю бітів коду. Але при збільшенні R відповідно падає кількість помилок, які можна відновити для надлишкових бітів (тих шо при меншому R раніше не можна було). А оскільки кількість помилок шо може виправити алгоритм – це мінімум з допустимих помилок, то зменшується і загальна надійність коду. Але це так, для розуміння. ;- )*/

/*R=2, -- це побітовий XOR (здається) рядків R_1. Але нам це вже не треба.*/

Отже, переходячи до випадку RM(5,1):

Є кодуюча матриця:

|1 1 1 1 1…1| ширина – n=2^D – довжина коду.

|0 0 0 0 0…1| висота – D+1 (бо ранг 1 = E_0 і E_1) – довжина повідомлення.

|0 0 0 0 0…1|

|0 0 0 0 1…1|

|0 0 1 1 0…1|

|0 1 0 1 0…1|


Для закодування повідомлення (m1,m2,m3,m4,m5,m6) треба вектор повідомлення помножити на матрицю кодування (за правилом множення ветора на матрицю, вийде вектор, довжини n.

/*(пишу в стовбчик, бо так видніше – “нє вєрь глазам своїм” – то великий довгий рядок.)*/ 

|1*m1+0*m2+0*m3+0*m4+0*m5+1*m6,
 1*m1+0*m2+0*m3+0*m4+1*m5+0*m6,
 1*m1+0*m2+0*m3+0*m4+1*m5+1*m6,
…
 1*m1+1*m2+1*m3+1*m4+1*m5+1*m6|

А отже, код буде складатися з таких сум: 

C :=
|m1,
 m1+m6,
 m1+m5,
 m1+m5+m6
 m1+m4
…
 m1+m2+m3+m4+m5+m6|

це і є закінчення алгоритму закодовування.

Допустимість помилок – при R=0 , кількість помилок, що можна виявити – ((2^D)-1). Виправити – (2^D-1)/2, заокруглене до низу. Для R=1. виявити -- (2^D-1)/2 (заокругл. До низу) виправити -- (2^D-1)/4 – (заокруглене до низу) Тобто, для RM(5,1) = D=5. R=1: виявити – 15, виправити – 7.


РОЗКОДОВУВАННЯ:

/*По-суті, просто логічні дії по розв’язанню системи лінійних рівнянь…*/

Відновлення оригінального повідомлення починається з кінця.

Намагаємося відновити m6:

Зі схеми закодовування видно, що C[2]-C[1] /*(відняти перший і другий стовбчик) по-суті, в бінарній арифметиці додавання = віднімання, тому ми будемо додавати, але для загальності і для розуміння можемо казати шось про віднімання.*/

Так от, видно, що С[2]-C[1]=m6. (m1+m6)- (m1)

Також m6 дорівнюють вінміння і інших сусідніх рядків:

m6= {C[2]-C[1], C[4]-C[3], C[6]-C[5], C[8]-C[7]….} /*16 штук.*/

яких значень буде більше («1» чи «0») таке і виберемо на значення m6.

Аналогічно m5: C[3]-C[1]=(m1+m5)-(m1);

m5={C[3]-C[1], C[4]-C[2], !!!C[7]-C[5],C[8]-C[6]… } /*cтсільки ж штук.*/

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


Деяка складність є в m1:

Оскільки m1 є у всіх рядках, то неможливо знайти таку суму, щоб отримати тільки значення m1. тому тут застосовується таких алгоритм:

Оскільки на момент обчислення m1 ми вже знаємо значення всіх інших бітів (m2…m6) то відновити m1 ми можемо, просто віднімаючи від кожного елемента коду значення всіх інших бітів, які в цьому елементі представлені у вигляді суми.

/*тобто, для С[1] – це і є m1. дляC[2] – треба відняти m6. для C[3] – віднімаємо m5, для C[4] – віднімаємо m5 I m6.*/

Отже, в результаті ми отримаємо вектор з 32 значень, з яких вибираємо значення для m1 за таким же принципом як і для всіх попередніх бітів.

/*всьо. Хотів, шоб всі нарешті догнали. ;-) та, і ше одне, трохи не по темі -- вікіпедіа каже, шо нас дуже напарили! ;-) коди є RM(r,m), а тому вони не 5,1 а 1,5... і матриця будується навпаки.. починаючи з всіх одиничок аж до тільки 1 одинички в першому рядочку. [[1]]

  • /

=== Циклічні коди.Поліноміальна реалізація. Циклічний код, як ідеал фактор-кільця поліномів. Існування породжуючого поліному, техніка поліноміального кодування. === /* $ */ [відповідальний Антон Чорний]


Циклічні коди

Лінійний код довжини n називається циклічним, якщо для будь-якого кодового слова (x_1,x_2,..,x_n) слово (x_2, ... , x_n, x_1) також є кодовим. Алгебраїчний опис циклічних кодів: Позначимо через F просте кінцеве поле GF(p), де p - просте число. Нагадаємо, що F[x] -- кільце всіх многочленів від змінної x із коефіціентами з поля F. Воно асоціативно, комутативно і має одиницю. В кільці F[x] розглянемо фактор-множину F[x]/(х^n-1), що складається з класів лишків кільця F[x] за модулем многочлена x^n-1. Множина F[x]/(x^n-1) є замкнутою відносно операцій додавання та множення, і, відповідно, є кільцем. Відмитимо, що множина F[x]/(x^n-1) не є полем, оскільки многочлен x^n-1 є зведеним.

Всі многочлени степені не більше n-1 потрапляють у різноманітні класи лишків і їх можна вибрати у якості представників цих класів. Кільце класів лишків F[x]/(x^n-1) ізоморфне n-мірному векторному простору над F:

c(x)=c_*0+c_1*x+c_2*x^2+...+c_(n-1)*x^(n-1) <--> c=(c_0,c_1,c_2, ... , c_(n-1))

Надалі ми не будемо розрізняти вектори і многочлени ступені менше n, але з контексту завжди буде зрозуміло йде мова про вектори чи про многочлени.

Циклічний код, як ідеал фактор-кільця поліномів

Ідеалом І кільця F[x]/(x^n-1) називається такий лінійний підпростір, що для будь-якийх многочленів r(x), що належать F[x]/(x^n-1) і с(х) належить I, многочлен r(x)*c(x) належить I.

Підпростір кільця F[x]/(x^n-1) є цикічним кодом тоді і лише тоді, коли він утворює ідеал. В кільці F[x]/(x^n-1) множення многочлена на х відповідає циклічному здвигу вектора у просторі F^n. Дійсно, x*c(x)=x*(c_0 + c_1*x + c_2*x^2 + ... + c_(n-1)x^(n-1)) = c_(n-1) + c_0*x + c_1*x^2 + ... + c_(n-2)*x^(n-1).

Таким чином вектор (с_0,c_1, ..., c_(n-1)) переходить у вектор (с_(n-1), c_0, c_1, ..., c_(n-2)), тобто ми отримуємо циклічний зсув у F^n.

Достатність. Нехай С -- циклічний код. Тоді для будь-якого кодового вектора c, його циклічний зсув належить С. Іншими словами, для будь-якого кодового многочлена с(х) добуток x*c(x) належить коду. Звідси випливає, що у зв'язку з лінійністю циклічного коду, що f(x)*c(x) є кодовим многочленом, де f(x) -- довільний многочлен із F[x]/(x^n-1). Відповідно, C -- ідеал в кільці F[x]/(x^n-1).

Необхідність. Нехай підпростір D кільця F[x]/(x^n-1) утворює ідеал. Розглянемо многочлен c(x) належить D. За визначенням ідеала, многочлен f(x)*c(x) належить D для будь-якого многочлна f(x) належить F[x]/(x^n-1). Тоді x*c(x) належить D. Крім того, сума будь-яких двох елементів із D також лежить у D і, відповідно, D -- циклічний код.

Інколи користуються наступним еквівалентним визначенням циклічного коду.

Визначення. Циклічним кодом довжини n називається ідеал кільця F[x]/(x^n-1)

Існування породжуючого поліному.

Виберемо в циклічному коді C ненульвоий многочлен найменшого ступеню і позначимо його ступінь через r. Помножимо многочлена на підходящий елемент поля F, щоб він став нормованим (чи зведеним), тобто, щоб коефіціент старшої степені многочлена дорівнював 1. У зв'язку з лінійністю коду C, отриманий многочлен також належить С. Позначимо його через g(x).

Циклічний код має єдиний ненульовий нормований многочлен найменшого ступеню. Доведення. Нехай існує два нормованих многочлена f(x) та g(x) найменшої ступені r. Тоді многочлен f(x)-g(x), що належить коду, має степінь менше r, що призводить до протиріччя.

Нормований ненульовий многочлен найменшого степені, що належить циклічному коду, називається породжуючим многочленом коду і позначається через g(x)

Циклічний код складається із всіх многочленів вигляду f(x)*g(x), де g(x) -- породжуючий многочлен кода ступеня r, степінь f(x) менша за (n-r).

Доведення. Згідно з тим, що циклічний код складає ідеал в кільці F[x]/(x^n-1), добуток будь-якого многочлена f(x) з F[x]/(x^n-1) на g(x) належить коду. Тоді добуток g(x) на всі многочлени ступені, меншої за n-r належать С.

Покажемо, що будь-який кодовий многочлен можна представити у вигляді такого добутку. Нехай c(x) -- кодовий. Розділимо його в кільці F[x]/(x^n-1) із залишком на многочлен g(x). Маємо c(x)=q(x)*g(x)+sigma(x), де ступінь s(x) менша за степінь g(x), а степінь q(x) менша n-r. Многочлен s(x)=c(x)-q(x)*g(x) є кодовим, оскільки доданки у правій частині належать коду C і він є лінійним. Але ступінь многочлена s(x) менша ступені g(x) -- найменшого степіня ненульового многочлена в С. Звідси s(x)=0 і c(x)=q(x)g(x), тобто с(x) має в кільці F[x]/(x^n-1) шукане представлення.


Кодування циклічних кодів.

Визначення. Код довжини n розмірності k називається систематичним, якщо після викреслення деяких (n-k) стовбців із його кодової матриці залишаються в точності всі різні вектори довжини k. Будь-який циклічний код еквівалентний систематичному коду.

Для циклічного коду існує простий спосіб знаходження породжуючої матриці в канонічному вигляді. При цьому ми отримуємо породжуючу матрицю того ж коду, а не еквівалентного. Це важливо, оскільки перестановко координат може порушити властивість циклічності. Далі наведені декільки спільних принципів кодування циклічних кодів.

Перший систематичний кодер.

Нехай циклічний код С довжини n має породжуючий многочлен g(x) ступеню r. Тоді розмірність k коду C дорівнює n-r. Для побудови породжуючої матириці G виконаємо ділення з залишком многочленів. x^(n-1),x^(n-2),...,x^(n-k) на g(x). Маємо: x^(n-1)=g(x)*a_1(x)+r_1(x), x^(n-2)=g(x)*a_2(x)+r_2(x), ... x^(n-k)=g(x)*a_k(x)+r_k(x).

Оскільки кожний многочлен x^(n-i) - r_i(x) для i=1,2,..,k ділиться на g(x), то він є кодовим. Степінь залишку r_i(x) не перевищує r-1. Нехай многочлен має вигляд -r_i(x)=lambda_(i,r-1)*x^(r-1)+lambda_(i,r-2)*x^(r-2)+...+lambda_(i,0)

Циклічні коди.Поліноміальна реалізація. Циклічний код, як ідеал фактор-кільця поліномів. Існування породжуючого поліному, техніка поліноміального кодування.

[відповідальний Антон Чорний] finished $


Циклічні коди

Лінійний код довжини n називається циклічним, якщо для будь-якого кодового слова (x_1,x_2,..,x_n) слово (x_2, ... , x_n, x_1) також є кодовим. Алгебраїчний опис циклічних кодів: Позначимо через F просте кінцеве поле GF(p), де p - просте число. Нагадаємо, що F[x] -- кільце всіх многочленів від змінної x із коефіціентами з поля F. Воно асоціативно, комутативно і має одиницю. В кільці F[x] розглянемо фактор-множину F[x]/(х^n-1), що складається з класів лишків кільця F[x] за модулем многочлена x^n-1. Множина F[x]/(x^n-1) є замкнутою відносно операцій додавання та множення, і, відповідно, є кільцем. Відмитимо, що множина F[x]/(x^n-1) не є полем, оскільки многочлен x^n-1 є зведеним.

Всі многочлени степені не більше n-1 потрапляють у різноманітні класи лишків і їх можна вибрати у якості представників цих класів. Кільце класів лишків F[x]/(x^n-1) ізоморфне n-мірному векторному простору над F:

c(x)=c_*0+c_1*x+c_2*x^2+...+c_(n-1)*x^(n-1) <--> c=(c_0,c_1,c_2, ... , c_(n-1))

Надалі ми не будемо розрізняти вектори і многочлени ступені менше n, але з контексту завжди буде зрозуміло йде мова про вектори чи про многочлени.

Циклічний код, як ідеал фактор-кільця поліномів

Ідеалом І кільця F[x]/(x^n-1) називається такий лінійний підпростір, що для будь-якийх многочленів r(x), що належать F[x]/(x^n-1) і с(х) належить I, многочлен r(x)*c(x) належить I.

Підпростір кільця F[x]/(x^n-1) є цикічним кодом тоді і лише тоді, коли він утворює ідеал. В кільці F[x]/(x^n-1) множення многочлена на х відповідає циклічному здвигу вектора у просторі F^n. Дійсно, x*c(x)=x*(c_0 + c_1*x + c_2*x^2 + ... + c_(n-1)x^(n-1)) = c_(n-1) + c_0*x + c_1*x^2 + ... + c_(n-2)*x^(n-1).

Таким чином вектор (с_0,c_1, ..., c_(n-1)) переходить у вектор (с_(n-1), c_0, c_1, ..., c_(n-2)), тобто ми отримуємо циклічний зсув у F^n.

Достатність. Нехай С -- циклічний код. Тоді для будь-якого кодового вектора c, його циклічний зсув належить С. Іншими словами, для будь-якого кодового многочлена с(х) добуток x*c(x) належить коду. Звідси випливає, що у зв'язку з лінійністю циклічного коду, що f(x)*c(x) є кодовим многочленом, де f(x) -- довільний многочлен із F[x]/(x^n-1). Відповідно, C -- ідеал в кільці F[x]/(x^n-1).

Необхідність. Нехай підпростір D кільця F[x]/(x^n-1) утворює ідеал. Розглянемо многочлен c(x) належить D. За визначенням ідеала, многочлен f(x)*c(x) належить D для будь-якого многочлна f(x) належить F[x]/(x^n-1). Тоді x*c(x) належить D. Крім того, сума будь-яких двох елементів із D також лежить у D і, відповідно, D -- циклічний код.

Інколи користуються наступним еквівалентним визначенням циклічного коду.

Визначення. Циклічним кодом довжини n називається ідеал кільця F[x]/(x^n-1)

Існування породжуючого поліному.

Виберемо в циклічному коді C ненульвоий многочлен найменшого ступеню і позначимо його ступінь через r. Помножимо многочлена на підходящий елемент поля F, щоб він став нормованим (чи зведеним), тобто, щоб коефіціент старшої степені многочлена дорівнював 1. У зв'язку з лінійністю коду C, отриманий многочлен також належить С. Позначимо його через g(x).

Циклічний код має єдиний ненульовий нормований многочлен найменшого ступеню. Доведення. Нехай існує два нормованих многочлена f(x) та g(x) найменшої ступені r. Тоді многочлен f(x)-g(x), що належить коду, має степінь менше r, що призводить до протиріччя.

Нормований ненульовий многочлен найменшого степені, що належить циклічному коду, називається породжуючим многочленом коду і позначається через g(x)

Циклічний код складається із всіх многочленів вигляду f(x)*g(x), де g(x) -- породжуючий многочлен кода ступеня r, степінь f(x) менша за (n-r).

Доведення. Згідно з тим, що циклічний код складає ідеал в кільці F[x]/(x^n-1), добуток будь-якого многочлена f(x) з F[x]/(x^n-1) на g(x) належить коду. Тоді добуток g(x) на всі многочлени ступені, меншої за n-r належать С.

Покажемо, що будь-який кодовий многочлен можна представити у вигляді такого добутку. Нехай c(x) -- кодовий. Розділимо його в кільці F[x]/(x^n-1) із залишком на многочлен g(x). Маємо c(x)=q(x)*g(x)+sigma(x), де ступінь s(x) менша за степінь g(x), а степінь q(x) менша n-r. Многочлен s(x)=c(x)-q(x)*g(x) є кодовим, оскільки доданки у правій частині належать коду C і він є лінійним. Але ступінь многочлена s(x) менша ступені g(x) -- найменшого степіня ненульового многочлена в С. Звідси s(x)=0 і c(x)=q(x)g(x), тобто с(x) має в кільці F[x]/(x^n-1) шукане представлення.


Кодування циклічних кодів.

Визначення. Код довжини n розмірності k називається систематичним, якщо після викреслення деяких (n-k) стовбців із його кодової матриці залишаються в точності всі різні вектори довжини k. Будь-який циклічний код еквівалентний систематичному коду.

Для циклічного коду існує простий спосіб знаходження породжуючої матриці в канонічному вигляді. При цьому ми отримуємо породжуючу матрицю того ж коду, а не еквівалентного. Це важливо, оскільки перестановко координат може порушити властивість циклічності. Далі наведені декільки спільних принципів кодування циклічних кодів.

Перший систематичний кодер.

Нехай циклічний код С довжини n має породжуючий многочлен g(x) ступеню r. Тоді розмірність k коду C дорівнює n-r. Для побудови породжуючої матириці G виконаємо ділення з залишком многочленів. x^(n-1),x^(n-2),...,x^(n-k) на g(x). Маємо: x^(n-1)=g(x)*a_1(x)+r_1(x), x^(n-2)=g(x)*a_2(x)+r_2(x), ... x^(n-k)=g(x)*a_k(x)+r_k(x).

Оскільки кожний многочлен x^(n-i) - r_i(x) для i=1,2,..,k ділиться на g(x), то він є кодовим. Степінь залишку r_i(x) не перевищує r-1. Нехай многочлен має вигляд -r_i(x)=lambda_(i,r-1)*x^(r-1)+lambda_(i,r-2)*x^(r-2)+...+lambda_(i,0)


Визначення циклічного коду через перевiрочнi множини. Побудова перевірочної матриці по перевiрочнiй множині. Перехід вiд породжуючого поліному до перевірочної множини i навпаки. ???

[відповідальний Назарук Алекс] Породжуючий многочлен g(x) ділить многочлен (x^n)-1

Поліном, такий що g(x)*h(x)=(x^n)-1 називається перевірочним поліномом циклічного коду. Його степінь k=n-r

Тврдження: Для довільного кодового слова c(x)циклічного коду з перевірочним поліномом h(x справедливим є c(x)*h(x)=0 по модулю полінома (x^n)-1.

Доведення: Відповідно до теореми(циклічний код складається із всіх многочленів виду f(x)*g(x) де g(x)-породж. многочлен коду степеня r степінь f(x) менша (n-r)), будь-який кодовий многочлен c(x) циклічного коду має вигляд g(x)*q(x) і, відповідно, в фактор-кільці F[x]/(x^n-1) справедлива рівність с(x)*h(x)=q(x)*g(x)*h(x)=q(x)(x^n-1)=0

Теорема: Перевірочна матриця циклічного коду довжини n з перевірочним поліномом h(x)=h_0+h_1*x+...+h_k*x^k має вигляд:

H=([0 ... ... 0 h_k ... h_1 ... h_0][0 ... 0 h_k ... h_1 h_0 0] ... [0 h_k ... h_1 h_0 0 ... 0][h_k ... h_1 h_0 0 ... ... 0])

Доведення: Згідно з твердженням, для будь-якого кодового слова с(x) циклічного коду виконується c(x)*h(x)=0

Тоді с(x)*h(x)=(СУМА[i=0..n-1](c_i*x^i))*(СУМА[j=0..n-1](h_j*x^j))=0, де с(x)=СУМА[i=0..n-1](c_i*x^i). Коефіцієнт при x^j, j=1,0, ... , n-1, в цьому добутку рівний СУМА[i=0..n-1](c_i*h_(j-i))=0. Індекси беруться по модулю n. Цы рівності задають перевірочні рівняння, які повинен задовільняти код.

Розглянемо матрицю.

H=([0 ... ... 0 h_k ... h_1 ... h_0][0 ... 0 h_k ... h_1 h_0 0] ... [0 h_k ... h_1 h_0 0 ... 0][h_k ... h_1 h_0 0 ... ...0])~([vec(h(x))][vec(x*h(x))][vec(x^2*h(x))]...[vec(x^(n-k-1)*h(x))]))

якщо вектор c=(c_0,c_1,c_2,...c_n-1) кодовий, то H*с^T=0 (1)

Так як deg(h(x))=k=n-deg(g(x)) є розмірністю коду, та рядки H лінійно незалежні, то умова (1) є також достатньою для того, щоб вектор c належав коду.

Таким чином, H - перевірочна матриця циклічного коду з перевірочним многочленом h(x).

БЧХ коди,яккласциклiчнихкодiв.ДекодуванняБЧХкодiвзаалгоритмом Петерсона. ???

[відповідальний Назарук Алекс]

Це окремий випадок ЦК

F_2 c F - розшир

ЦК називаються БЧХ-кодом, якщо його перевірочна множина V має вигляд:

v={alfa,alfa^2,alfa^(delta-1)},

де alfa належить F delta=2*t+1

delta - конструктивна відстань

Теорема. Мінімальна відстань БЧХ-коду завжди перевищує конструктивну відстань

alfa_min>=delta

Декодер Петерсона

t-найбільше ціле 2t+1<=delta

c(x) - код помилки

e(x) - поліном помилки

r(x)=c(x)+e(x)

Вваж, що deg(c(x))=n-1, тобто довжина коду = n

Множина epsilon - номери позицій, в яких допускали помилки.

epsilon={0<=j<=n-1:e_j!=0}

c_j - коеф при x^j

Локатор помилки

delta(x)=П[j нал epsilon](1-(alfa^j)*x) Знаючи r(x), ми відновимо epsilon(де були помилки)

1/alfa^0, 1/alfa^1, 1/alfa^2,..., 1/alfa^(n-1) - послідовно їх підставляємо.

Колокатор помилок.

w(x)=СУМА[i=0..n-1](e_i*alfa^i*П[j нал epsilon,j!=i](1-(alfa^j)x))=СУМА[i=0..n-1](e_i*alfa^i*sigma(x)/(1-(alfa^i)x))

Степінь локатора помилок: не більше ніж t

Степінь колокатора помилок: не більше t-1

deg sigma(x)<=t

deg omega(x)<=t-1

Властивості

1.omega(x)/sigma(x)---SUM[m=0..2t-1]((x^m)e(alfa^(m+1))) по модулю x^2t

2.e(alfa^m)=r(alfa^m) 1<=m<=2t

3.omega(x)/sigma(x)---SUM[m=0..2t-1]((x^m)r(alfa^(m+1)))

4.omega(x)---SUM[m=0..2t-1]((x^m)r(alfa^(m+1))sigma(x))

5.omega_j=SUM[u_v=j]((r(alfa^(u+1))sigma_v),де 0<=j<=2t-1

6.0=SUM[u_v=j]((r(alfa^(u+1))sigma_v),де t<=j<=2t-1

Коректнiсть алгоритму Петерсона - iснування та єдинiсть розв'язкiв двох систем лiнiйних рiвнянь, що мають бути розв'язанi за алгоритмом. ???

[відповідальний Назарук Алекс] Отримуємо таку систему:

j=1,2,...,v(ню здається)

{-S_j+v=sigma_1*S_j+v-1+sigma_2*S_j+v-2+ ... + sigma_v*S_j

Перепишемо у матричному вигляді:

  • M=([S_1 S_2 ... S_v][S_2 S_3 ... S_v+1] ... [S_v S_v+1 ... S_2v-1])*
  • ([sigma_v][sigma_v-1]...[sigma_1])=([-S_v+1][-S_v+2]...[-S_2v])

Треба визначити, має чи не має система розвязки

Визначник Вандермонда: |[1 1 1 ... 1][a_1 a_2 a_3 ... a_m][(a_1)^2 (a_2)^2 (a_3)^2 ... (a_m)^2]...[(a_1)^n+1 (a_2)^n+1 (a_3)^n+1 ... (a_m)^n+1]|=П[i<j]

Розглянемо матрицю Вандермонда розмірності М(мю) А=([1 1 ... 1 ][x_1 x_2 ... x_М][(x_1)^2 (x_2)^2 ... (x_М)^2]...[(x_1)^М-1 (x_2)^М-1 ... (x_М)^М-1])

x_M def(=)0

Теорема: Якщо M=V(ню), то матриця * не вироджена

Тоді система рівняннь має єдиний розв-к

Якщо M>V, то матриця є виродженою.

Тоді треба покласти v=t-1, знову перевіряємо і тд... v, що ми його отримали - реальна кількість помилок

Введемо матрицю В (діагон):

B=([y_1*x_1 0 0 ... 0][0 y_1*x_1 0 ... 0]...[0 0 0 ... y_v*x_v])

безпосереднім обчисленням можна показати, що A*B*(A^T)_ij=(СУМА[l-1...M](y_e*(x_e)^(i+j-1))_ij)=матр. синдромів(*)=М

Довести, що мінімальна выдстань БЧХ коду не менша за конструктивну. Пояснити чому вона може перевищувати конструктивну.

Мінімальна відстань d BCH не менше ніж конструктивна відстань delta d>=delta
Доведення
Декодер дозволяє виправити не більше t помилок, то мін відстань d>=2*t+1, а це й є конструктивна відстань за означенням.
[відповідальний Роман Буняк. Величезне дякую Валерії Наумовій за написання цього питання;)]

Довести нерівність Сінгелтона. Поняття коду з максимально досяжною мінімальною відстанню.

(n,k,d)(_q) - лінійні коди, де
n - розмірність простору кодування;
k - розмірність кодів, як векторного підпростору;
d - мінімальна відстань коду;
q - число, що визначає поле кодування F(_q);

Нерівність Сінглтона виконується для лінійних кодів і визначається як:
d<=n-k+1

Доведення.
Якщо m - повідомлення і E - кодуюча матриця, то довільний код с будується так:
с = m*E, отже k = rank E;
Зберемо матрицю з усіх можливих кодів,де m - таке повідомлення, де всі елементи 0, а один елемент 1. Дана матриця обов'язково міститиме деякий ненульовий мінор(M) порядку k.(Мінором порядку k матриці А називається визначник матриці, складеної з елементів, що розташовані на перетині деяких вибраних k рядків та k стовпчиків). Перемістимо цей мінор в ліву частину матриці(шляхом перестановки стовпчиків). Отримаємо: [[M(_1) ...][M(_2)...][...][M(_k)]]При цьому код залишиться еквівалентним початковому. Далі зводимо матрицю до такого вигляду, коли мінор зведеться до одиничної матриці, а вправій частині отримаємо довільні числа. Оскільки мінор був порядку k, то кількість чисел в правій частині матриці в кожному рядочку буде n-k. Розглянемо найгірший випадок, коли усі ці n-k чисел ненульові. Тоді максимальна кількість ненульових елементів в рядку дорівнює - n-k+1 (одиниця з одиничної матриці).
Отже, d <=n-k+1.
Доведено.

Кодом з максимально досяжною мінімальною відстанню називається код, для якого виконується рівність: d=n-k+1.
[відповідальний Роман Буняк]

Коди Ріда-Соломона, як коди з максимально досяжною мінімальною відстанню.

(n,\!k,\!d)_{q} - лінійні коди, де

n - розмірність простору кодування, причому n = q-1
k - розмірність кодів, як векторного підпростору
d - мінімальна відстань коду
q - число, що визначає поле кодування Fq


c(x) - код

m(x) - повідомлення

δ - конструктивна відстань для БЧХ кодів

Коди Ріда - Соломона це окремий випадок БЧХ кодів.

F_q = \tilde{F_q}, тобто поле локатора помилок і поле кодування збігаються.

Перевірочна множина має вигляд V = \left \{\alpha, \alpha^2,\cdots \alpha^{\delta-1} \right \}. Далі для кожного елемента множини α знайдемо поліном мінімального степеня, який має коренем α. Оскільки поля збігаються:

  • \alpha \to (x - \alpha)
  • \alpha^2 \to (x - \alpha^2)
  • \cdots
  • \alpha^{\delta-1} \to (x - \alpha^{\delta-1})

Тоді породжуючий поліномом буде g(x) = (x − α) * (x − α2) * ... * (x − αδ − 1)

У даних кодів deg g(x) найменший з усіх можливих БЧХ кодів.

Враховуючи c(x) = m(x) * g(x), степені поліномів:

deg(c(x)) \le n - 1 \le q - 2 (віднімаємо одиницю, бо вільний член не треба враховувати при підрахунку степеня полінома)
deg(g(x)) = δ − 1
deg(m(x)) \le q - 2 - (\delta - 1) = q - \delta - 1

Лема. Коди Ріда-Соломона це коди з максимально досяжною мінімальною відстанню.

Доведення.

За означенням коди з максимально досяжною мінімальною відстанню це коди для яких виконується рівність Сінглтона d \le n-k+1.

Знайдемо розмірність простору поліномів m(x):

k = q − δ − 1 + 1 = q − δ

Підставимо в нерівність Сінглтона:

d \le q - 1 - q + \delta + 1 = \delta

А за основною властивістю БЧХ-кодів: d \ge \delta

Тоді d = δ.

Отже, коди Ріда-Соломона - це коди з максимально досяжною мінімальною відстанню.

[відповідальний Роман Буняк]

Базові поняття криптографії: шифр, ключ, шифри заміни та перестановок, блочні та потокові шифри. Шифр Цезаря з точки зору алгебри лишків. Частотний аналіз та ідея К.Гауса, що робить його неможливим

М - простір повідомлень.
m - повідомлення з М
Якщо існує певна процедура E(_k,k')(m), яка ствавить у відповідність кожному повідомленню певний код с, то цей код і називається шифром, або криптотекстом.
k і k'(ключі) - це елементи криптосистеми, які є основою кожної системи і, змінюючи їх, повинно змінюватись все кодування.
k - ключ, за допомогою якого закодовують.
k' - ключ, за допомогою якого розкодовують.
Процедура E(_k,k')(m), разом з ключами називається криптосистемою.
Симетричні криптосистеми - це криптосистеми, у яких k = k'.
Асиметричні криптосистеми - це криптосистеми, у яких k != k'.
Блочні шифри:
Вхідне повідомлення ділиться на певні однакові частини(блоки) і кожна з цих частин по черзі і НЕЗАЛЕЖНО обробляється криптосистемою. Результуючим шифром буде об'єднання результатів роботи криптосистеми.
Потокові шифри:
Вхідне повідомлення обробляється таким чином, що на закодовування кожного наступного блоку впливає результат попередньої роботи.
Шифри заміни - це шифри, в яких кожній букві(слову,символу, біту...) ставиться у відповідність якийсь інший символ, або комбінація символів.
Шифри перестановок - це шифри, в яких у вхідному повідомленні за певним алгоритмом і залежно від ключа робиться перестановка символів(слів, бітів ...) у вхідному повідомленні.
Шифр Цезаря.
Ототожнюємо алфавіт, з якого побудоване вхідне повідомлення, з кільцем лишків Z(_n), де n - кількість літер в алфавіті. Вибираємо k, яке належить Z(_n).
Кожна літера x вхідного повідомлення кодується, як c = x+k mod n.
Ключем даної криптосистеми є k.
Частотний аналіз - ідеологія криптоатак, яка базується на визначенні частоти появи символів у зашифрованому тексті.
Ідея К.Гауса, що унеможливлює частотний аналіз:
Спочатку кожній літері алфавіту ставиться у відповідність певна множина можливих кодів цієї літери. При чому чим частіше ця літера зустрічається в мові, тим більша множина їй ставиться у відповідність. Крім того такі множини не повинні перетинатись. А далі при закодуванні з такої множини рендомом обирається код для відповідної літери.
Оскільки одна і та ж літера може бути закодована різними кодами, то за допомогою частотного аналізу стає практично неможливо атакувати криптосистему.
[відповідальний Роман Буняк]

Шифри Віженера,способи їх зламу. Ідея автокодування.

[відповідальна Оксана Підперигора]

питання 33

Шифр Вiженера винайдений в 16 столiттi i протягом 300 рокiв вважався незламним. Кожна буква алфавiту нумерується починаючи вiд нуля. Ключ - певна послiдовнiсть лiтер. Кодується так: ключ перiодично повторюється, щоб повнiстю покрити повiдомлення; рахується сума номера кожної лiтери повiдомлення і номера вiдповiдної лiтери ключа за модулем кількості літер в алфавіті. Результат - номер лiтери в криптотекстi. Наприклад: розглянемо англійський алфавіт, пронумеруємо літери (А - 0, Z - 25 ) Повідомлення- ilovetea ключ- abc записуємо ключ під повідомленням, повторюючи його скільки треба 

i   l    o    v   e   t   e   a 
a   b    c    a   b   c   a   b
8   11  14    21  4   19  4   0
0   1    2    0   1    2  0   1
8   12  16    21  5   21  4   1
i   m    q    v   f   v   e   b

де 1 рядок - повідомлення, 2 - ключ, 3- номери літер повідомлення, 4 - номери літер ключа, 5- сума номерів 3-го і 4-го рядків за модулем 26, 6 - зашифрована фраза. Отже, криптотекст - imqvfveb. Розшифровка проводиться аналогічно. Довжина ключа називається періодом. Шифр Віженера з періодом 1 називається шифром Цезаря, тобто кожна літера повідомлення зсувається вперед на певне фіксоване число місць по алфавіту.

Способи зламу . Сильна сторона шифру Віженера - він стійкий до частотного аналізу, оскільки літера е, припустимо, може бути зашифрована як будь-яка з певної кількості літер алфавіту у різних місцях повідомлення. Критична слабкість шифру Віженера- відносно короткий і повторюваний ключ. Якщо криптоаналітик знайде довжину ключа, то повідомлення можна розглядати як набір кількох ріних шифрів Цезаря, які в свою чергу тривіально ламаються за допомогою частотного аналізу. ( певні літери в алфавіті зустрічаються частіше ніж інші при утвореннні слів). Тести Казізкі і Фрідмана допомагають визначити довжину ключа.

Тест Казізкі (1863) два однакових відрізки відкритого тексту будуть відповідати двом однаковим відрізкам шифрованого тексту, якщо різниця номерів позицій їх початків кратна довжині ключа. Тобто, якщо ми виявимо 2 однакових відрізка криптотексту принаймні з 3 літер, то їм відповідають з великою ймовірністю однакові відрізки відкритого тексту. Суть тесту : знайти пари однакових відрізків,обчислити різниці номерів позицій їх початків і визначити їх спільні дільники.Один з них , як правило, є довжиною ключа.

тест Фрідмана Індекс співпадіння. Для послідовності букв індекс співпадіння - число, що дорівнює кількості всіх пар номерів позицій послідовності,на яких знаходяться однакові букви, поділеному на загальну кількість всіх пар номерів позицій цієї послідовності, тобто середньому числу пар, що складаються з однакових букв.

Автокодування . Шифр типу Віженера, в якому саме повідомлення використовується в якості ключа - шифр з автоключем. Шифрування починається з допомогою первинного ключа і продовжується за допомогою повдомлення, зміщеного на довжину первинного ключа. 

а   б   р   а    к    а    д   а   б   р   а
к   л   ю   ч    а    б    р   а   к   а   д
*   *   *   *    *    *    *   *   *   *   *

Афінні шифри, як узагальнення шифрів Віженера. Властивості афінних шифрів.

[відповідальна Оксана Підперигора]

питання 34

Афінні шифри - особливий варіант моноалфавітних шифрів підстановки(моноалфавітні - ті, які використовують фіксовану підстановку для всього повідомлення). Функція підстановки для літери x -> Ax+b, де х=(х_1,х_2,...,х_n), b=(b_1,b_2,...,b_n) x_i є Z_n, b_i є Z_n,де Z - група. А=(а_i,j) i,j=1..n,detA!=0 Переваги і недоліки такі ж як у шифа Віженера. Для англ. мови n=26, тому є всього 286 нетривіальних кодів, не враховуючи тривіального, коли а=1 - шифр Цезаря. Слабкість коду в тому, що якщо криптоаналітик визначить(за допомогою частотного аналізу, вгадування і т.д.) дві шифрувальні літери, то ключ можна легко знайти, розв’язавши відповідне рівняння. Властивості needed

Шифри 20-го сторіччя : Мішаний шифр ADFGVX, Enigma,шифр одноразового блокноту,як еталон незламного шифру.

[відповідальна Оксана Підперигора]

питання 35

ADFGVX - шифр, що використовувався у першій світовій війні німецькою армією. ADFGVX - розширення раніше використовуваного ADFGX . Робота алгоритму: Нехай нам треба закодувати повідомлення "Attack at once". Спершу алфавіт переставлений певним чином записується у квадрат 5х5 

	A 	D 	F 	G 	X
A 	b 	t 	a 	l 	p
D 	d 	h 	o 	z 	k
F 	q 	f 	v 	s 	n
G 	g 	j 	c 	u 	x
X 	m 	r 	e 	w 	y

ось так. Літери i i j поєднні в одній літері j. Потім кодуєтся повідомлення, при чому кожній літері відповідає пара : a->AF, p->AX і т.д. Отримали: 

A  T  T  A  C  K  A  T  O  N  C  E
AF AD AD AF GF DX AF AD DF FX GF XF

Потім беремо ключ. Нехай це буде C A R G O і записуємо повідомлення рядками під ним. 

C A R G O

_________ 

A F A D A
D A F G F
D X A F A
D D F F X
G F X F X

Далі здійснюємо перестановку ключа. отримуємо: 

A C G O R

_________ 

F A D A A
A D G F F
X D F A A 
D D F X F
F G F X X

Потім зчитуємо по стовпчиках і отримуємо криптотекст. FAXDF ADDDG DGFFF AFAXX AFAFX У 1918 році була додана літера V, що розширило таблицю до 6х6 і дало змогу дописувати до алфавіту цифри. ADFGVX був зламаний і зараз вважається ненадійним.

Enigma - портативна шифрувальна машина. Точніше - це сімейство електромеханічних роторних машин , які використовувались з 20-х років ХХ століття. Найбільшого розповсюдження набула в роки другої світової війни в нацистській Німеччині. По суті - багатократний Віженер зі змінною довжиною ключа.

Шифр одноразового блокноту. Це шифр у якому відкритий текст комбінується з ключем,що має таку ж довжину як сам текст і використовується лише раз. Щоб комбінувати текст і ключ використовується модульне додавання або XOR в двійкових даних. Винайдений у 1917. Якщо ключ справді рандомний, ніколи не використовувався і зберігається у таємниці, то оноразовий блокнот забезпечує ідеальну безпеку і є прикладом незламного шифру.

Принципи роботи системи кодування DES. Показати використання попередніх ідей шифрування.

[відповідальна Оксана Підперигора]

DES - digital encrypting standart Повідомлення - 64 біти розбивається на два блоки по 32 біти - Left i Right. Шифрування відбувається в 16 раундів. Left в новому раунді дорівнює Right попереднього. А Right в новому - це Left з попереднього ксорена з Right-перестановками(функція від Right і ключа). Ключ - 64 біта, але кожен 8 контрольна сума. Решта 56 бітів ділиться на два блоки по 28 бітів. В кожній частині односасно відбувається циклічний зсув на 1 або на 2 позиції. Right розширюється до 48 бітів, а ключ стискається до 48 бітів. Відбувається їхній ксор. Далі робимо підстановку в S-блок, який розбиває 48 біт на 8 частин. Існує 8 S-блоків, кожен з яких посвоєму обробляє вхідні 6 бітів і видає 4. З S-блоку виходить 32 біти і далі відбувається перестановка в P-блоці. Далі робимо описану вище процедуру ксору з Left.

Концепція асиметричної криптографії (шифрування з відкритим ключем) за Діффі та Хелманом. Пояснити на прикладі ситсеми RSA. $

[відповідальна Ромашевська Мирослава]

Питання 37

Концепція асиметричного шифрування - 1976 р. (Вітфільд Діффі, Мартін Хелман, Ральф Меркле):

ключ k_e - код закодовування

ключ k_d - код розкодовування

k_e знають усі. Пишуть і шифрують ним. k_d - секретний.

Є дві системи:

1. Робіна Вільямса

2. RSA


Проблема при ламанні коду:

p, q - прості. n = p*q. Якщо n можна знайти, то відновити з n p і q важко.

Тобто n - це k_e; а p, q - k_d.


RSA

RSA працює просто

Нехай повідомлення m - натуральне число.

Генеруємо відкритий ключ.

k_e - (e,n), де е - число, умова: е є Z_phi(n) (функція Ейлера)

Тобто n оборотній до е. Функція Ейлера дає порядок мультиплікативної групи.

phy(n)=|Z^*_n|.

У нашому випадку phy(n)=(p-1)*(q-1)

Якщо e з n оборотнє, то 

э d:e*d equvivalent 1 mod phy(n)

Секретний ключ k_d , яким читається повідомлення:

(d, phy(n))

Читаємо так:

Криптотекст c=(m^e)mod n є числом від 1 до n.

Беремо(c^d)mod n=(m^e*d)=m^(1+k*phy(n))=m*m(^k*phy(n))=m, бо m(^k*phy(n))=1 mod phy(n).

Поідомлення розшифроване.


Організація електронного підпису за допомогою асиметричної криптосистеми. $

[відповідальна Ромашевська Мирослава]

Питання 38

Розглянемо організацію електронного підпису за допомогою асиметричної криптосистеми на прикладі RSA.

Нехай k_e1, k_d1 - відповідно відкриті та закртиті ключі того, хто відправляє повідомлення,

а k_e2, k_d2 - того, хто отримує. m - повідомлення, що шифрується.

Тоді (m^e2)mod n2 (m^d1)mod n1 - зашифроване повідомлення з електронним підписом відправника,

де (m^e2)mod n2 - зашифроване повідомлення за допомогою відкритого ключа отримувача,

(m^d1)mod n1 - електронний підпис - зашифроване повідомлення за допомогою закритого ключа відправника.

Коли отримувач отримує зашифроване повдіомлення з електронним підписом (с=с1с2),

то першу його частину розшифровує за допомогою свого закритого ключа (c1^d2)mod n2,

а другу - за допомогою відкритого ключа відправника (c2^е1)mod n1.

Якщо ці частини одинакові, то це повідомлення ми дійсно отримали від даного відправника.

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

[відповідальна Ромашевська Мирослава]

Питання 39

Нехай F_p = \left \{ 1, 2, \cdots p-1 \right \} - мультиплікативна група цілих по модулю p (p - просте число).

g \in F_p - фіксоване.

Проблема: для заданого y потрібно знайти дискретний логарифм x такий, що gx = ymod p.

На проблемі дискретного логарифму базується протокол обміну ключами за Діффі-Хеллманом.

Приклад

Аліса та Боб повинні обмінятися ключами.

Аліса та Боб домовляються про просте p, g \in F_p.

Аліса обирає число 0 < ka < p і надсилає Бобу g^{k_a} \bmod p.

Боб обирає число 0 < kb < p і надсилає Алісі g^{k_b} \bmod p.

Кожний окремо рахує число g^{k_a*k_b}. Аліса рахує таким чином g^{k_a*k_b} = \left ( g^{k_b} \right )^{k_a}, а Боб g^{k_a*k_b} = \left ( g^{k_a} \right )^{k_b}

Тепер і Аліса, і Боб знають g^{k_a*k_b} - яке і є ключем. Але числа k_a,\! k_b залишаються в секреті.

Проблема: знайти g^{k_a*k_b}, знаючи p, g, g^{k_a}, g^{k_b}.

(Може, треба додати Ель-Гаммаля)

Система електронного підпису DSA. $

[відповідальна Ромашевська Мирослава]

Питання 40

DSA (Digital Signature Algorithm) — алгоритм з використанням відкритого ключа для створення електронного підпису, але не для шифрування. Секретне створення хеш-значення повідомлення і його публічна перевірка - тільки одна людина може створити хеш-значення повідомлення, але будь-хто може перевірити його коректність. Заснований на обчислювальній складності взяття логарифмів скінченних полях. Алгоритм був запропонований NIST (Національним Інститутом Стандартів та Технологій, США) у серпні 1991 року.

Вибір параметрів

Для підписування повідомлень необхідна пара ключів - відкритий та закритий. Параметри самого алгоритму - загальнодоступні.

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

1. Вибір хеш-функції H(x). (Не ентропії!!!) Для використання алгоритму необхдіно, щоб повідомлення,яке підписується, було числом. Хеш-функція повинна перетворити будь-яке повідомлення в число.

2. Вибір великого простого числа q, розмірінсть якого в бітах співпадає з розмірністю в бітах значень хеш-функції Н(х).

3. Вибір простого числа р, такого, що (p-1) ділиться на q. Розмірність Р задає криптостійкість системи. Раніше рекомендувалась довжина в 1024 біта. На даний момент для систем, які повинні бути стійкими до 2010(2030)року, рекомендується довжина в 2048(3072) біта. (кратна 64)

4. Вибір числа g такого, що його мультиплікативний порядок за модулем р дорівнює q. Для його обчислення можна скористатись формулою g = h(p-1)/q mod p, де h - певне довільне число, 1<h<p-1, таке, що g<>1. Зазвичай h = 2 задовільняє цю умову.

Генерація відкритого та закритого ключа

1. Закритий ключ - число з інтервалу x ∈ (0, q)

2. Відкритий ключ обчислюється за формулою y=gx mod p

Відкриті параметри - числа (p,q,g,y). Закритий - лише один x.

Підпис повідомлення

Підпис здійснюється за наступним алгоримтом:

1. Вибір випадкового числа k ∈ (0, q)

2. Знаходження r = (gk mod p)mod q

3. Знаходження s = k-1 * H(m) + x*r (mod q)

4. Вибір іншого k, якщо виявилось, що r=0 або s=0

Підписом є пара чисел (r,s) 

Перевірка підпису

Перевірка підпису здійснюється за наступним алгоритмом:

1. Знаходимо w=s-1 mod q

2. Знаходимо u1 = (H(m)*w)mod q

3. Знаходимо u2 = (r*w)mod q

4. Знаходимо v = ((gu1*yu2)mod p) mod q

Підпис правильний, якщо v = r

Правильність алгоритму

Підпис схеми правильний в розумінні, що верифікатор завжди прийматиме справжні підписи.

Це можна показати так:

По-перше, якщо g = h(p–1)/q mod p, то звідси випливає, що gq ⇔ hp-1 ⇔ 1 mod p за малою теоремою Ферма.

Оскільки g>1 і q просте, то g повинно мати порядок на q.

Підписувач обчислює s=k-1(H(m)+x*r) mod q.

Таким чином 

k ⇔ H(m)*s-1+x*r*s-1 ⇔ H(m)*w + x*r*w mod q

Оскільки g впорядковане на q, то ми маємо: 

gk ⇔ g(H(m)*w)*g(x*r*w) ⇔ gH(m)*w*yr*w ⇔ gu1*yu2 mod p

Нарешті, правильність DSA випливає з: 

r=(gk mod p) mod q = (gu1*yu2 mod p) mod q = v.


Стандартизовані Умовні Позначення

ksi - літера ксі ( випадкова величина ксі ξ)

alpa - літера альфа

lambda - літера лямбда

eta - (η використовувалась в лекціях), велика позначалась Η, малою позначалась η, наприклад сумісна ентропія Η(ξ,η) у нас виглядатиме як H(ksi,eta)

phi - літера фі

H(ksi) - ентропія

p - ймовірність

_i - нижній індекс, наприклад: p(_i) - i-та ймовірність

A|B - виконання події А за умови виконання події B (А за умови B)

^i - верхній індекс, або степінь

SUM - сума, наприклад SUM(_i=0)(^n) - сума від 0 до n [] - операторні дужки - в них стоїть вираз по якому йде обчислення: логарифм при основі 2 з 10 = log(_2)[10], або сума від одного до 10 по p(_i) = SUM(_i=1)(^10)[p(_i)]

[[1 1 1][0 0 0][1 1 1]] - позначення для матриці:
|1 1 1|
|0 0 0|
|1 1 1|

M(_i) - і-тий рядок матриці М


|= - логічний наслідок

/\ - перетин

V - об"єднання

є або э - належить, наприклад A*э S значить "S належить A*"

!є або !э - не належить

Э - існує

!Э - не існує

equvivalent - значок еквівалентності(потрійне дорівнює(тобто три горизонтальні риски))

<> - не дорівнює

%float% -- зведення до цілого зверху. (5.4 = 6, як я поняв... це є в 8-му запитанні.)


CЛУЖБОВІ СИМВОЛИ:

/* */ - все що знаходиться між ними - необов"язкове

Отримано з http://wiki.usic.org.ua/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B8_%D0%BA%D0%BE%D0%B4%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D1%96%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D1%96%D1%97:%D0%86%D1%81%D0%BF%D0%B8%D1%82
Особисті інструменти