АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Надлишкові коди

Читайте также:
  1. Визначення зовнішніх і внутрішніх надлишкових тисків
  2. Економічна думка в період становлення національних держав
  3. Згортальні двійкові коди
  4. І розподіл доходів
  5. КОЛІСНІЧЕНКО Наталії 7 страница
  6. Коректні прийоми ведення суперечок
  7. КРУГОВОРОТ РЕЧОВИН У БІОСФЕРІ
  8. Моделі оптимізації коштів
  9. Особливості наукового тексту і професійного наукового викладу думки. Мовні засоби наукового стилю
  10. Оцінка результатів роботи госпрозрахункових ветеринарних підприємств
  11. Подласый И. П. Курс лекций по коррекционной педагогике. Для средних специальных учебных заведений. – M.: Владос, 2002

 

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

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

 

N0 = mn , (3.7)

 

де m – основа коду;

n - значимість коду (кількість символів в кодовій комбінації),

а тільки деяких їх частин:

N<N0 (3.8)

Комбінації, що використовуються в даному коді, називаються дозволеними, а ті, що не використовуються – забороненими. Перетворення дозволеної комбінації в заборонену в результаті дії перешкоди виявляє існування помилки. Однак, якщо одна дозволена комбінація перетворюється в іншу дозволену комбінацію, то помилка виявлена не буде. Таким чином, будь-який код, що задовільняє умову (3.8), здатен виявити N(N0-N) помилок з їх можливої кількості N(N0-1). Відношення виявлених кодом помилкових комбінацій до всіх можливих помилок складає

. (3.9)

Аналогічно справа ведеться з виправленням помилок. Для використання коду в якості виправляючого потрібно виконати розбиття множини заборонених кодових комбінацій N0 – N на N підмножин Mi, що не перетинаються (рис. 3.1). Кожна з цих підмножин приписується до своєї дозволеної кодової комбінації. Виправлення полягає в тому, що дану заборонену комбінацію завжди приймають за ту дозволену комбінацію, до якої дана заборонена комбінація приписана. Таким чином, відношення помилок, що виправляються, до всіх можливих помилок складає:

 

(3.10)


а до всіх помилок, що виявлені

 
 

(3.11)

 

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

 

 


Ak Bj Mk

 
 

 

Рисунок 3.1 – Можливий розподіл заборонених кодових комбінацій за дозволеними.

 

Таблиця 3.3 – Виправлення помилок нищої кратності

Вектор помилки Дозволені комбінації
       
Прийняті комбінації
0001 0010 0100 1000 0000 0011 0101 1001 0100 0111 0001 1101 1111 1100 1010 0110 1110 1101 1011 0111
0011 0101 1001 0110 1010 1100 0010 0100 1000 0111 1011 1101 0110 0000 1100 0011 1111 1001 1101 1011 0111 1000 0100 0010 1100 1010 0110 1001 0101 0011
0111 1011 1101 1110 0110 1010 1100 1111 0010 1110 1000 1011 1001 0101 0011 0000 1000 0100 0010 0001
1111 1110 1010 0001 0000

 

Викладене ілюструє табл.3.3. В ній показано дію всіх можливих помилок на випадково вибрані дозволені комбінації чотиризначного коду. Введений вектор помилки треба розуміти так: 0 – помилки нема; 1 – помилка є. Прийнята комбінація отримується шляхом складання передачі і помилки. Правила складання:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

В розглянутому прикладі:

кількість можливих комбінацій N0 = mn =24=16;

кількість векторів помилок Nпом =mn-1=24-1=15;

кількість можливих помилок N(N0-1) = 4(16-1) = 60;

кількість виявлених помилок N(N0-N)=4(16-4)= 48(80%);

кількість невиявлених помилок (комбінації, підкреслені в таблиці)

N(N0-1) - N(N0-N) = 60-48 = 12(20%);

кількість помилок, що не виправляються

N(N0-1) - (N0-N) = 60-12=48 (80%).

Спосіб виправлення помилок повинен забезпечити мінімум їх середньої ймовірності. Тому розбиття заборонених кодових комбінацій (помилки, що можна виправити) на підгрупи відбувається в залежності від статистики помилок. У випадку, якщо в каналі зв’язку діють переважно взаємонезалежні помилки, їх ймовірність зменшується із збільшенням кратності помилки q. При такому положенні в першу чергу треба виправляти помилки нижчої кратності. Для прикладу, приведенного в таблиці 3.3, це зводиться до розподілу, що показане в табл. 3.4, в якій до дозволених комбінацій перш за все приписані помилки з кратністю q =2 і т.д. Множини заборонених кодових комбінацій, що приписуються дозволеним кодовим комбінаціям не повинні бути взаємоперетинаючими. Тому у випадку попадання однієї забороненої комбінації в дві множини її залишають тільки в одній з них, довільно вибраній.

Таблиця 3.4 – Виправлення пакетних помилок

Дозволені комбінації
       
Приписані заборонені комбінації
    1101     0111
  0010     1000  
             

 

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

Таблиця 3.5-Виправлення помилок

Дозволені комбінації
       
Приписані заборонені комбінації
 
       
1101      
         

 

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

1 2 3 4

1 0 1 4 3

2 0 3 2

3 0 1

4 0

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

 

101

 
 

 

Рисунок 3.2- Геометрична інтерпретація двійкового коду

а)–двозначного; б)–трьохзначного; в) – чотиризначного

 

Розглядаючи двійковий код з геометричної точки зору (звідки і взяли термін “віддаль”), кожну кодову комбінацію ми можемо уявити собі як одну з вершин куба, існуючого в n – мірному просторі, де n відповідає значимості коду. Якщо виходити з такого припущення, то кодова відстань двійкового коду буде дорівнювати найменшому числу ребер одиничного куба, що відділяють одну кодову комбінацію від іншої (рис.3.2). Вибір складу множин заборонених комбінацій, що приписуються до дозволених, зводиться до вибору власних областей в просторі сигналів.

Із поняття кодової віддалі ρ випливає, що для виявлення всіх одиничних помилок (тобто помилок з q = 1) необхідно і достатньо, щоб ρ ≥2, а для виявлення всіх помилок кратності qd величина ρ повинна відповідати нерівності

ρ ≥ qd +1. (3.12)

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

ρ ≥2 qс + 1. (3.13)

Для того, щоб код міг виправляти всі помилки з кратністю ≤ qс і одночасно виявляти всі помилки з кратністю ≤ qd, достатньо, щоб кодова відстань виконувала умову

ρ ≥ qс + qd +1. (3.14)

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

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

Поряд із застосуванням виправляючих кодів визначене розповсюдження одержали так звані дешифратори (канали) із стиранням (erasure channel). Особливість цих дешифраторів в тому, що їх розв’язуючий пристрій має область невизначеності, в яку попадають всі сумнівні сигнали. Крім символів двійкового коду 0 і 1 на виході такого пристрою може з’явитися також символ невизначеності, або стирання, 0. Зміст викладеного в тому, що встановити стерті знаки при повній надійності решти легше, ніж виправити помилкові. При заданій кодовій відстані ρ найбільша кратність відновлюваних стирань t рівна кратності помилок, які виявлені, т.б.

ρ ≥ t + 1. (3.15)

Щоб код міг одночасно виправити qс помилок і відновити t стертих символів, достатньо, щоб кодова відстань виконувала умову

ρ ≥ qс + t + 1. (3.16)

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

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

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

До найбільш поширених блочних кодів відносяться систематичні і циклічні коди. Поняття “ систематичний код” тут застосоване в найвужчому його понятті. Обидва ці коди подільні, т.б. символи, які входять в їх кодові комбінації, що діляться на основні, або інформаційні, і контрольні, або провірочні. Кожна з цих груп символів у всіх кодових комбінаціях (векторах) займає одні і тіж позиції. Роздільні коди звичайно позначаються, як (n, k) – коди,

де n – значність коду,

k–число інформаційних символів в кодовій комбінації.

Кожний рівномірний надлишковий блочний код складається виходячи з кількості кодуючих елементів N і вимог, які пред’являються до виправляючої здатності коду, які визначають кодову відстань ρ (формули (3.13), (3.14)).

З виразу

N = 2k (3.17)

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)