Кількісна оцінка інформації

Кількісна оцінка ІНФОРМАЦІЇ

Загальне число неповторюваних повідомлень, яке може бути складеноз алфавіту m шляхом комбінування з n символів у повідомленні,

. (1)

Невизначеність, що припадає на символ первинного (кодованого) [1]алфавіту, складеного з равновероятностних і взаімонезавісімих символів,

. (2)

Основа логарифма впливає лише на зручність обчислення. У разіоцінки ентропії: а) в двійкових одиницях

б) у десяткових одиницях

де; в) у натуральних одиницях

де

Так як інформація є невизначеність, знімна при отриманніповідомлення, то кількість інформації може бути представлено яктвір загальної кількості повідомлень до на середню ентропію Н, що припадаєна одне повідомлення:

(3)

Для випадків равновероятностних і взаімонензавісімих символівпервинного алфавіту кількість інформації в повідомленнях до алфавіту m одно

а кількість інформації в повідомленні, складеному з к неравновероятностнихсимволів,

(5)

Для неравновероятностних алфавітів ентропія на символ алфавіту

(4)

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

Кількість інформації визначається виключно характеристикамипервинного алфавіту, об'єм - характеристиками вторинного алфавіту. Обсяг [2]інформації

(6)де lср - середня довжина кодових слів вторинного алфавіту. Для рівномірнихкодів (всі комбінації коду містять однакову кількість розрядів)

де n - довжина коду (число елементарних посилок в коді). Згідно (3), обсягдорівнює кількості інформації, якщо lср = Н, тобто у випадку максимальноїінформаційного навантаження на символ повідомлення. У всіх інших випадках
.
Наприклад, якщо кодувати в коді Бодо деякі рівноймовірно алфавіт,що складається з 32 символів, то

Якщо закодувати в коді Бодо російська 32-літерний алфавіт, то безобліку кореляції між літерами кількість інформації

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

Тема 2. Умовна ентропія та ентропія об'єднання

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

У всіх випадках при обчисленні умовної ентропії в тому чи іншому виглядівикористовуються умовні ймовірності.

Якщо при передачі n повідомлень символ А з'явився m раз, символ Вз'явився l разів, а символ А разом із символом В - к разів, то ймовірністьпояви символу А; ймовірність появи символу В;ймовірність спільного появи символів А і В; умовнаймовірність появи символу А щодо символу В і умовнаймовірність появи символу У відносно символу А

(7)

Якщо відома умовна ймовірність, то можна легко визначити іймовірність спільного появи символів А і В, використовуючи вирази (7)

(8)

Від класичного вираження (4) формула умовної ентропії відрізняєтьсятим, що в ній ймовірності - умовні:

(9)

(10)де індекс i обраний для характеристики довільного стану джерелаА повідомлення, індекс j обраний для характеристики довільного стануадресата В.

Розрізняють поняття приватної і загальної умовної ентропії. Вираз (9) і
(10) являють собою приватні умовні ентропії.

Загальна умовна ентропія повідомлення У відносно повідомлення Ахарактеризує кількість інформації, що міститься в будь-якому символі алфавіту,і визначається грам по всіх символів, тобто по всіх станів зурахуванням ймовірності появи кожного з станів, і дорівнює суміймовірностей появи символів алфавіту на невизначеність, яказалишається після того, як адресат прийняв сигнал

(11)

Вираз (11) є загальним виразом для визначення кількостіінформації на один символ повідомлення для випадку нерівномірних івзаімонезавісімих символів.

Так як є ймовірність спільного появидвох подій, то формула (11) можна записати наступним чином:

(12)

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

У загальному випадку, якщо ми передаємо m сигналів А і очікуємо отримати mсигналів, вплив перешкод у каналі зв'язку повністю описується канальноїматрицею, яку ми наводимо нижче:

| В | |
| А | b1 b2 ... bj |
| | ... Bm |
| а1 | |
| а2 | ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. |
| ... | |
| АI | |
| ... | ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... |
| аm | |
| | |

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

Якщо описувати канал зв'язку з боку джерела повідомлень, топроходження даного виду сигналу в даному каналі зв'язку описуєтьсярозподілом умовних ймовірностей виду, так для сигналу
розподілом виду

(13)
(14)
(15)
(16)

(17)
(18)

(19)

тема 3. Обчислення інформаційних втрат при передачі повідомлень по каналах зв'язку з шумами

Втрати інформації в каналах зв'язку з шумами зазвичай описують придопомоги умовної ентропії і ентропії об'єднання.

Якщо перешкод немає або їх рівень настільки низький, що вони не в змозізнищити сигнал або імітувати корисний сигнал під час відсутності передачі, топри передачі ми будемо твердо впевнені, що отримаємо - сигнал,відповідний переданому ai-му сигналу. Події А і В статистичножорстко пов'язані, умовна ймовірність максимальна, а умовна ентропія
!!!! 1так як !!!!. У цьому випадку кількість інформації, що міститься в прийнятомуансамблі повідомлень В, так само ентропії переданих повідомлень ансамблю А,тобто I (В, А) = Н (А).

При високому рівні перешкод будь-який з прийнятих сигналів bj можевідповідати будь-якого прийнятого сигналу ai, статистичний зв'язок міжпереданими та прийнятими сигналами відсутній. У цьому випадкуймовірності !!!!!! Є ймовірність незалежних подій і !!!!!!< br>!!!! 1тому що!! 11, тобто умовна ентропія дорівнює безумовній, а кількістьінформації, що міститься в В, щодо А дорівнює нулю:
!!!!

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

Незважаючи на те, що частина інформації уражається перешкодами, міжприйнятими і переданими повідомленнями існує статистична залежність.
Це дозволяє описувати інформаційні характеристики реальних каналівзв'язку за допомогою ентропії об'єднання статистично залежних подій. Такяк
!!!! 1то втрати в каналі зв'язку можуть бути враховані за допомогою ентропії об'єднаннянаступним чином:
!! 1!а з використанням умовної ентропії
!!!

Для обчислення середньої кількості інформації, що міститься вприйнятому ансамблі повідомлень У відносно переданого ансамблю повідомлень
А в умовах дії перешкод, користуються такими виразами, виведенимибезпосередньо з вираження (25):
!!!!!!!!

Для обчислення часто зручно застосовувати вирази (26-28) у вигляді
!!!!!!!

Для повного та всебічного опису каналу зв'язку необхідно задати:канальну матрицю виду !!!!!! і безумовні ймовірності виду!!!! абоканальну матрицю виду !!!!!! і безумовні ймовірності виду !!!!!. Уостанньому випадку сума значень по стовпцях матриці дає безумовніймовірності виду !!!!!!!!!!, а сума за рядками дає безумовніймовірності виду !!!!!!. Умовні ймовірності можуть бути знайденими звиразів:
!!!!!!!

Знаючи умовні і безумовні ймовірності, можна знайти Н (А), Н (В),
Н (А/В) і Н (В/А).

Якщо рівень перешкод настільки високий, що з однаковою ймовірністю можнаочікувати перехід будь-якого символу джерела повідомлення в довільний символпервинного алфавіту,. то ентропія каналу зв'язку буде дорівнює !!!!!, акількість інформації !!!!!!!, при цьому значення I може бути негативноювеличиною, що означає, що канал зв'язку вносить дезінформацію.

ТЕМА 5. ВИЗНАЧЕННЯ НАДЛИШКОВОГО ПОВІДОМЛЕНЬ. ОПТИМАЛЬНЕ КОДУВАННЯ

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

Для визначення кількості «зайвої» інформації, яка закладена вструктурі алфавіту або в природі коду, вводиться поняття надмірності.
Надмірність, з якою ми маємо справу в теорії інформації, не залежить відзмісту повідомлення і зазвичай заздалегідь відома зі статистичних даних [4].
Інформаційна надмірність показує відносну недовантаженими насимвол алфавіту і є безрозмірною величиною:

(45)де - коефіцієнт стиснення (відносна ентропія). іберуться щодо одного і того ж алфавіту.

Крім загального поняття надмірності існують приватні види надмірності.

Надмірність, обумовлена неравновероятним розподілом символів уповідомленні,

(46)

Надмірність, викликана статистичної зв'язком між символами повідомлення,

(47)

Повна інформаційна надмірність

(48)

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

Так при передачі десяткових цифр двійковим кодом максимально завантаженимибувають тільки ті символи вторинного алфавіту, які передають значення,є цілочисельними ступенями двійки. В інших випадках тим жекількістю символів може бути передано більшу кількість цифр
(повідомлень). Наприклад, трьома двійковими розрядами ми можемо передати і цифру
5, і цифру 8, тобто на передачу п'яти повідомлень витрачається стільки жсимволів, скільки витрачається і на вісім повідомлень.

Фактично для передачі повідомлення достатньо мати довжину кодовоїкомбінації

,де N - загальна кількість переданих повідомлень.

L можна представити і як

,де і-відповідно якісні ознаки первинного івторинного алфавітів. Тому для цифри 5 у двійковому коді можна записати

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

де - округлене до найближчого цілого числа значення. Длянашого прикладу

Надмірність - не завжди небажане явище. Для підвищеннязавадостійкості кодів надмірність необхідна і її вводять штучно ввигляді додаткових символів (див. тему 6). Якщо в коді всього прозрядів і з них несуть інформаційне навантаження, то =характеризує абсолютну коригувальну надмірність, а величинахарактеризує відносну коригувальну надмірність.
Інформаційна надмірність - звичайно явище природне, закладена вона впервинному алфавіті. Коригуюча надмірність - явище штучне,закладена вона в кодах, представлених у вторинному алфавіті.
Найбільш ефективним способом зменшення збитковості повідомлення єпобудова оптимальних кодів.
Оптимальні коди [5] - коди з практично нульовою надмірністю.
Оптимальні коди мають мінімальну середню довжину кодових слів - L. Верхняі нижня межі L визначаються із нерівності

(49)де Н - ентропія первинного алфавіту, т - число якісних ознаквторинного алфавіту.
У разі поблочно кодування, де кожен з блоків складається з Мнезалежних букв, мінімальна середня довжина кодового блоку лежить вмежах

(50)

Загальна вираз середнього числа елементарних символів на букву повідомленняпри блоковому кодуванні

(51)

З точки зору інформаційного навантаження на символ повідомлення по блокахкодування завжди вигідніше, ніж політерний.
Суть блокового кодування можна з'ясувати на прикладі поданнядесяткових цифр у двійковому коді. Так, при передачі цифри 9 в двійковому кодінеобхідно витратити 4 символу, тобто 1001. Для передачі цифри 99 приполітерний кодуванні - 8, при поблочно - 7, так як 7 двійкових знаківдостатньо для передачі будь-якої цифри від 0 до 123; при передачі цифри 999співвідношення буде 12 - 10, при передачі цифри 9999 співвідношення буде 16 -
13 і т.д. У загальному випадку «вигода» блокового кодування виходить і зарахунок того, що в блоках відбувається вирівнювання ймовірностей окремихсимволів, що веде до підвищення інформаційного навантаження на символ.

При побудові оптимальних кодів найбільшого поширення знайшлиметодики Шеннона-Фано і Хаффмена.

Згідно з методикою Шеннона - Фано побудова оптимального коду ансамблю зповідомлень зводиться до наступного:

1-й крок. Безліч з повідомлень розташовується в порядку убуванняймовірностей.

2-й крок. Початковий ансамбль кодованих сигналів розбивається на двагрупи таким чином, щоб сумарні ймовірності повідомлень обох групбули по можливості рівні. Якщо рівній ймовірності в підгрупах не можнадосягти, то їх ділять так, щоб у верхній частині (верхній підгрупі)залишалися символи, сумарна ймовірність яких менше сумарноїймовірності символів у нижній частині (у нижній підгрупі).

3-й крок. Першій групі присвоюється символ 0, другої групи символ 1.

4-й крок. Кожну з освічених підгруп ділять на дві частини такимчином, щоб сумарні ймовірності новостворених підгруп були поможливості рівні.

5-й крок. Першим групам кожної з підгруп знову присвоюється 0, адруга - 1. Таким чином, ми отримуємо друга цифри коду. Потім кожна зчотирьох груп знову ділиться на рівні (з точки зору сумарноюймовірності) частині до тих пір, поки в кожній з підгруп не залишиться поодній букві.
Згідно з методикою Хаффмена, для побудови оптимального коду N символипервинного алфавіту виписуються в порядку убування ймовірностей. Останні
символів, де [6] і - ціле число, об'єднують в деякийновий символ з імовірністю, яка дорівнює сумі ймовірностей об'єднанихсимволів Останні символи з урахуванням утвореного символу знову об'єднують,отримують новий, допоміжний символ, знову виписують символи в порядкуубування ймовірностей з урахуванням допоміжного символу і т. д. до тих пір,поки сума ймовірностей т залишилися символів після-го виписування впорядку убування ймовірностей не дасть в сумі ймовірність, що дорівнює 1. Напрактиці звичайно, не роблять багаторазового виписування ймовірностейсимволів з урахуванням ймовірності допоміжного символу, а обходятьсяелементарними геометричними побудовами, суть яких зводиться до того,що символи кодованого алфавіту попарно об'єднуються в нові символи,починаючи з символів, що мають найменшу ймовірність. Потім з урахуванням зновуутворених символів, яким присвоюється значення сумарної ймовірностідвох попередніх, будують кодове дерево, у вершині якого стоїть символ зймовірністю 1. При цьому відпадає необхідність у впорядкування символівкодованого алфавіту в порядку убування ймовірностей.
Побудовані за вказаними вище (або подібних) методиками коди знерівномірним розподілом символів, що мають мінімальну середню довжинукодового слова, називають оптимальним, нерівномірним, кодами (ОНК).
Рівномірні коди можуть бути оптимальними тільки для передачі повідомлень зарівноймовірно розподілом символів первинного алфавіту, при цьому числосимволів первинного алфавіту має дорівнювати цілої ступеня числа, рівногокількості якісних ознак вторинного алфавіту, а в разі двійковихкодів - цілої ступеня двох.
Максимально ефективними будуть ті ОНК, у яких

Для двійкових кодів

(52)так як log22 = 1. Очевидно, що рівність (52) задовольняється приумови, що довжина коду у вторинному алфавіті

Величина точно дорівнює Н, якщо, де п - будь-яке ціле число. Якщоп не є цілим числом для всіх зн?? чений букв первинного алфавіту, то
і, згідно з основною теореми кодування [7], середня довжина кодовогослова наближається до ентропії джерела повідомлень в міру укрупненнякодованих блоків.
Ефективність ОНК. оцінюють за допомогою коефіцієнта статистичногостиснення:

(53)який характеризує зменшення кількості двійкових знаків на символповідомлення при застосуванні ОНК у порівнянні із застосуванням методівнестатістіческого кодування і коефіцієнта відносної ефективності
(54)який показує, наскільки використовується статистична надмірністьпереданого повідомлення.
Для найбільш загального випадку неравновероятних і взаімонезавісімих символів

Для випадку неравновероятних і взаємозалежних символів

ТЕМА 6 . Виявлення і виправлення помилок У ПОВІДОМЛЕННЯХ

Поняття про ідею корекції помилок

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

10110 - передана кодова комбінація;

10010 - 1-а прийнята комбінація;

10100 --а прийнята комбінація;

00110 - 3-я прийнята комбінація;

10110 - накопичена комбінація.
Як бачимо, незважаючи на те, що у всіх трьох прийнятих комбінаціях булипомилки, накопичена не містить помилок [8].
Прийняте повідомлення може також складатися з коду і його інверсії. Код таінверсія посилаються в канал зв'язку як одне ціле. Помилка на приймальному кінцівиділяється при зіставленні коду і його інверсії.
Для того щоб спотворення будь-якого із символів сполучення призвело дозабороненої комбінації, необхідно в коді виділити комбінації, що відрізняютьсяодин від одного в ряді символів, частина з цих комбінацій заборонити і тимсамим ввести в код надмірність. Наприклад, в рівномірному блоковому кодівважати дозволеними кодові комбінації з постійним співвідношенням нулів іодиниць у кожної кодової комбінації. Такі коди отримали назву кодів зпостійним вагою. Для двійкових кодів число кодових комбінацій в кодах зпостійним вагою довжиною в п символів одно

(55)де - число одиниць у кодовому слові. Якщо б не існувало умовипостійного ваги, то кількість комбінацій коду могло б бути набагато більшою, асаме. Прикладом коду з постійним вагою може служити стандартнийтелеграфний код № 3 (див. додаток 4). Комбінації цього коду побудованітаким чином, що на 7 тактів, протягом яких повинна бути прийнята однакодова комбінація, завжди припадають три струмові і чотири безтоковиепосилки. Збільшення або зменшення кількості струмових посилок говорить пронаявності помилки.

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

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

Коди без надмірності виявляти, а тим паче виправляти помилки неможуть [9]. Мінімальна кількість символів, в яких будь-які дві комбінаціїкоду відрізняються один від одного, називається кодовою відстанню. Мінімальнакількість символів, в яких всі комбінації коду відрізняються один відодного, називається мінімальною кодовою відстанню. Мінімальна кодовавідстань - параметр, що визначає перешкодостійкість коду і закладену вкоді надмірність. Мінімальним кодовою відстанню визначаютьсякоригуючі властивості кодів.

У загальному випадку для виявлення r помилок мінімальна кодова відстань

(56)
Мінімальна кодова відстань, необхідне для одночасноговиявлення та виправлення помилок,

(57)де s - число виправляємо помилки.

Для кодів, тільки що виправляють помилки,

(58)

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

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

Якщо кодова комбінація двійкового коду А відстоїть від кодової комбінації Уна відстані d, то це означає, що в коді А треба d символів замінити назворотні, щоб отримати код В, але це не означає, що потрібно d додатковихсимволів, щоб код володів даними коригуючими властивостями. У двійковихкоди для виявлення одиночної помилки досить мати 1 додатковийсимвол незалежно від числа інформаційних розрядів коду, а мінімальнекодова відстань
Для виявлення та виправлення одиночної помилки співвідношення між числомінформаційних розрядів і числом коригувальних розрядів повиннозадовольняти таким умовам:

(59)

60)при цьому мається на увазі, що загальна довжина кодової комбінації

. (61)
Для практичних розрахунків при визначенні числа контрольних розрядівкодів з мінімальною кодовою відстанню зручно користуватисявиразами:

(62)якщо відома довжина повної кодової комбінації п, і

(63)якщо при розрахунках зручніше виходити з певної кількості інформаційнихсимволів [10].
Для кодів, що виявляють все триразові помилки

(64)або

(65)
Для кодів довжиною в п символів, що виправляють одну або дві помилки

(66)
Для практичних розрахунків можна користуватися виразом

(67)

Для кодів, що виправляють помилки 3

(68)

Для кодів, що виправляють s помилок

(69)
Вираз ліворуч відомо як нижня межа Хеммінга [16], а виразсправа - як верхня межа Варшамова - Гільберта [3] [11]

Для наближених розрахунків можна користуватися виразом

(70)
Можна припустити, що значення буде наближатися до верхньої межів залежності від того, наскільки вираз під знаком логарифманаближається до цілої ступеня двох.

Лінійні групові коди

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

Для двійкових кодів в якості лінійної операції використовують додавання помодулю 2.

Правила складання по модулю 2 визначаються такі рівняння:

Послідовність нулів та одиниць, що належать даному коду, будемоназивати кодовою вектором.
Властивість лінійних кодів: сума (різниця) кодових векторів лінійного кодудає вектор, що належить даному коду.
Лінійні коди утворюють алгебраїчну групу по відношенню до операціїскладання по модулю 2. У цьому сенсі вони є груповими кодами.
Властивість групового коду: мінімальна кодова відстань між кодовимивекторами групового коду дорівнює мінімальній вазі ненульових кодовихвекторів.
Вага кодового вектора (кодової комбінації) дорівнює числу його ненульовихкомпонентів.
Відстань між двома векторами кодовими одно вазі вектора, отриманогов результаті складання вихідних векторів за модулем 2. Таким чином, дляданого групового коду

Групові коди зручно задавати матрицями, розмірність якихвизначається параметрами коду та. Число рядків матриці одно
, Число стовпців одно +=:

(71)
Коди, що породжуються цими матрицями, відомі як-коди, де, авідповідні їм матриці називають породжують, що виробляють,утворюють.
породжує матриця С може бути представлена двома матрицями І і П
(інформаційної та перевірочної). Кількість стовпців матриці П одно, числостовпців матриці І одно:

(72)

Теорією і практикою встановлено, що як матрицю І зручно братиодиничну матрицю в канонічній формі:

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

Вага кожного рядка матриці П повинен бути не менше, де - вагавідповідного рядка матриці І. Якщо матриця І - одинична, то
(зручність вибору як матрицю І одиничної матриці очевидно: заускладнилося б як побудова кодів, так і їх технічна реалізація).

При дотриманні перерахованих умов будь-яку породжує матрицю груповогокоду можна привести до наступного вигляду:

званого лівого канонічною формою породжує матриці.
Для кодів з = 2 виробляє матриця С має вигляд

В усіх комбінаціях коду, побудованого за допомогою такої матриці, парнечисло одиниць.
Для кодів з породжує матриця не може бути представлена у формі,загальною для всіх кодів з даними. Тип матриці залежить від конкретнихвимог до породжуване коду. Цими вимогами можуть бути або мінімумкоригувальних розрядів, або максимальна простота апаратури.
Коригувальні коди з мінімальною кількістю надлишкових розрядівназивають щільно упакованими або досконалими кодами.
Для кодів з співвідношення п и. наступні: (3: 1), (7; 4), (15;
11), (31; 26), (63; 57) і т. д.
Ретельно упаковані коди, оптимальні з точки зору мінімуму надлишковихсимволів, які виявляють максимально можливу кількість варіантів помилоккратністю r + 1; r + 2 і т. д. і які мають і, були досліджені Д.
Слепяном в роботі [10]. Для отримання цих кодів матриця П повинна матикомбінації з максимальною вагою. Для цього при побудові кодів зпослідовно використовуються вектори довжиною п, вагою. Тим же
Слепяном в роботі [11] були досліджені нещільно упаковані коди з малоющільністю перевірок на парність. Ці коди економні з точки зору простотиапаратури і містять мінімальне число одиниць у коригувальних розрядахпороджує матриці. При побудові кодів з максимально простимишифратори і дешифратор послідовно вибираються вектори вагою
= 2, 3, ...,. Якщо число комбінацій, що представляють собоюкоригувальні розряди коду та задовольняють умові, більше,то в першому випадку не використовують набори з найменшою вагою, а в другому - знайбільшим.

Строчки що утворює матриці З представляють собою комбінацій шуканогокоду. Інші комбінації коду будуються за допомогою утворюючої матриці понаступного правилом: коригувальні символи, призначені для виявленняабо виправлення помилок в інформаційній частини коду, знаходяться шляхомпідсумовування за модулем 2 тих рядків матриці П, номери яких співпадають зномерами розрядів, що містять одиниці в кодовому вектор, який являєінформаційну частину коду. Отриману комбінацію приписують справа доінформаційної частини коду і отримують вектор повного коригуючого коду.
Аналогічну процедуру роблять з другого, третього і наступнимиінформаційними кодовими комбінаціями, поки не буде побудованийкоригуючий код для передачі всіх символів первинного алфавіту.

Алгоритм освіти перевірочних символів за відомою інформаційноїчастини коду може бути записана наступним чином:

У процесі декодування здійснюються перевірки, ідея яких у загальному виглядіможе бути представлена наступним чином:

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

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

Вид синдрому для кожної конкретної матриці може бути визначений придопомоги перевірочної матриці Н, яка являє собою транспонованаматрицю П, доповнену одиничною матрицею, число стовпців якоїдорівнює числу перевірочних розрядів коду:

.
Стовпці такої матриці являють собою значення синдрому для розряду,відповідного номеру стовпця матриці Н.
Процедура виправлення помилок у процесі декодування групових кодівзводиться до наступного.
Будується кодова таблиця. У першому рядку таблиці розташовуються всікодові вектори. У першому стовпці другого рядка розміщується вектор
, Вага якого дорівнює 1.
Інші позиції другого рядка заповнюються векторами, отриманими врезультаті підсумовування за модулем 2 вектора c вектором,розташованим у відповідному стовпці першого рядка. У першому стовпцітретій рядки записується вектор, вага якого також дорівнює 1,однак, якщо вектор містить одиницю в першому розряді, то - удруге. В інші позиції третій рядки записують суми і.
Аналогічно надходять до тих пір, поки не будуть підсумував з векторами
всі вектори, вагою 1, з одиницями в кожному з п розрядів. Потімпідсумовуються за модулем 2 вектори, вагою 2, з послідовнимперекриттям всіх можливих розрядів. Вага вектора визначає числовиправляємо помилок. Число векторів, визначається можливим числомнеповторюваних синдромів і дорівнює (нульова комбінація говорить провідсутності помилки). Умова неповторяемості синдрому дозволяє за його увазівизначати один-єдиний відповідний йому вектор. Вектори
, Є вектори помилок, які можуть бути виправлені даними груповимкодом.
По виду синдрому прийнята комбінація може бути віднесена до того чи іншогосуміжному класу, що було створене складанням за модулем 2 кодової комбінації
з вектором помилки, тобто до певної рядку кодової табл.
6.1.

Таблиця 6.1

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

Вектори не повинні бути рівні жодному з векторів, вІнакше в таблиці з'явилися б нульові вектори.

тривіальні систематичні коди.

Код Хеммінга

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

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

Код Хеммінга є типовим прикладом систематичного коду. Однак прийого побудові до матриць зазвичай не вдаються. Для обчислення основнихпараметрів коду задається або кількість інформаційних символів, абокількість інформаційних комбінацій. За допомогою (59) і (60)обчислюються і. Співвідношення між код Хеммінгапредставлені в табл. 1 додатка 8. Знаючи основні параметрикоригуючого коду, визначають, які позиції сигналів будуть робочими, аякі контрольними. Як показала практика, номери контрольних символівзручно вибирати за законом, де і т.д. - Натуральний ряд чисел.
Номери контрольних символів в цьому випадку будуть відповідно: 1, 2, 4, 8,
16, 32 і т. д.
Потім визначають значення контрольних коефіцієнтів (0 або 1),керуючись наступним правилом: сума одиниць на контрольних позиціяхповинна бути парному. Якщо ця сума парна, то значення контрольногокоефіцієнта - 0, в іншому випадку - 1.
Перевірочні позиції вибираються наступним чином: складається таблицядля ряду натуральних чисел у двійковому коді. Число рядків таблиці

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

Якщо у прийнятому коді є помилка, то результати перевірок з контрольнимпозиціях утворюють двійкове число, яке вказує номер помилкової позиції.
Виправляють помилку, змінюючи символ помилкової позиції на зворотний.
Для виправлення одиночної і виявлення подвійної помилки, крім перевірок поконтрольним позицій, слід проводити ще одну перевірку на парність длякожного коду. Щоб здійснити таку перевірку, слід до кожного коду вНаприкінці кодової комбінації додати контрольний символ таким чином, щобсума одиниць в отриманій комбінації завжди була парному. Тоді у разіоднієї помилки перевірки по позиціях вкажуть номер помилкової позиції, аперевірка на парність вкаже наявність помилки. Якщо перевірки позицій вкажуть нанаявність помилки, а перевірка на парність не фіксує помилки, значить в кодідві помилки

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

Циклічні коди [4, 6, 7, 9, 12, 13] названі так тому, що в них частинукомбінацій коду або всі комбінації можуть бути отримані шляхом циклічногозсуву однієї або декількох комбінацій коду. Циклічний зсувздійснюється справа наліво, причому вкрай