ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

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

     

    Інформатика, програмування

    АП-97161

    АНОТАЦІЯ

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

    АП-97161

    ЗМІСТ

    1. Введення
    .................................................. ..........................< br>............... 6
    2. Постановка завдання
    .................................................. ........................< br>7
    3. Операції над циклічними кодами
    ............................................. 8
    4. Принцип побудови циклічних кодів
    ....................................... 9
    4.1. Отримання кодової комбінації додаванням залишку R (x) ...... 11
    4.2. Отримання кодової комбінації множенням на який утворює поліном
    .................................................. ..........................< br>.............. 14
    5. Розробка схеми алгоритму
    .................................................. ......... 15
    6. Розробка тексту програми
    .................................................. ....... 16
    7. Результати роботи програми
    .................................................. ..... 21
    -------------------------------------------------- --------------------------< br>------------------------

    Література
    .................................................. ..........................< br>............ 23

    Додаток № 1
    .................................................. ..........................< br>... 24

    Додаток № 2
    .................................................. ..........................< br>... 30

    § 1 Введення

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

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

    Циклічний код відноситься до лінійних, блокових, коригувальних,рівномірним кодами.

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

    Циклічні коди є різновидом систематичних кодіві тому володіють усіма їхніми властивостями. Спочатку вони були створені дляспрощення схем кодування та декодування. Їх ефекти -вність при виявленні та виправлення помилок забезпечила їм шіроеоезастосування на практиці.

    Циклічні коди використовуються в ЕОМ при послідовній передачіданих.

    (2 Постановка завдання

    Побудувати циклічний код для передачі 31 розрядної кодової комбінаціїз виправленням одноразової помилки (n = 31, s = 1) двомаспособами.

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

    (3 Операції над циклічними кодами

    1. Зрушення справа наліво здійснюється шляхом множення полінома на x:

    G (x) = x4 + x2 +1 (0010101;

    G (x) (x = x5 + x3 + x (0101010.

    2. Операції додавання і віднімання виконуються за модулем 2.
    Вони є еквівалентність та асоціативними:

    G1 (x) + G2 (x) => G3 (x);

    G1 (x)-G2 (x) => G3 (x );

    G2 (x) + G1 (x) => G3 (x);
    Приклад:

    G1 (x) = x5 + x3 + x;

    G2 (x) = x4 + x3 1;

    G3 (x) = G1 (x) (G2 (x) = x5 + x4 + x +1.

    3. Операція поділу є звичайним поділом многочленів, тількизамість віднімання використовується додавання по модулю 2:

    G1 (x) = x6 + x4 + x3;

    G2 (x) = x3 + x2 +1.

    x6 + x4 + x3 x3 + x2 +1

    (x6 + x5 + x3 x3 + x2 x5 + x4

    (x5 + x4 + x2 x2те ж у двійковому коді:

    1011000 1101

    (1101 1100

    1100

    (1101

    100

    Всі операції легко реалізуються апаратно на регістрах зсуву зазворотними зв'язками.

    (4 Принцип побудови циклічних кодів

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

    Щоб зрозуміти принцип побудови циклічного коду, множимо комбінаціюпростого k-значного коду Q (x) на Одночлен xr, а потім деліна створюючийполіном P (x), ступінь якого дорівнює r. У результаті множення Q (x) на xrступінь кожного Одночлен, що входить в Q (x), підвищена щує на r. При розподілітвори xrQ (x) на створюючий поліном виходить приватне C (x) такий жемірою, як і Q (x). Результат можна представити у вигляд

    Q (x) xr R (x)

    ((((= C (x) + ((( , (1)

    P (x) P (x)де R (x) - залишок від ділення Q (x) xr на P (x).
    Приватне C (x) має таку ж ступінь, як і кодова комбінація Q (x) простогокоду, тому C (x) є кодовою комбінацією цього жпостів k-значного коду. Слід зауважити, що ступінь залишку не може бутибільше мірі утворює полінома, тобто його найвищий ступінь може бутидорівнює (r-1). Отже, найбільше число розрядів залишку R (x) неперевищує числа r.
    Множачи обидві частини рівності (1) на P (x) і зробивши деякі перестановкиотримуємо:

    F (x) = C (x) P (x) = Q (x) xr + R (x) (2)
    Таким чином, кодова комбінація циклічного n-значного коду можебути отримана двома способами:

    1) множення кодової комбінації Q (x) простого коду на Одночлен xrі додавання до цього твору залишку R (x), отриманого в результатіподілу твори Q (x) xr на який утворює полином P (x);

    2) множення кодової комбінації C (x) простого k-значного на який утворюєполіном P (x).

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

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

    (4.1 Отримання кодової комбінації додаванням залишку R (x)

    Побудувати циклічний код для передачі 31 розрядної кодовоїкомбінації з виправленням одноразової помилки (n = 31, s = 1)

    Рішення.
    1. Визначимо число контрольних розрядів - m: m = log2 (n +1) = log2 (31 +1) = 5.
    2. Визначимо кількість інформаційних розрядів k: k = nm = 26,тобто отримали (31, 26) - код.
    3. Будуємо інформаційний поліном, сответствующій інформаційномуслову довжиною k-біт:

    G (x) = 00000000000000000000000101 = x2 +1.
    4. Здійснюючи зсув коду вліво на m = nk = 5 розрядів тобто поліном G (x)множиться на xm: xm G (x) = (x2 +1) x5 = x7 + x5 = 0000000000000000000000010100000.
    5. Вибирається створюючий многочлен-P (x) за таблицею непріводімихмногочленів. Для виправлення одиночної помилки (d0 = 3) утворює поліном
    P (x) повинен бути ступеня m = nk = 5 і кількістю ненульових членів не меншемінімального кодового відстані d0 = 3. Виходячи зцього образуюшій полином P (x) дорівнює:
    P (x) = x5 + x4 + x3 + x 2 +1 = 111101.
    6. Визначимо залишок R (x) від ділення G (x) (xm на який утворює по-Ліном P (x) x7 + x5 x5 + x4 + x3 + x 2 1
    10100000 111101 x7 + x6 + x5 + x 4 + x2 x2 + x +1 111101

    111 x6 + x4 + x2
    101010 x6 + x5 + x4 + x 3 + x 111101 x5 + x3 + x2 + x
    101110 x5 + x4 + x3 + x 2 1
    111101 x4 + x +1
    10011

    Залишок R (x) = x4 + x +1 = 10011.
    7. Будуємо передається кодовий проліну F (x):
    F (x) = xm G (x) (R (x) = x7 + x5 + x4 + x +1 = 0000000000000000000000010110011.
    8. Нехай у прийнятому повідомленні сталася помилка в тридцять першомурозряді, при зтом прийняте кодове повідомлення має вигляд:

    F ((x) = F (x) (E (x) = 1000000000000000000000010110011.
    9. Розділемо многочлен F1 (x) соотвествующий отриманої кодової ком-комбінаціїна який утворює поліном, при цьому вага залишку (кількість одиниць в кодізалишку) повинен бути менше або дорівнює кількості помилок W (S

    1000000000000000000000010110011 111101

    111101

    111010

    111101 < p> 111000

    111101

    101000

    111101

    101010

    111101

    101110

    111101

    100110

    111101

    110110

    111101

    101100

    111101

    100010

    111101

    111110

    111101

    110010

    111101

    111111

    111101

    100011

    111101

    11110
    Порівнюємо вага отриманого залишку w з числом виправляємо помилкиw> s.

    10. Виробляємо циклічний зсув прийнятої кодової комбінації на одинрозряд вліво і повторюємо п.9 поки w (s.

    a) 0000000000000000000000101100111 111101

    111101

    100011

    111101

    111101

    111101

    1 (w = s.
    Складаємо по модулю 2 останнє ділене з останнім залишком:

    0000000000000000000000101100111
    (1

    0000000000000000000000101100110

    Здійснюємо зворотний зсув на 1 розряд отриманої комбінації
    0000000000000000000000010110011
    Відкинувши контрольні розряди, отримуємо передане інформаційної слово.

    § 4.2 Побудова кодової комбінації шляхом множення на який утворює поліном

    Побудувати циклічний код для передачі 31 розрядної кодовоїкомбінації з виправленням одноразової помилки (n = 31, s = 1) шляхом множенняутворює многочлена на многочлен повного 31 розрядного коду.

    Рішення.

    1. Будуємо інформаційний поліном, сответствующій інформаційномуслову довжиною k-біт:
    G (x) = 00000000000000000000000101 = x2 2.
    2. Будуємо передається кодовий поліном

    00000000000000000000000101

    111101

    00000000000000000000000101

    00000000000000000000000101

    00000000000000000000000101

    00000000000000000000000101

    00000000000000000000000101

    0000000000000000000000011001001

    3. Процес виправлення одноразової помилки аналогічний описаномув § 4.1.

    (5. Розробка схеми алгоритму

    Ciclic code

    немає

    так

    немає

    так

    Кінець

    (6. Розробка тексту програми

    Для подання інформаційного слова в пам'яті використовується масив. До складу програми входить основна програма і два модулі,що реалізують алгоритм кодування і декодування інформаційних слів ідіалогу з користувачем відповідно.
    Program Cyclic_Code;
    Uses

    Crt, _CC31, _Serv;
    Var m, mm: Move_code; p: Polinom; r: Rest; i, Mainflag, From, Error: integer;

    Switch: byte;

    Key: boolean;begin
    Repeat

    Key: = true;

    TextColor (11);

    TextBackGround (7);

    Clrscr;

    SetWindow (24,10,45,14,2, 'Головне меню');

    Switch: = GetMainMenuChoice; case Switch of

    1: begin

    About;

    Readln;

    Key: = False; end;

    2: begin

    TextColor (0);

    ClrScr;

    SetWindow (25,10,40,13,1, 'Утворити');

    Switch: = GetSubMenuChoice; case Switch of

    1: begin

    TextBackGround (0);

    TextColor (15);

    ClrScr;

    SetWindow ( 1,1,79,24,2, 'Демонстрація');

    TextColor (14);

    GotoXY (2,2);

    Init ( m, p, r, MainFlag);

    Write ( 'Інформаційний поліном');

    TextColor (2); for i: = n downto 0 do begin if (i = 0 ) and (r2 [i1] = 0)) do dec (i1); if (i1 =- 1) then goto RETURN;

    Kol: = n1-i1; while (Kol> 0) do begin for i: = n1 downto 1 do r2 [i]: = r2 [i-1]; dec (Kol); end;

    Kol: = n1-i1; while ((Kol> 0) and (j> = 0)) do begin r2 [Kol-1]: = m2 [j]; dec (Kol); dec (j); end; if ((j =- 1) and (Kol = 0)) then begin for i: = n1 downto 0 do r2 [i]: = r2 [i] xor p2 [i]; end else flag: = Kol; end; end else if (n1 = j) then begin for i: = n1 downto 0 do begin r2 [i]: = m2 [j]; dec (j); end; for i: = n1 downto 0 do r2 [i]: = r2 [i] xor p2 [i] end else if (j0) then begin k: = n1-flag; for i: = n1 downto flag do begin m3 [k]: = r3 [i]; dec (k); end; end

    else begin for i: = n1-1 downto 0 do m3 [i]: = r3 [i]; end;end;
    Procedure MakeError (var m4: Move_code; var err: integer);begin

    Randomize; err: = Random (n); m4 [err]: = m4 [err] xor 1;

    end;
    Procedure Decoder (var m6: Move_Code);var i: integer; k: byte;begin k: = 5; while (k> 0) do begin for i: = 0 to n-1 do m6 [i]: = m6 [i +1]; dec (k); end; for i: = n downto n-n1 +1 do m6 [i]: = 0;end;

    Procedure BildMoveCodeMultiplication (var m7: Move_Code);var m1, m2, m3, m4, mm: Move_Code; i, j: integer;begin mm: = m7; m1: = m7; for j: = 0 to 1 do begin for i: = n downto 1 do m1 [i]: = m1 [i-1]; m1 [j]: = 0; end ; m2: = m7; for j: = 0 to 2 do begin for i: = n downto 1 do m2 [i]: = m2 [i-1]; m2 [j]: = 0; end; m3: = m7 ; for j: = 0 to 3 do begin for i: = n downto 1 do m3 [i]: = m3 [i-1]; m3 [j]: = 0; end; m4: = m7; for j: = 0 to 4 do begin for i: = n downto 1 do m4 [i]: = m4 [i-1]; m4 [j]: = 0; end; for i: = n downto 0 do m7 [i]: = mm [i] xor m1 [i] xor m2 [i] xor m3 [i] xor m4 [i];

    end;
    Procedure Correction (var m5: Move_code; p5: Polinom; var r5: Rest);var i, Correctflag, i1: integer;

    Count, Countcarry, Carryflag: byte;

    begin

    Correctflag: = 0;

    Countcarry: = 0; repeat for i: = n1 downto 0 do r5 [i]: = 0;

    Count: = 0;

    Divizion (m5, r5, p5, Correctflag); i1: = n1; while ((i1> = Correctflag) and (r5 [i1] = 0)) do dec (i1); if (((i1 = Correctflag-1) or

    () (i1 = Correctflag) and (r5 [Correctflag] = 1 )){)} then m5 [0]: = m5 [0] xor r5 [Correctflag] else begin

    Carryflag: = m5 [ n]; for i: = n downto 1 do m5 [i]: = m5 [i-1]; m5 [0]: = Carryflag; inc (Countcarry); end; until (((i1 = Correctflag-1) or

    () (i1 = Correctflag) and (r5 [Correctflag] = 1 ));{);} while (Countcarry> 0) do begin

    Carryflag: = m5 [0 ]; for i: = 0 to n-1 do m5 [i]: = m5 [i +1]; m5 [n]: = Carryflag; dec (Countcarry); end;end;end.

    Додаток № 2

    Процедури і функції модуля _Serv.

    Unit _SERV;
    Interface
    Uses

    Crt, Dos;
    Const

    EmptyBorder = 0;

    SingleBorder = 1;

    DoubleBorder = 2;

    BorderChar: array [0 .. 2, 1 .. 6] of Char =

    ((# 32, # 32, # 32, # 32, # 32, # 32),

    (# 218, # 196, # 191, # 179, # 192, # 217),

    (# 201, # 205, # 187, # 186, # 200, # 188 ));

    MaxChar = 80;

    MaxLine = 25;

    MenuTop = 3;

    SubMenuTop = 2;

    MenuLine: array [1 .. MenuTop ] of string [20] =

    ( 'Про програму ...',' Демонстрація' 'Вихід');

    SubMenuLine: array [1 .. SubMenuTop] of string [ 20] =

    ( 'Додавання', 'Множенням');
    Procedure SetWindow (x1, y1, x2, y2, Bord: byte; Header: string);
    Procedure CursorOff;
    Function GetMainMenuChoice: byte;
    Function GetSubMenuChoice: byte;
    Procedure About;
    Implementation
    Procedure SetWindow (x1, y1, x2, y2, Bord: byte; Header: string);var i: integer;begin if not ((x11) then dec (Count);

    # 80: if (Count1) then dec (Count);

    # 80: if (Count

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status