Міністерство освіти РФ
Пермський Державний Технічний Університет
Кафедра автоматизації і телемеханіки
КОНТРОЛЬНА РОБОТА З ПРЕДМЕТУ:
МЕРЕЖІ ЕОМ
Виконала студентка
Суханова С. А.
Гр. КК-04з, МТФ
Перевірив викладач
Кузнєцов І. І.
2007
Зміст
1. Циклічні коди. Основні поняття і визначення. Побудувати породжує матрицю циклічного коду з g (х) = 1 + х + х * 3
1.1 Циклічні коди
1.2 Основні параметри циклічних кодів
1.3 Основні поняття та визначення
1.4 Побудувати породжує матрицю циклічного коду з g (х) = 1 + х + х * 3
2. Поняття відкритої системи
2.1 Модель OSI
2.2 Поняття В«відкритої системиВ»
Список літератури
1. Циклічні коди. Основні поняття та визначення. Побудувати породжує матрицю циклічного коду з g (х) = 1 + х + х * 3
1.1 Циклічні коди
Циклічні коди - це ціле сімейство завадостійких кодів, що включає в себе в якості одного з різновидів кодів Хеммінга, але в цілому забезпечує велику гнучкість з точки зору можливості реалізації кодів з необхідною здатністю виявлення та виправлення помилок, визначуваної параметром d0, в порівнянні з кодами Хеммінга (для яких d0 = 3 або d0 = 4). Одним із класів циклічних кодів, здатність виправляти багатократні помилки, є коди БЧХ. Широке використання циклічних кодів на практиці обумовлено також простотою реалізації відповідних кодерів і декодерів. Основні властивості і само назву циклічних кодів пов'язані з тим, що всі дозволені комбінації біт в переданому повідомленні (кодові слова) можуть бути отримані шляхом операції циклічного зсуву деякого вихідного кодового слова:
Циклічні коди задаються за допомогою так званих породжують поліномів (многочленів) g (x) ступеня r = nk, що є співмножником двочлена x n +1, і їх коренів. Крім того, вводяться поняття полінома вихідного повідомлення. Для цих поліномів, представляють собою, по суті, альтернативну запис чисел у двійковій системі числення, визначаються операції додавання, множення і ділення, необхідні для організації кодування й декодування повідомлення. Всі ці операції виконуються по модулю 2.
Кодові слова представляються у вигляді многочленів:
1.2 Основні параметри циклічних кодів
Довжина коду - n; Довжина інформаційної послідовності - k; Довжина перевірочної послідовності - r = nk; Кодове відстань коду - d 0 ; Швидкість коду - R = k/n; Надмірність коду - R п‚ў; Імовірність виявлення помилки (Спотворення) - Р ГО ; Вірогідність не виявлення помилки (спотворення) - Р АЛЕ . - Коефіцієнти з поля GF (q).
1.3 Основні поняття та визначення
Кодове відстань між двома кодовими словами (відстань Хеммінга) - це число позицій, в яких вони відрізняються один від одного. Кодове відстань коду - це найменша відстань Хеммінга між різними парами кодових слів. Основні залежності між кратністю виявляються помилок t 0 , що виправляються помилок t u , виправленням стирань t c і кодовою відстанню d 0 коду:
стирання називається "втрата" значення переданого символу в деякій позиції кодового слова, яка відома. Код, в якому кожне кодове слово починається з інформаційних символів і закінчується перевірочними символами, називається систематичним. Якщо код побудований над полем GF (2), то коефіцієнти приймають значення 0 або 1 і код називається двійковим. Довжина циклічного коду називається примітивною і сам код називається примітивним, якщо його довжина n = q m -1 над GF (q). Якщо довжина коду менше довжини примітивного коду, то код називається укороченим або непрімітівним. Загальна властивість кодових слів циклічного коду - це їх подільність без залишку на деякий многочлен g (x), званий породжує. Результатом ділення двочлена x n +1 на многочлен g (x) є перевірочний многочлен h (x). При декодуванні циклічних кодів використовуються многочлен помилок e (x) і синдромний многочлен S (x). Многочлен помилок ступеня не більше (n-1) визначається з виразу
де - многочлени, відображають відповідно прийняте (з помилкою) і передане кодові слова. Ненульові коефіцієнти в е (x) займають позиції, які відповідають помилкам. Синдромний многочлен, використовуваний при декодуванні циклічного коду, визначається як залишок від ділення прийнятого кодового слова на породжує многочлен, тобто
або
Отже, синдромний многочлен залежить безпосередньо від многочлена помилок е (х). Це положення використовується при побудові таблиці синдромів, застосовуваної в процесі декодування. Ця таблиця містить список многочленів помилок і список відповідних синдромів, обумовлених з виразу (див. таблицю 4).
Таблиця 4
(x)
S (x)
1
R g (x) [1]
X
R g (x) [x]
X 2
R g (x) [x2]
п‚·
п‚·
п‚·
п‚·
п‚·
п‚·
X +1
R g (x) [x +1]
X 2 +1
R g (x) [x2 +1]
п‚·
п‚·
п‚·
п‚·
п‚·
п‚·
В процесі декодування за прийнятим кодовому слову обчислюється синдром, потім в таблиці знаходиться відповідний многочлен е (х), підсумовування якого з прийнятим кодовим словом дає виправлене кодове слово, тобто
Перераховані многочлени можна складати, множити і ділити, використовуючи відомі правила алгебри, але з приведенням результату за модулем 2, а потім по модулю x n +1, якщо ступінь результату перевищує ступінь (n-1). Приклади.
Припустимо, що довжина коду n = 7, то результат наводимо по модулю x 7 +1.
При побудові та декодуванні циклічних кодів в результаті ділення многочленів зазвичай необхідно мати не приватне, а залишок від ділення. Тому рекомендується більш простий спосіб розподілу, використовуючи не многочлени, а тільки його коефіцієнти (Варіант 2 в прикладі).
Приклад.
1. 2.
Циклічний код може бути заданий породжує g (x) і перевірочної h (x) матрицями. Для побудови достатньо знати породжує і перевірочний многочлени. Для не систематичного циклічного коду матриці будуються циклічним зрушенням породжує і перевірочного многочленів, тобто шляхом їх множення на х.
Одна з основних завдань, що стоять перед розробниками пристроїв захисту від помилок при передачі дискретних повідомлень по каналах зв'язку є вибір породжує багаточлена для побудови циклічного коду, забезпечує необхідну мінімальна код...
