Количественная оцінка информации

КІЛЬКІСНА ОЦІНКА ИНФОРМАЦИИ.

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

[pic]. (1).

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

[pic]. (2).

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

[pic] б) в десяткових единицах.

[pic] де [pic]; в) в натуральних единицах.

[pic] де [pic].

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

[pic] (3).

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

[pic] а кількість інформацією повідомленні, складеному з до неравновероятностных символов,.

[pic] (5).

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

[pic] (4).

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

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

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

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

[pic].

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

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

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

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

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

Якщо за передачі n повідомлень символ, А з’явився m раз, символ У з’явився l раз, а символ, А з символом У — до раз, то ймовірність появи символу, А [pic]; можливість появи символу У [pic]; ймовірність спільного появи символів Проте й У [pic]; умовна можливість появи символу Що ж до символу У і умовна можливість появи символу У щодо символу А.

[pic] (7).

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

[pic] (8).

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

[pic] (9).

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

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

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

[pic] (11).

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

Оскільки [pic]представляет собою ймовірність спільного появи двох подій [pic], то формула (11) можна записати наступним образом:

[pic] (12).

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

У випадку, коли ми передаємо m сигналів Проте й очікуємо отримати m сигналів У, вплив перешкод в каналі зв’язку повністю описується канальної матрицею, що її наводимо нижче: [pic].

|В | | |А |b1 b2 … bj | | |… bm | |а1 |[pic][pic][pic][pic][pic] | |А2 |… | |… | | |аi |[pic][pic] | |… |… | |аm | | | |[pic][pic] |.

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

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

[pic] (13) [pic](14) [pic](15) [pic](16) [pic].

|В | | |А |b1 b2 … bj | | |… bm | |а1 |[pic][pic][pic][pic][pic] | |А2 |… | |… | | |аi |[pic][pic] | |… |… | |аm | | | |[pic][pic] |.

[pic].

[pic](17) [pic](18) [pic] [pic](19) [pic] [pic] [pic] [pic] [pic].

[pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic].

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

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

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

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

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

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

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

Для обчислення часто зручно застосовувати висловлювання (26−28) як !!!

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

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

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

ТЕМА 5. ВИЗНАЧЕННЯ НАДМІРНОСТІ ПОВІДОМЛЕНЬ. ОПТИМАЛЬНЕ КОДИРОВАНИЕ.

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

[pic].

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

[pic] (45) де [pic]— коефіцієнт стискування (відносна энтропия). pic] і [pic] беруться щодо однієї й тієї ж алфавита.

Окрім загальної поняття надмірності існують приватні види избыточности.

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

[pic] (46).

Надмірність, викликана статистичної зв’язком між символами сообщения,.

[pic] (47).

Повна інформаційна избыточность.

[pic] (48).

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

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

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

[pic], де N — загальна кількість переданих сообщений.

L можна уявити і как.

[pic], де [pic] і [pic]—соответственно якісні ознаки первинного і вторинного алфавітів. Тож цифри 5 в двоичном коді можна записать.

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

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

[pic].

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

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

[pic] (50).

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

[pic] (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 символи первинного алфавіту виписуються у порядку спаду ймовірностей. Останні [pic] символів, де [pic][6] і [pic] - ціла кількість, об'єднують в певний новий символ з імовірністю, рівної сумі ймовірностей об'єднаних символів Останні символи з урахуванням освіченого символу знову об'єднують, отримують новий, допоміжний символ, знову виписують символи гаразд зменшення ймовірностей з урахуванням допоміжного символу тощо. буд. до того часу, поки сума ймовірностей т решти символів після [pic]-го виписування в порядку спаду ймовірностей дасть у сумі ймовірність, рівну 1. На практиці зазвичай, не виробляють багаторазового виписування ймовірностей символів з урахуванням ймовірності допоміжного символу, а обходяться елементарними геометричними побудовами, доцільність яких зводиться до того що, що символи кодованого алфавіту попарно об'єднують у нові символи, починаючи з символів, мають найменшу ймовірність. Потім із урахуванням знову освічених символів, яким присвоюється значення сумарною ймовірності попередніх, будують кодове дерево, в вершині якого стоїть символ з ймовірністю 1. У цьому зайвими в упорядочивании символів кодованого алфавіту у порядку спаду ймовірностей. Побудовані за зазначеними вище (або подібним) методикам коди з через нерівномірний розподіл символів, мають мінімальну середню довжину кодового слова, називають оптимальним, нерівномірним, кодами (ОНК). Рівномірні коди може бути оптимальними лише передачі повідомлень з равновероятным розподілом символів первинного алфавіту, у своїй число символів первинного алфавіту має бути одно цілої ступеня числа, рівного кількості якісних ознак вторинного алфавіту, а разі двійкових кодів — цілої ступеня двох. Максимально ефективними будуть ті ОНК, у которых.

[pic].

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

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

[pic].

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

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

[pic].

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

[pic].

ТЕМА 6. ВИЯВЛЕННЯ І ВИПРАВЛЕННЯ ПОМИЛОК У СООБЩЕНИЯХ.

Поняття з ідеєю корекції ошибок.

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

10 110 — передана кодова комбинация;

10 010 — 1-ша прийнята комбинация;

10 100 — -я прийнята комбинация;

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

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

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

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

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

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

У випадку щоб виявити r помилок мінімальне кодове расстояние.

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

[pic] (57) де p. s — число исправляемых ошибок.

Для кодів, лише які виправляють ошибки,.

[pic] (58).

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

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

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

[pic] (59).

[pic] 60) у своїй мається на увазі, що це загальна довжина кодовою комбинации.

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

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

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

[pic] (64) или.

[pic][pic] (65) Для кодів у п символів, які виправляють одну чи дві помилки [pic].

[pic] (66) Для практичних розрахунків можна скористатися выражением.

[pic] (67).

Для кодів, які виправляють 3 помилки [pic].

[pic] (68).

Для кодів, які виправляють p. s помилок [pic].

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

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

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

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

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

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

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

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

[pic].

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

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

[pic] (72).

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

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

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

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

[pic] званому лівої канонічної формою породжує матриці. Для кодів з [pic]=2 яка виробляє матриця З має вид.

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

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

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

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

[pic].

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

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

Вигляд синдрому кожної конкретної матриці то, можливо визначено при допомоги перевірочною матриці М, що дає транспонированную матрицю П, доповнену одиничної матрицею [pic], число шпальт якої одно числу перевірочних розрядів кода:

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

Таблиця 6.1.

[pic].

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

Вектори [pic] нічого не винні бути рівні жодному з векторів [pic], в іншому разі в таблиці чи з’явилися б нульові векторы.

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

Код Хэмминга.

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

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

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

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

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

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

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

Ідея побудови циклічних кодів виходить з використанні неприводимых в поле[14] двійкових чисел багаточленів. Неприводимыми називаються багаточлени, які можуть бути як твори багаточленів нижчих ступенів з коефіцієнтами із такого самого поля, як і, як прості числа неможливо знайти представлені твором інших чисел. Інакше кажучи, неприводимые багаточлени діляться на всі сто лише з себе" чи на единицу.

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

Припустимо, требуйся закодувати жодну з комбінацій чотиризначної двоичного коду. Припустимо також, що ця комбінація — [pic]. Поки що обгрунтовуючи свій вибір, беремо з таблиці неприводимых багаточленів (табл. 2, додаток 9) як утворить багаточлен [pic]. Потім помножимо [pic] на одночлен тієї мірі, як і утворюючий багаточлен. Від множення багаточлена на одночлен ступеня п ступінь кожного члена багаточлена підвищиться на [pic], що еквівалентно приписыванию [pic] нулів із боку молодших розрядів багаточлена. Оскільки ступінь обраного неприводимого багаточлена дорівнює трьом, то вихідна інформаційна комбінація збільшується на одночлен третьої степени:

[pic] Це робиться здобуття права згодом дома цих нулів можна було б записати коригувальні разряды.

Значення коригувальних розрядів знаходять за результатом від розподілу [pic] на [pic]: [pic] [pic] или.

[pic].

Таким образом,.

[pic] чи загальному виде.

[pic] (75) де [pic] - приватне, a [pic] - залишок від розподілу [pic] на [pic].

Позаяк у двоичной арифметиці [pic], отже, [pic], можна при додаванні двійкових чисел переносити складові з частині рівності в іншу без зміни знака (якщо це зручно), тому рівність виду [pic] можна записати як і [pic] як і [pic]. Усі три рівності у разі означають, або [pic] і [pic] рівні 0, або чи [pic] рівні 1, т. е. мають однакову четность.

Отже, вираз (75) можна записати как.

[pic] (76) у разі нашого прикладу даст.

[pic] или.

[pic].

Багаточлен 1 101 001 це і є бажана комбінація, де 1101 — інформаційна частина, а 001 — контрольні символи. Зауважимо, що потрібну комбінацію ми змогли б отримати як у результаті множення одній з комбінацій повного чотиризначної двоичного коду (у разі 1111) на утворює багаточлен, і множенням заданої комбінації на одночлен, має таку ж ступінь, як і обраний утворює багаточлен (у разі в такий спосіб отримали комбінація 1 101 000) з наступним додаванням до одержаному твору залишку від розподілу цього твору на утворює багаточлен (у нашій прикладі залишок мало вигляд 001). Отже, ми знаємо два способу освіти комбінацій лінійних систематичних кодів, до яких належать і цікаві для нас циклічні коди. Ці засоби з’явилися теоретичним основою побудови які кодують і декодирующих пристроїв. Шифратори циклічних кодів, у цьому чи іншій формі, побудовано за принципом множення двійкових багаточленів. Кодові комбінації виходять внаслідок складання сусідніх комбінацій по модулю два, що, як побачимо нижче, еквівалентно множенню першої комбінації на двочлен [pic]. Отже, комбінації циклічних кодів можна представляти як багаточленів, які мають показники ступеня [pic] відповідають номерам розрядів, коефіцієнти при x рівні 0 чи 1 залежно від цього, стоїть 0 чи 1 в розряді кодовою комбінації, якою є даний багаточлен. Например,.

[pic] Циклічний зрушення кодовою комбінації аналогічний множенню відповідного багаточлена на х:

[pic].

Якщо рівень багаточлена сягає розрядності коду, це відбувається «перенесення» в нульову ступінь при [pic]. У шифраторах циклічних кодів ця операція здійснюється шляхом сполуки виходу осередки старшого розряду зі входом осередки нульового розряду. Складання по модулю 2 будь-яких двох сусідніх комбінацій циклічного коду еквівалентно операції множення багаточлена відповідного комбінації першого доданка на багаточлен [pic] якщо приведення подібних членів здійснюється за модулю 2:

[pic] [pic].

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

Проте побудувати циклічний код. Треба вміти виділення з нього можливі помилкові розряди, т. е. запровадити деякі опознаватели помилок, які виділяли б помилковий блок із усіх інших. Оскільки циклічні коди — блочні, то кожен блок повинен мати свій опознаватель. І тоді вирішальну роль грають властивості утворить багаточлена [pic]. Методика побудови циклічного коду така, що утворюючий багаточлен бере участь у освіті кожної кодовою комбінації, тому будь-який багаточлен циклічного коду ділиться на утворює на всі сто. Але на всі сто поділяються лише ті багаточлени, які належать даному коду, т. е. утворюючий багаточлен дозволяє вибрати дозволені комбінації з усіх можливих. Якщо навіть за розподілі циклічного коду на утворюючий багаточлен отримають залишок, то отже або у коді відбулася помилка, чи це комбінація якогось іншого коду (заборонена комбінація), що з декодирующего устрою немає принципової різниці. По залишку і можна знайти наявність забороненої комбінації, т. е. можна знайти помилка. Залишки від розподілу багаточленів є опознавателями помилок циклічних кодов.

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

[pic][pic] починаючи з восьмого, залишки повторюватимуться. Залишки від розподілу використовують із побудови їхнім виокремленням матриць, які, завдяки їхній наочності і зручності отримання похідних комбінацій, отримали стала вельми поширеною для побудови циклічних кодів. Побудова котра утворює матриці зводиться до написання одиничної транспонованої і шляхом додаткової матриці, елементи якої представляють собою залишки від розподілу одиниці з нулями на утворює багаточлен [pic][15]. Нагадаємо, що одинична транспонированная матриця представляє собою квадратну матрицю, все елементи якої - нулі, крім елементів, розташованих по-діагоналі справа-наліво згори донизу (в нетранспонированной матриці діагональ з одиничними елементами розташована зліва-направо згори вниз). Елементи додаткової матриці приписують праворуч від одиничної транспонованої матриці. Проте чи все залишки від розподілу одиниці з нулями на утворюючий багаточлен можна використовувати як елементи додаткової матриці. Використовуватися можуть лише ті залишки, вагу яких [pic] де [pic] - мінімальне кодове відстань. Довжина залишків мусить бути щонайменше кількості контрольних розрядів, а число залишків має рівнятися числу інформаційних розрядів. Рядки котра утворює матриці є перші комбінації шуканого коду. Інші комбінації коду виходять внаслідок підсумовування по модулю 2 різноманітних поєднань рядків котра утворює матрицы[16]. Описаний вище метод побудови їхнім виокремленням матриць перестав бути єдиним. Утворює матриця то, можливо побудовано результаті безпосереднього множення елементів одиничної матриці на утворює багаточлен. Це це часто буває зручніше, ніж перебування залишків від розподілу. Отримані коди нічим немає від кодів, побудованих по що створює матрицями, у яких додаткова матриця складається з залишків від розподілу одиниці з нулями на утворює багаточлен. Утворює матриця то, можливо побудована також шляхом циклічного зсуву комбінації, отриманого результаті множення рядки одиничної матриці рангу [pic] на утворюючий багаточлен. На закінчення пропонуємо іще одна метод побудови циклічних кодів. Перевагою цього є виняткова простота схемних реалізації які кодують і декодирующих пристроїв. Для отримання комбінацій циклічного коду у разі досить зробити циклічний зрушення рядки котра утворює матриці і комбінації, що є її дзеркальним відображенням. При побудові кодів з [pic], [pic], [pic] число комбінацій, одержуваних підсумовуванням по модулю 2 різноманітних поєднань рядків котра утворює матриці, одно числу комбінацій, одержуваних у результаті циклічного зсуву рядки котра утворює матриці і дзеркальній їй комбінації. Однак це спосіб використовується щоб одержати кодів малим числом інформаційних розрядів. Вже за [pic] число комбінацій, одержуваних внаслідок циклічного зсуву, буде набагато меншою, ніж число комбінацій, одержуваних у результаті підсумовування різноманітних поєднань рядків котра утворює матриці. Кількість ненульових комбінацій, одержуваних у результаті підсумовування по модулю 2 різноманітних поєднань рядків котра утворює матрицы,.

[pic] (77) де [pic] - число інформаційних розрядів кода[17].

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

[pic].

(78) де [pic] - довжина кодовою комбінації. При числі інформаційних розрядів [pic] число комбінацій від підсумовування рядків котра утворює матриці зростає значно швидше, ніж число комбінацій, одержуваних у результаті циклічного зсуву рядки котра утворює матриці і дзеркальній їй комбінації. У разі коди виходять надмірними (бо за тієї самої довжини коду можна іншим чином передати більше кількість повідомлень), відповідно, падає відносна швидкість передачі. У разі доцільність застосування одного чи іншого методу кодування може бути оцінена з конкретних технічних умов. Помилки в циклічних кодах виявляються й у виправляють з допомогою залишків від розподілу отриманої комбінації на утворюючий багаточлен. Залишки від розподілу є опознавателями помилок, але з вказують безпосередньо цього разу місце помилки у циклічному коді. Ідея виправлення помилок виходить з тому, що помилкова комбінація після певної кількості циклічних зрушень «підганяється «під залишок таким чином, що сумарно із залишком вона дає виправлену комбінацію. Залишок у своїй є нічим іншим, як відмінність між перекрученими і правильними символами, одиниці поза стінами вузу стоять саме на місцях перекручених розрядів в підігнаної циклічними зрушеннями комбінації. Підганяють викривлену комбінацію до того часу, поки число одиниць на залишку нічого очікувати одно числу помилок в коді. У цьому, природно, число одиниць то, можливо або одно числу помилок [pic], исправляемых даним кодом (код виправляє 3 помилки й у перекрученою комбінації 3 помилки), або менше p. s (код виправляє 3 помилки, а прийнятої комбінації - 1 помилка). Місце помилки у кодовою комбінації має значення. Якщо [pic] то після певної кількості зрушень все помилки будуть у зоні «разового» дії утворить багаточлена, т. е. досить отримати один залишок, вагу якого [pic], цього вже буде достатньо виправлення перекрученою комбінації. У цьому сенсі коди БЧХ (про них говоритимемо нижче) можуть виправляти пачки помилок, аби довжина пачки не перевищувала s.

Побудова і декодування конкретних циклічних кодов.

I. Коди, исправляющие одиночну помилку, [pic]. 1. Розрахунок співвідношень між контрольними і інформаційними символами коду виготовляють підставі висловів (59) — (69). Якщо поставлено число інформаційних розрядів [pic], то число контрольних розрядів [pic] знаходимо з выражения.

[pic] Загальна кількість символів кода.

[pic] Якщо задана довжина коду [pic], то число контрольних разрядов.

[pic] Співвідношення числа контрольних та інформаційних символів для кодів з [pic] наведені у табл. 3 докладання 9. 2. Вибір утворить багаточлена проводиться у разі таблицям неприводимых двійкових багаточленів. Утворюючий багаточлен [pic] слід вибирати максимально коротким, але ступінь його має не менше ніж контрольних розрядів [pic], а число ненульових членів — незгірш від мінімального кодового відстані [pic]. 3. Вибір параметрів одиничної транспонованої матриці відбувається з умови, що кількість шпальт (рядків) матриці визначається кількістю інформаційних розрядів, т. е. ранг одиничної матриці дорівнює [pic]. 4. Визначення елементів додаткової матриці проводиться у разі залишкам від розподілу останньої рядки транспонованої матриці (одиниці з нулями) на утворюючий багаточлен. Отримані залишки повинні задовольняти наступним вимогам: а) число розрядів кожного залишку має бути одно числу контрольних символів [pic], отже, число розрядів додаткової матриці має бути одно ступеня утворить багаточлена; б) число залишків має не менше ніж рядків одиничної транспонованої матриці, т. е. має бути одно числу інформаційних розрядів [pic]; до одиниць кожного залишку, т. е. його вага, має не меншим величини [pic], де [pic] - мінімальне кодове відстань, одна з числа які виявляються помилок; р) кількість нулів, приписуваних до одиниці з нулями під час ділення в обраний неприводимый багаточлен, має бути такою, щоб дотримувалися умови а), б), в).

5. Утворює матриця складається дописуванням елементів додаткової матриці праворуч від одиничної транспонованої матриці або множенням елементів одиничної матриці на утворює многочлен.

6. Комбінаціями шуканого коду є рядки котра утворює матриці і всі можливі суми по модулю 2 різних поєднань рядків котра утворює матрицы.

7. Виявлення та виправлення помилок проводиться у разі залишкам від розподілу прийнятої комбінації [pic] на утворюючий багаточлен [pic]. Якщо прийнята комбінація ділиться на утворює багаточлен на всі сто, то код прийнято безпомилково. Залишок від розподілу свідчить про наявність помилки, але з вказує, що саме. Щоб знайти помилковий розряд і виправити їх у циклічних кодах, здійснюють такі операції: а) прийняту комбінацію ділять на утворює багаточлен і б) підраховують кількість одиниць на залишку (вагу залишку). Якщо [pic], де p. s — дозволене число исправляемых даним кодом помилок, то прийняту комбінацію складають по модулю 2 з отриманим залишком. Сума дасть виправлену комбінацію. Якщо [pic], то) виробляють циклічний зрушення прийнятої комбінації [pic] вліво однією розряд. Комбінацію, одержаний прибуток у результаті циклічного зсуву, ділять на [pic]. Якщо результаті повторного розподілу [pic] то подільне підсумовують із залишком, потім р) виробляють циклічний зрушення вправо однією розряд комбінації, отриманого результаті підсумовування останнього діленого з залишком. Отримана внаслідок комбінація не містить помилок. Якщо після першого циклічного зсуву і наступного розподілу залишок виходить таким, що його вага [pic], то буд) повторюють операцію пункту з) до того часу, поки що не [pic]. У цьому вся разі комбінацію, отриманий прибуток у результаті останнього циклічного зсуву, підсумовують із залишком від розподілу цієї комбінації на утворюючий багаточлен, а потім е) виробляють циклічний зрушення вправо рівно настільки розрядів, на скільки була зрушена суммируемая з залишком комбінація щодо прийнятої комбінації. Через війну одержимо виправлену комбинацию[18].

II. Коди, обнаруживающие трехкратные помилки, [pic]. 1. Вибір числа коригувальних розрядів робиться з соотношения.

[pic] или.

[pic] 2. Вибір утворить багаточлена виробляють, виходячи з таких міркувань: щоб виявити триразовій ошибки.

[pic] тому ступінь утворить багаточлена може бути менше чотирьох; багаточлен третього ступеня, має •число ненульових членів більше або однакову трьом, дозволяє виявляти все подвійні помилки, багаточлен першої ступеня [pic] виявляє скільки завгодно непарних помилок, отже, багаточлен четвертого ступеня, отримуваний внаслідок множення цих багаточленів, має їх корректирующими властивостями: може виявляти дві помилки, і навіть один, і три, т. е. все трехкратные ошибки.

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

4. Інші комбінації коригувального коду знаходять підсумовуванням по модулю 2 різноманітних поєднань рядків котра утворює матрицы.

5. Виявлення помилок проводиться у разі залишкам від розподілу прийнятої комбінації [pic] на утворює багаточлен [pic]. Якщо залишку немає, то контрольні розряди відкидаються і інформаційна частина коду використовується за призначенням. Якщо результаті розподілу виходить залишок, то комбінація бракується. Зауважимо, такі коди можуть виявляти 75% будь-якого кількості помилок, оскільки крім подвійний помилки виявляються все непарні помилки, але гарантоване кількість помилок, яке код будь-коли пропустить, одно 3.

Приклад: Вихідна кодова комбінація — 101 111 000, прийнята — 1 011 001 (т. е. стався потрійний збій). Показати процес виявлення помилки, якщо відомо, що комбінації коду створили з допомогою багаточлена 101 111.

Решение:

[pic].

Остаток не нульової, комбінація бракується. Вказати помилкові розряди при триразових викривлення такі коди не могут.

III. Циклічні коди, исправляющие дві й більше кількість помилок, [pic] Методика побудови циклічних кодів з [pic] відрізняється від методики побудови циклічних кодів з [pic] тільки у виборі утворить багаточлена. У літературі ці коди відомі як коди БЧХ (перші літери прізвищ Боуз, Чоудхури, Хоквинхем — авторів методики побудови циклічних кодів з [pic]). Побудова утворить багаточлена залежить, переважно, від двох параметрів: від довжини кодового слова п. і зажадав від числа исправляемых помилок p. s. Інші параметри, що у побудові утворить багаточлена, в залежність від заданих [pic] і [pic]могут визначити з допомогою таблиць та допоміжних співвідношень, про які буде вказано нижче. Для виправлення числа помилок [pic] ще досить умови, щоб між комбінаціями коду мінімальне кодове відстань [pic]. слід також, щоб довжина коду [pic] задовольняла условию.

[pic].

(79) у своїй п завжди буде непарною числом. Розмір h визначає вибір числа контрольних символів [pic] і пов’язана з [pic] і p. s наступним соотношением:

[pic] (80) З іншого боку, число контрольних символів визначається що створює многочленом і одно його ступеня. При великих значеннях h довжина коду п стає дуже великі, що викликає цілком конкретні труднощі при технічної реалізації які кодують і декодирующих пристроїв. У цьому частина інформаційних розрядів часом залишається невикористаної. У разі визначення h зручно користуватися вираженням [pic] (81) де [pic] одна із сомножителей, куди розкладається число п.

Співвідношення між [pic], З повагою та h може бути зведені в таку таблицю |№ |h |[pic] |З | |п/п | | | | |1 |3 |7 |1 | |2 |4 |15 |5; 3 | |3 |5 |31 |1 | |4 |6 |63 |7; 3; 3 | |5 |7 |127 |1 | |6 |8 |255 |17; 5; 3 | |7 |9 |511 |7; 3; 7 | |8 |10 |1023 |31; 11; 3 | |9 |11 |2047 |89; 23 | |10 |12 |4095 |3; 3; 5; 7; | | | | |13 |.

Наприклад, при h = 10 довжина кодовою комбінації може дорівнювати і 1023 [pic] і 341 (З = 3), і 33 (З =31), і 31 (З = 33), зрозуміло, що п неспроможна менше [pic] Розмір З впливає вибір порядкових номерів мінімальних багаточленів, оскільки індекси спочатку вибраних багаточленів множаться на З. Побудова утворить багаточлена [pic] виробляється з допомогою так званих мінімальних багаточленів [pic], що є простими неприводимыми многочленами (див. табл. 2, додаток 9). Утворює багаточлен є твір непарних мінімальних багаточленів і був частиною їхнього найменшим загальним кратним (НОК). Максимальний порядок [pic] визначає номер останнього зі выбираемых табличных мінімальних многочленов.

[pic].

(82) Порядок багаточлена використовується щодо числа сомножителей [pic]. Наприклад, якщо p. s = 6, то [pic]. Оскільки для побудови [pic] використовуються лише непарні багаточлени, то ними будуть: [pic] старшого із них має порядок [pic]. Як кажуть, число сомножителей [pic] одно 6, т. е. числу исправляемых помилок. Отже, число мінімальних багаточленів, що у побудові утворить многочлена,.

[pic].

(83) а старша степень.

[pic].

(84) ([pic] вказує колонку в таблиці мінімальних багаточленів, з якої зазвичай вибирається багаточлен для побудови [pic]). Ступінь утворить багаточлена, отриманого внаслідок перемножения вибраних мінімальних многочленов,.

[pic] (85) Загалом виде.

[pic] (86) Декодування кодів БЧХ проводиться у разі тієї ж методиці, як і декодування циклічних кодів з [pic]. Проте у про те, що майже всі коди БЧХ представлені комбінаціями з [pic], можуть виникнути дуже складний варіанти, коли щоб виявити і виправлення помилок необхідно здійснювати велика кількість циклічних зрушень. У цьому вся разі для полегшення можна комбінацію, отриману після [pic]-кратного зсуву і підсумовування із залишком, зрушувати не вправо, а вліво на [pic] циклічних зрушень. Це доцільно робити не тільки при [pic].

ТЕМА 8. СТИСНЕННЯ ИНФОРМАЦИИ.

Стиснення інформації є операцію, у яких даному коду чи повідомленню ставлять у відповідність коротший код чи сообщение[19]. Стиснення інформації має своєю метою — прискорення і здешевлення процесів механізованої обробки, збереження і пошуку інформації, економія пам’яті ЕОМ. При стискуванні слід йти до мінімальної неоднозначності стиснутих кодів за максимальної простоті алгоритму стискування. Розглянемо найбільш характерні методи стискування інформації. Стиснення інформації розподілом коду на частини, менші деякою наперед заданої величини А, у тому, що вихідний код ділиться на частини, менші Затим чого отримані частини коду складаються між собою або за правилами. двоичной арифметики, або за модулю 2. Наприклад, вихідний код 101 011 010 110; A = 4.

[pic] [pic].

Стиснення інформації з побуквенным зрушенням у кожному розряді [5], як і попередній спосіб, коштів відновлення стисливих кодів, а застосовується тільки до скорочення адреси або самого коду стисливого слова в пам’яті ЭВМ.

Припустимо, вихідне слово «газета» кодується кодом, у якому довжина кодовою комбінації літери l = 8: Р — 1 000 111; а — 11 110 000; із — 1 100 011; е — 10 111; т — 11 011 000.

Повний код слова «Газета».

10 001 111 111 000 001 169 071 233 486 536 760 005 366 906 880. Стиснення здійснюється складанням по модулю 2 двійкових кодів літер стисливого слова з побуквенным зрушенням у кожному разряде.

[pic].

[pic].

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

[pic].

(88) де [pic] - максимально допустима довжина (кількість двійкових розрядів) стиснутого коду; N — можливу кількість адрес в ЗУ. Якщо уявити процес побуквенного зсуву загалом, як показано на рис. 1, бо довжина стиснутого кода.

[pic] де k — число побуквенных зрушень; [pic] - довжина кодовою комбінації буквы.

Оскільки зсуваються всі букви, крім першої, те й число зрушень [pic], де L — число літер у слові. Тогда.

[pic].

У російській мові найбільш довгі слова мають 23 — 25 літер. Якщо прийняти це [pic], з вимогою здійснення побуквенного зсуву з кожним кроком рівно на один розряд, для n і l можна отримати такі соотношения.

[pic] Якщо значення [pic] не задовольняє нерівності (88), можна кінцеві літери слова складати по модулю 2 без зсуву щодо попередньої літери, як і показано на рис. 1, б. Наприклад, для попереднього прикладу щодо слова «Газета» [pic], стиснений код матиме вид:

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

[pic] Згорнений масив матиме вид:

[pic] Розшифровка (розгортання) приміром із кінця масиву. Перехід на наступний рядок відбувається за двома умовам: або за заповнення рядки, або за зустрічі [pic].

[pic].

Пропущені цифри заповнюються автоматично по аналогічним розрядам попередньої рядки. Заповнення здійснюється з початку масиву. Цей метод можна розвинути також для згортання масивів, у яких повторювані розряди зустрічаються лише з початку рядки. Якщо рядку один який повторювався ділянку, то крім [pic] додається ще одна додатковий символ До, що означає кінець рядки. Розшифровка тягнеться з До до До. Довжина рядки відома. Потрібно, щоб було закрито між K цифри разом із пропущеними розрядами становили повну рядок. У цьому нас усе одно, де рядки викидаються повторювані розряди, аби в рядку було більше однієї дільниці з повторюваними розрядами. Например:

[pic].

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

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

[pic] Пропущені цифри заповнюються по аналогічним розрядам попередньої рядки починаючи з кінця масиву. Якщо рядку масиву кілька повторюваних ділянок, можна замість [pic] вставляти спеціальні символи, що вказують на необхідну кількість перепусток. Наприклад, якщо позначити кількість перепусток, відповідно, Х — 2; Y — 3; Z — 5, то вихідний і згорнений масиви матимуть вид:

[pic] Процес розгортання масиву здійснюється так: довжина рядки відома, кількість перепусток визначається символами X, Y, Z.

[pic] Пропущені цифри заповнюються по аналогічним розрядам попередньої рядки. Умовою переходу для наступної рядок є заповнення попередньої строки.

Метод Р. У. Лівінського грунтується у тому, що у пам’яті машини зберігаються стислі числа, розрядність котрих значно менша розрядності реальних чисел. Ефект стискування досягається завдяки тому, що послідовності попередньо упорядкованих чисел розбиваються на цілий ряд рівних відрізків, всередині яких відлік ведеться за їх абсолютну величину, як від кордону попереднього відрізка. Розрядність чисел, одержуваних в такий спосіб, природно, менше розрядності відповідних реальних чисел [18, 21]. Для розміщення у пам’яті ЕОМ М кодів, у яких найбільше з кодованих чисел одно N, необхідний обсяг памяти.

[pic] Зі збільшенням N довжина кодовою комбінації зростатиме як [pic]. Для економії обсягу пам’яті Q, число [pic], де вираження у дужках — округлене значення [pic] до найближчого цілого числа, розбивають на L рівних частин. Максимальне число в отриманому інтервалі чисел буде більше [pic]. Величина [pic] визначає розрядність збережених чисел, обсяг пам’яті їхнього зберігання буде більше [pic]. Якщо пам’яті ЕОМ зберігати адреси кордонів відрізків і порядкові номери збережених чисел, що обчислюються від чергової кордону, то [pic] визначає розрядність чисел висловлення номери кордону (у тому інтервалі має бути хоча одне число); обсяг пам’яті для зберігання номерів кордонів буде [pic] де [pic] - число кордонів між відрізками (їх кількість завжди на одиницю менше, ніж число відрізків). Загальний обсяг пам’яті цьому буде не больше.

[pic] (89).

Щоб знайти, яких L вираз (89) приймає мінімальне значення, досить продифференцировать його за L і, прирівняти похідну нанівець. Неважко переконатися, що [pic] буде при.

[pic][20] (90) Якщо підставити значення [pic] в вираз (89), одержимо. значення обсягу пам’яті за оптимального кількості зон, на, які розбиваються збережені у пам’яті ЕОМ числа,.

[pic] (91) Для значень [pic] при обчисленнях можна скористатися наближеною формулой.

[pic] (92) Під час пошуку інформацією пам’яті ЕОМ передусім визначають значення [pic] і знаходять величину інтервалу між двома границами.

[pic] Потім визначають, якому саме з інтервалів перебуває дані число х.

[pic] Після цього визначається адресу шуканого числа як різницю між абсолютним значенням числа і кількістю, що є граничним для даного інтервалу. ———————————- [1] Первинний алфавіт складається з m1 символів (якісних ознак), з яких записано передане повідомлення. Вторинний алфавіт складається з m2 символів, з яких повідомлення трансформується на код. [2] У принципі, обсягу інформації немає. Ми вкладаємо у цей термін те що призвичаїлися під цим розуміти, — кількість елементарних символів у прийнятому (вторинному) повідомленні. [3] Суть взаємозалежності символів літер абетки у тому, що можливість появи i-го літери на місці повідомлення залежить від цього, які літери стоять перед з нею й після неї, і надто відрізнятиметься від безумовною ймовірності pi, відомої з статистичних властивостей даного алфавита.

" Розгляд семантичної надмірності не входить у завдання теорії информации.

[4] Тут і далі, під терміном «оптимальний код» матимемо на увазі коди з нульової надмірністю, оскільки порівнюємо довжину кодовою комбінації з ентропія джерела повідомлень, без урахування взаємозалежність символів. З урахуванням взаємозалежності символів ефективність кодування ніколи 100%, т. е.

[pic].

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

[5] т—-число якісних ознак споруджуваного оптимального кода.

[6] З основний теоремою кодування для каналів зв’язку без шумів можна ознайомитися у роботі До. Шеннона «А роботи з теорії інформації та кібернетиці* або у популярному викладі на роботах [18, 22].

[7] Розглянутий принцип закладений у основу мажоритарного декодування.- коригувальних кодів і відомий як засіб Бодо—Вердана.

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

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

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

[pic].

[11] «Оптимальним коригувальним кодом для симетричного каналу називається груповий код, під час використання якого ймовірність помилки не більше, чеу під час використання лю5ого іншого коду із п» і Лц [1, 2, б]. У цих кодів критерій оптимальності немає нічого спільного з критерієм оптимальності ОНК.

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

[13] Спрощено, безліч елементів належить одного полю, якщо над ними можна робити операції складання і множення за правилами даного поля, у своїй складання і множення мають підкорятися дистрибутивному закону [pic] всім [pic] і [pic].

[14] Про можливість уявлення лінійного коду як одиничної і деякою додаткової матриці див., наприклад, [22, з. 408, 409].

[15] Треба сказати, що не циклічні коди можна отримати такою простою способом, проте будемо поки ускладнювати изложение.

[16] [pic] можна визначати й за такою формулою [pic].

[17] Коди з d0 = 2, обнаруживающие одиночну помилку, тут свідомо не розглядаються, оскільки вони мають практичного значення. У двійкових кодах завжди простіше підібрати контрольний символ 0 чи 1 в такий спосіб, щоб сума одиниць на кодовому слові була четной, ніж будувати циклічний код щоб одержати тієї самої результата.

[18] Кодування від стискування особливий тим, що коди майже завжди довші кодованих повідомлень, оскільки кількість якісних ознак вторинного алфавіту (коду) звичайно буває більшою за кількість якісних ознак первинного алфавіту (кодованих повідомлень). Говорячи «стиснений код», будемо пам’ятати комбінацію, представляє кодируемое поняття після процедури сжатия.

[19] При M.