Мета роботи: отримати навики по розробленню Windows Forms програм CLR за допомогою інструментарію Visual C++ 2005 та реалізувати циклічний кодер/декодер алгоритмічною мовою С++.
Завдання
Написати мовою С++ програму, що реалізує алгоритм роботи циклічного кодера та декодера для коду БЧХ, згідно варіанту завдання. Вигляд програми має відповідати рис. 5.1.
Функція кодування зчитує число у двійковому вигляді з вікна №1 (G_X () та виводить закодоване повідомлення у двійковому вигляді у вікно №2 (F_X). Параметри коду БЧХ задаються у середині програми. Відповідно до цих даних вибрати мінімальний по розміру беззнаковий цілий тип.
Функція декодування зчитує закодоване повідомлення у двійковому вигляді з вікна №2 (F_X), а з вікна №4 зчитує у двійковому виді маску з “1” у спотворюваних розрядах, за допомогою якої здійснює інверсію розрядів закодованого повідомлення F_X. Результат декодування виводить у вікно №3 (( G_X). Механізм виявлення та виправлення помилок реалізувати за допомогою алгоритму з циклічними зсувами. Усю необхідну додаткову інформацію виводити у широке інформаційне вікно.
На основі розробленої програми провести дослідження можливостей по виявленню та виправленню помилок для заданого твірного поліному БЧХ. Зняти 10 результатів виконання циклічного кодування-декодування при внесенні спотворень згідно таблиці 2.
* У вхідних даних коду БХЧ: n – довжина закодованого повідомлення, s – кількість помилок, що виправляються, P(x) – твірний поліном. Кількість контрольних бітів визначається із залежності: n = k + m, а запис твірного полінома, представленого у вигляді вісімкових цифр, перетворюється шляхом переводу кожної вісімкової цифри у двійкове число. Наприклад, P(x) = 2467. Цифрі 2 відповідає двійкове число 010, цифрі 4 – 100, цифрі 6 – 110, а цифрі 7 – 111, і остаточно – 10100110111 ( ).

№ п/п
Параметри циклічного коду БЧХ

2
n = 15; k = 11; s = 1; P(x) = 23


№
п/п
1) без спотворень; 2) спотворився молодший розряд закодованого повідомлення F_X; 3) спотворився старший розряд; 4) спотворилися два молодших розряди; 5) спотворилися два старших розряди; 6-10 набори спотворень вибираються з таблиці згідно № п/п та № групи.



Група 2


2

6) 4, 7, 9; 7) 2, 8, 11;
8) 2, 10; 9) 7; 10) 1;



Короткі теоретичні відомості
Циклічний кодер
Циклічні коди відносяться до числа блокових систематичних кодів, у яких кожна комбінація кодується самостійно (у вигляді блоку) таким чином, що інформаційні k та контрольні m символи (розряди) завжди знаходяться на визначених місцях. Назва кодів походить від їх циклічних властивостей: якщо – кодове слово циклічного коду, тоді , отримане циклічним зсувом елементів C, також є кодовим словом. Усі циклічні зсуви C, утворюють кодові слова. І як результат циклічної властивості, ці коди володіють значною кількістю структурних зручностей, які можна використати при реалізації операцій кодування та декодування.
Можливість виявлення та виправлення практично любих помилок при відносно малій надлишковості та простій реалізації зробило ці коди широко розповсюдженими. Циклічні коди використовуються в безпровідній телефонії та у мобільному зв’язку.
Теорія циклічних кодів базується на теорії груп та алгебрі многочленів над полем Галуа. Поліном (многочлен), який можна представити у вигляді добутку поліномів нижчих степенів, називають звідним, в протилежному випадку незвідним. Поліноми у полі двійкових чисел називають незвідними, якщо вони діляться без остачі тільки на себе чи на одиницю. Незвідні поліноми можна записати у вигляді алгебричного поліному, або у вигляді двійкових чи десяткових чисел, наприклад

В основу циклічного кодування закладено використання незвідних поліномів , які для циклічних кодів називають твірними поліномами.
Найпростіший спосіб утворення циклічного коду полягає у множенні заданої кодової комбінації на твірний поліном . Недоліком такого підходу є те, що контрольні розряди m будуть розміщені у найрізноманітніших місцях кодової комбінації. Такий підхід вважається не раціональним, і тому використовується спосіб, який розміщує контрольні розряди після інформаційних.
Метод побудови циклічного коду
Множимо вхідну кодову комбінацію на одночлен , що має таку ж степінь, що й твірних поліном
. (3.1)
Ділимо добуток на твірний поліном
, (3.2)
де – частка від ділення, що має той самий степінь, що й поліном ; – залишок від ділення, що має степінь, не більший від (менший, ніж степінь дільника ).
Множачи цей вираз на та переносячи у другу частину рівняння, згідно правил алгебри двійкового поля, тобто без зміни знаку на зворотній, отримуємо
, (3.3)
де – закодоване повідомлення. Звідси
, (3.4)
Приклад:
Зауваження: є певна надлишковість коду, пов’язана з необхідністю визначати кількість розрядів на початку та в кінці алгоритму, тобто в середині циклу do ( while обчислення кількості розрядів виконується двічі.
Формуємо повідомлення циклічного коду (3.4).
Циклічний декодер
Ідея виявлення помилок у прийнятому циклічному коді полягає у тому, що при відсутності помилок закодоване повідомлення ділиться на твірний поліном без залишку. При цьому контрольні розряди m відкидаються, а інформаційні розряди k використовуються за призначенням.
Обчислюємо залишок від результату ділення за правилами алгебри двійкового поля (алгоритм знаходження цього залишку аналогічний алгоритму п.2 циклічного кодера).
При робимо висновок, що комбінація прийнята без помилок. Наявність залишку свідчить, що комбінація спотворена.
Якщо , тоді виконуємо процедуру виправлення помилок за такою схемою.
Виконуємо підрахунок ваги залишку , тобто підрахунок кількості «1» у залишку.
Якщо вага залишку рівна чи менша числу помилок, що виправляються , то прийняту комбінацію сумують за модулем 2 із залишком та отримують виправлену комбінацію.
Якщо , то проводять циклічний зсув на один біт вліво та отриману комбінацію знову ділять на твірний поліном . Якщо вага отриманого залишку , то циклічно зсунуту комбінацію сумують із залишком, а потім циклічно зсувають її у зворотну сторону вправо на 1 розряд (повертають на попереднє місце). В результаті отримують виправлену комбінацію.
Якщо після циклічного зсуву на один біт знову , то проводять додаткові зсуви вліво. При цьому після кожного зсуву зсунуту комбінацію ділять на та перевіряють вагу залишку. При виконують дії, вказані в п.b, з тією лиш різницею, що зворотних циклічних зсувів вправо роблять стільки, скільки їх було зроблено вліво.
Вилучаємо контрольні розряди.
Загальний алгоритм побудови циклічного декодера.
Оголошуємо та ініціалізуємо ідентифікатори ( String^ ErrorText; беззнаковий цілий F_X, G_X, P_X, R_X, first_F_X, first_R_X; int всі решта, проміжні змінні чи маски для F_X, R_X мають теж беззнаковий тип).
Встановлюємо початкові значення для таких змінних:
shift = i_cycling = 0; break_R_X =1; (break_R_X ( інформація про наявність помилки, i_cycling ( кількість виконаних циклів )
Зчитуємо закодоване повідомлення у двійковому вигляді.
Далі у циклі виконуємо такий код:
Зауваження: недоліком алгоритму виправлення помилок за допомогою циклічних зсувів є можливість виникнення ситуації зациклення: тобто при циклічному зсуві вліво та діленні на твірний поліном значення ваги W не зменшується, а через певне число циклів повторюється комбінація початкових значень та . Тому для цього ми запам’ятовуємо первинні значення та , та у кожному наступному циклі порівнюємо їх з новими. Якщо зауважуємо співпадіння – формуємо інформацію про помилку та завершуємо процес декодування.
Здійснюємо перевірку на помилку зациклення та виконуємо зворотний циклічний зсув .
Вилучаємо контрольні розряди.
Виводимо декодоване повідомлення у двійковому вигляді.
Виводимо інформацію про наявні помилки у вигляді інформаційного вікна або у компоненті для виводу тексту (наприклад TextBox із заданою опцією Multiline = true).
Список ідентифікаторів методів, використаних у програмі, та їх пояснення.
Fx,f_Fx,Gx,Px=0x13,nPx,Rx,f_Rx,nRx,break_Rx,invert,i_cyc,shift,W,word,mask,count,s_CC=1,n_CC=615,k_CC=11,k_bit;