Міністерство освіти і науки України
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсового проекту
на тему "Кодування інформації. Код Ріда-Малера"
за курсом "Кодування та захист інформації"
2003
Зміст
Введення
1 Надлишкові коди
2 Алгоритм кодування Ріда-Малера
3 Тестовий приклад
Висновок
Бібліографічний список
Додаток: Текст програми
Введення
Метою цієї роботи є закріплення знань, одержуваних у процесі вивчення дисципліни, придбання необхідних практичних навичок застосування методів кодування інформації. У цій роботі розглядається кодування інформації методом Ріда-Малера. Код Ріда-Малера відноситься до надмірних кодами. Завданням на дану роботу було розробити алгоритм і програму кодування і декодування даних кодом Ріда-Малера (16,11).
1. Надлишкові коди
Надлишкові коди - одне з найбільш ефективних засобів забезпечення високої достовірності переданих і прийнятих повідомлень.
Надлишкові коди можуть застосовуватися з метою або тільки виявлення можливих помилок, які виправлення виявлених помилок. У всіх випадках бажано досягти максимальної корегуючої здібності. Але в залежності від конкретного побудови коду його здатність до виправлення тих чи інших помилок може змінюватися в широких межах.
При деяких значеннях n і k може бути знайдене таке вдале побудова коду, при якому ваги всіх дозволених ненульових комбінацій мало відрізняються один від одного і від половини максимально можливого ваги. При інших значеннях n і k може виявитися, що для деякої малої частини кодових комбінацій з їх загального числа відстань виявляється істотно меншим, ніж для більшості інших. Тому при розгляді характеристик кодів можна виявити, що близькі за надмірності і числу розрядів коди різко відрізняються один від одного за своєю корегуючої здібності.
У кодах з однією перевіркою на парність міститься всього один перевірочний символ. Цей символ вибирається таким, щоб його сума за модулем два з усіма інформаційними символами дорівнювала нулю. Завдяки такому способу вибору перевірочного символу кодова комбінація містить парне число одиниць. І отже ознакою спотворення кодової комбінації є непарність одиниць у прийнятій комбінації. Даний код дозволяє тільки виявляти однократні помилки і всі помилки непарної кратності.
У кодах з простим повторенням положення метод повторення вихідної кодової комбінації. На приймальному боці комбінація складається з вихідною і при нульовій сумі комбінація приймається. Цей код дозволяє виявляти помилки, за винятком помилок в парних елементах.
Кореляційні код. Подвоюються символи, при цьому якщо в розряді інформаційної частини стоїть 0, то він замінюється на 01, а 1 - на 10. Сигналом помилки є поява 00 або 11.
У інверсному коді використовується повторення вихідної комбінації наступним чином: якщо комбінація містить непарне число одиниць, то замість 1 ставиться 0, а всесто 0 - 1. Якщо парне число одиниць, то вона подвоюється без інверсії. На приймальному боці підраховується число одиниць і, якщо воно парне, то друга половинка інвертується і складається з першою. Якщо ж число одиниць парне, то друга складається з першої і повинен вийти 0.
2 Алгоритм кодування Ріда-Малера
Коди Ріда-Малера - це блокові коди, які будуються таким чином:
n-довжина блоку
K-число інформаційних символів
d-мінімальне кодова відстань
m-позитивне, умовне число не менше 3
s-порядок коду, який завжди менше, ніж m.
Тобто в залежності від порядку при одному і тому ж m можна отримати різні коди.
m = 4; s = 1,2,3; n = 2 4 = 16.
Побудова кодів Ріда-Маллера зводиться до наступного.
На початку будується виробляє матриця G, перший рядок якої містить n одиниць. Далі слід m рядків, сукупність яких зручно розглядати як (m * n)-матрицю, в якості стовпців якої обрані двійкові числа (починаючи з нуля). Номери розрядів двійкових чисел зручно вважати зверху вниз. Ці m рядків визначають вектори першого порядку d. Далі йдуть рядки векторів другого порядку, які виходять з усіх творів двох рядків першого порядку, потім - рядки третього порядку, що є усіма творами трьох рядків першого порядку і т д.
Приклад: т = 3 s = 2 п = 2 т = 2 3 = 8
Для кодування визначається загальна кількість символів в блоці через інформаційні символи, підсумовуючи ненульові позиції відповідного стовпчика, що утворює матриці. Одиниці в стовпцях матриці G показують, які саме інформаційні символи Uk визначають значення символів Ui кодового слова.
Нехай прийшла послідовність:
Отримуємо: 11101011
Декодування здійснюється за мажоритарним принципом або принципом більшості.
Декодування здійснюється спочатку для всіх інформаційних символів (крім 1-го) на основі так званих парних компонентів. Починати запис таких рівнянь треба з векторів максимального порядку.
У нашому прикладі s = 2 => перший виписується U k 5.
Для векторів 2-го порядку парними вважаються компоненти:
00 ® 0
01 ® 1
На другому рівні поєднань кожен 0 з'єднується з кожної 1 попарно. Тепер у перевіряється рівність виписуються всі об'єднані позиції 1-го і 2-го рівнів.
Обчислюємо символ U k6
Для U k7:
При декодуванні за допомогою векторів 1-го порядку ми також точно користуємося парними компонентами, але оскільки тут 1-ий рівень, то ми об'єднуємо просто 0 і 1, що стоїть на відповідних позиціях, і, по-друге, при декодуванні в отриманих рівняннях використовують не вихідне, а перетворене рівняння, яке виходить шляхом додавання за модулем два вихідного рівняння і векторів 2-го порядку, (тому що матриця має другу порядок),
Після цього ще раз перетворять вихідне вираз: до отриманого перетвореному висловом додаємо вектори 1-го порядку, які містять одиницю у відповідному інформаційному розряді.
Якщо в отриманому виразі отримали всі 1, то значить U k 1 = 1, а якщо все 0, то U k 1 = 0.
Якщо при передачі відбулися спотворення, то обчислюваний символ по кожній системі перевірок вибирається за мажоритарним принципом, в тому числі і для символу U k 1.
3 Тестовий приклад
В якості тестового прикладу використовувалася комбінація 11001010000.
У завданні до курсового проекту зазначено, що n = 16, а k = 11. Таким чином отримали твірну матрицю, яка має наступний вигляд:
Побудова матриці реалізовано програмно для заданих n і k.
Після кодування вихідної комбінації 11001010000 за отриманою твірної матриці отримали комбінацію1010111101010000. При цьому ми підсумовуємо ті розряди вихідної комбінації, на відповідних позиціях яких, в розглянутому стовпці твірної матриці, стоять одиниці. Наприклад, візьмемо четвертий стовпець. Одиниці є в розрядах 1,2,3,6. При підсумовуванні цих розрядів отримаємо 0. Тобто в закодованій комбінації в четвертому розряді отримали 0:
Декодування здійснюється за мажоритарним ознакою, тобто при декодуванні кожен розряд комбінації перевіряється кількома рівняннями. Завдяки цьому можна уникнути помилок при передачі. Навіть якщо в будь-якому розряді помилка, вона поміняє результат тільки одного рівняння. А в решті результат залишиться той самий.
Висновок
В ході курсової роботи було досліджено простий перешкодостійкий код, а саме код Ріда-Малера. Даний код виявляє помилки, але не виправляє їх. Розглядався випадок, коли n = 16, k = 11, тому в матриці присутні тільки вектора першого і другого порядку. Проте якщо з'явиться необхідність використовувати також вектора третього порядку, то утворює матриця стане значно більше, що не вигідно з точки зору економії пам'яті. При цьому також збільшиться довжина закодованої комбінації, що збільшить час передачі повідомлення по каналу зв'язку.
Бібліографічний список
1. Березюк М.Т. «Кодування Інформації» - 1978.
2. Конспект лекцій з дисципліни «Кодування та захист інформації».
Додаток
Текст програми
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсового проекту
на тему "Кодування інформації. Код Ріда-Малера"
за курсом "Кодування та захист інформації"
2003
Зміст
Введення
1 Надлишкові коди
2 Алгоритм кодування Ріда-Малера
3 Тестовий приклад
Висновок
Бібліографічний список
Додаток: Текст програми
Введення
Метою цієї роботи є закріплення знань, одержуваних у процесі вивчення дисципліни, придбання необхідних практичних навичок застосування методів кодування інформації. У цій роботі розглядається кодування інформації методом Ріда-Малера. Код Ріда-Малера відноситься до надмірних кодами. Завданням на дану роботу було розробити алгоритм і програму кодування і декодування даних кодом Ріда-Малера (16,11).
1. Надлишкові коди
Надлишкові коди - одне з найбільш ефективних засобів забезпечення високої достовірності переданих і прийнятих повідомлень.
Надлишкові коди можуть застосовуватися з метою або тільки виявлення можливих помилок, які виправлення виявлених помилок. У всіх випадках бажано досягти максимальної корегуючої здібності. Але в залежності від конкретного побудови коду його здатність до виправлення тих чи інших помилок може змінюватися в широких межах.
При деяких значеннях n і k може бути знайдене таке вдале побудова коду, при якому ваги всіх дозволених ненульових комбінацій мало відрізняються один від одного і від половини максимально можливого ваги. При інших значеннях n і k може виявитися, що для деякої малої частини кодових комбінацій з їх загального числа відстань виявляється істотно меншим, ніж для більшості інших. Тому при розгляді характеристик кодів можна виявити, що близькі за надмірності і числу розрядів коди різко відрізняються один від одного за своєю корегуючої здібності.
У кодах з однією перевіркою на парність міститься всього один перевірочний символ. Цей символ вибирається таким, щоб його сума за модулем два з усіма інформаційними символами дорівнювала нулю. Завдяки такому способу вибору перевірочного символу кодова комбінація містить парне число одиниць. І отже ознакою спотворення кодової комбінації є непарність одиниць у прийнятій комбінації. Даний код дозволяє тільки виявляти однократні помилки і всі помилки непарної кратності.
У кодах з простим повторенням положення метод повторення вихідної кодової комбінації. На приймальному боці комбінація складається з вихідною і при нульовій сумі комбінація приймається. Цей код дозволяє виявляти помилки, за винятком помилок в парних елементах.
Кореляційні код. Подвоюються символи, при цьому якщо в розряді інформаційної частини стоїть 0, то він замінюється на 01, а 1 - на 10. Сигналом помилки є поява 00 або 11.
У інверсному коді використовується повторення вихідної комбінації наступним чином: якщо комбінація містить непарне число одиниць, то замість 1 ставиться 0, а всесто 0 - 1. Якщо парне число одиниць, то вона подвоюється без інверсії. На приймальному боці підраховується число одиниць і, якщо воно парне, то друга половинка інвертується і складається з першою. Якщо ж число одиниць парне, то друга складається з першої і повинен вийти 0.
2 Алгоритм кодування Ріда-Малера
Коди Ріда-Малера - це блокові коди, які будуються таким чином:
n-довжина блоку
K-число інформаційних символів
d-мінімальне кодова відстань
m-позитивне, умовне число не менше 3
s-порядок коду, який завжди менше, ніж m.
Тобто в залежності від порядку при одному і тому ж m можна отримати різні коди.
m = 4; s = 1,2,3; n = 2 4 = 16.
Побудова кодів Ріда-Маллера зводиться до наступного.
На початку будується виробляє матриця G, перший рядок якої містить n одиниць. Далі слід m рядків, сукупність яких зручно розглядати як (m * n)-матрицю, в якості стовпців якої обрані двійкові числа (починаючи з нуля). Номери розрядів двійкових чисел зручно вважати зверху вниз. Ці m рядків визначають вектори першого порядку d. Далі йдуть рядки векторів другого порядку, які виходять з усіх творів двох рядків першого порядку, потім - рядки третього порядку, що є усіма творами трьох рядків першого порядку і т д.
Приклад: т = 3 s = 2 п = 2 т = 2 3 = 8
Для кодування визначається загальна кількість символів в блоці через інформаційні символи, підсумовуючи ненульові позиції відповідного стовпчика, що утворює матриці. Одиниці в стовпцях матриці G показують, які саме інформаційні символи Uk визначають значення символів Ui кодового слова.
Нехай прийшла послідовність:
Отримуємо: 11101011
Декодування здійснюється за мажоритарним принципом або принципом більшості.
Декодування здійснюється спочатку для всіх інформаційних символів (крім 1-го) на основі так званих парних компонентів. Починати запис таких рівнянь треба з векторів максимального порядку.
У нашому прикладі s = 2 => перший виписується U k 5.
0 0 0 1 0 0 0 1 |
Для векторів 2-го порядку парними вважаються компоненти:
00 ® 0
01 ® 1
На другому рівні поєднань кожен 0 з'єднується з кожної 1 попарно. Тепер у перевіряється рівність виписуються всі об'єднані позиції 1-го і 2-го рівнів.
Обчислюємо символ U k6
0 0 0 0 0 1 0 1 |
Для U k7:
При декодуванні за допомогою векторів 1-го порядку ми також точно користуємося парними компонентами, але оскільки тут 1-ий рівень, то ми об'єднуємо просто 0 і 1, що стоїть на відповідних позиціях, і, по-друге, при декодуванні в отриманих рівняннях використовують не вихідне, а перетворене рівняння, яке виходить шляхом додавання за модулем два вихідного рівняння і векторів 2-го порядку, (тому що матриця має другу порядок),
0 1 0 1 0 1 0 1 |
0 0 1 1 0 0 1 1 |
0 0 0 0 1 1 1 1 |
Після цього ще раз перетворять вихідне вираз: до отриманого перетвореному висловом додаємо вектори 1-го порядку, які містять одиницю у відповідному інформаційному розряді.
Якщо в отриманому виразі отримали всі 1, то значить U k 1 = 1, а якщо все 0, то U k 1 = 0.
Якщо при передачі відбулися спотворення, то обчислюваний символ по кожній системі перевірок вибирається за мажоритарним принципом, в тому числі і для символу U k 1.
3 Тестовий приклад
В якості тестового прикладу використовувалася комбінація 11001010000.
У завданні до курсового проекту зазначено, що n = 16, а k = 11. Таким чином отримали твірну матрицю, яка має наступний вигляд:
Побудова матриці реалізовано програмно для заданих n і k.
Після кодування вихідної комбінації 11001010000 за отриманою твірної матриці отримали комбінацію1010111101010000. При цьому ми підсумовуємо ті розряди вихідної комбінації, на відповідних позиціях яких, в розглянутому стовпці твірної матриці, стоять одиниці. Наприклад, візьмемо четвертий стовпець. Одиниці є в розрядах 1,2,3,6. При підсумовуванні цих розрядів отримаємо 0. Тобто в закодованій комбінації в четвертому розряді отримали 0:
Декодування здійснюється за мажоритарним ознакою, тобто при декодуванні кожен розряд комбінації перевіряється кількома рівняннями. Завдяки цьому можна уникнути помилок при передачі. Навіть якщо в будь-якому розряді помилка, вона поміняє результат тільки одного рівняння. А в решті результат залишиться той самий.
Висновок
В ході курсової роботи було досліджено простий перешкодостійкий код, а саме код Ріда-Малера. Даний код виявляє помилки, але не виправляє їх. Розглядався випадок, коли n = 16, k = 11, тому в матриці присутні тільки вектора першого і другого порядку. Проте якщо з'явиться необхідність використовувати також вектора третього порядку, то утворює матриця стане значно більше, що не вигідно з точки зору економії пам'яті. При цьому також збільшиться довжина закодованої комбінації, що збільшить час передачі повідомлення по каналу зв'язку.
Бібліографічний список
1. Березюк М.Т. «Кодування Інформації» - 1978.
2. Конспект лекцій з дисципліни «Кодування та захист інформації».
Додаток
Текст програми
//------------------------------------------------ ---------------------------
# Include <vcl.h>
# Pragma hdrstop
# Include "Unit1.h"
//------------------------------------------------ ---------------------------
# Pragma package (smart_init)
# Pragma resource "*. dfm"
TForm1 * Form1;
const N = 16;
const K = 11;
char * s;
int f, l [11], l1 [16];
//------------------------------------------------ ---------------------------
__fastcall TForm1:: TForm1 (TComponent * Owner)
: TForm (Owner)
{Int i, j;
for (i = 0; i <N; i + +)
{StringGrid1-> Cells [i] [0] = 1;}
for (i = 0; i <N; i + +)
{StringGrid1-> Cells [i] [1] = 0;
i + +; StringGrid1-> Cells [i] [1] = 1;}
for (i = 0; i <N; i + +)
{StringGrid1-> Cells [i] [2] = 0;
i + +; StringGrid1-> Cells [i] [2] = 0;
i + +; StringGrid1-> Cells [i] [2] = 1;
i + +; StringGrid1-> Cells [i] [2] = 1;}
for (i = 0; i <N; i + +)
{If (i <N / 2)
{StringGrid1-> Cells [i] [4] = 0;}
else
{StringGrid1-> Cells [i] [4] = 1;}
}
for (i = 0; i <N; i + +)
{If (7 <i & & i <12 | | 4> i & & i <8)
{StringGrid1-> Cells [i] [3] = 0;}
else {StringGrid1-> Cells [i] [3] = 1;}
}
int b;
int k1, k2, a = 5;
j = 1; b = 1;
for (j; j <4; j + +)
{For (i = 0; i <N; i + +)
{K1 = StringGrid1-> Cells [i] [b]. ToInt ();
j + +; k2 = StringGrid1-> Cells [i] [j]. ToInt (); j -;
if (k1 == 1 & & k2 == 1)
{StringGrid1-> Cells [i] [a] = 1;}
else
{StringGrid1-> Cells [i] [a] = 0;}
}
a + +;}
b = 2; j = 2;
for (j; j <4; j + +)
{For (i = 0; i <N; i + +)
{K1 = StringGrid1-> Cells [i] [b]. ToInt (); j + +;
k2 = StringGrid1-> Cells [i] [j]. ToInt (); j -;
if (k1 == 1 & & k2 == 1)
{StringGrid1-> Cells [i] [a] = 1;}
else
{StringGrid1-> Cells [i] [a] = 0;}
}
a + +;
}
b = 3; j = 3;
for (j; j <4; j + +)
{For (i = 0; i <N; i + +)
{K1 = StringGrid1-> Cells [i] [b]. ToInt (); j + +;
k2 = StringGrid1-> Cells [i] [j]. ToInt (); j -;
if (k1 == 1 & & k2 == 1)
{StringGrid1-> Cells [i] [a] = 1;}
else
{StringGrid1-> Cells [i] [a] = 0;}
}
}
s = ""; Edit1-> Text = s;
Edit1-> MaxLength = 12;
Memo1-> Text = s;
Memo1-> Lines-> Add ("U1 = Uk1");
Memo1-> Lines-> Add ("U2 = Uk1 + Uk2");
Memo1-> Lines-> Add ("U3 = Uk1 + Uk3");
Memo1-> Lines-> Add ("U4 = Uk1 + Uk2 + Uk3 + Uk6");
Memo1-> Lines-> Add ("U5 = Uk1 + Uk4");
Memo1-> Lines-> Add ("U6 = Uk1 + Uk2 + Uk4 + Uk7");
Memo1-> Lines-> Add ("U7 = Uk1 + Uk3 + Uk4 + Uk9");
Memo1-> Lines-> Add ("U8 = Uk1 + Uk2 + Uk3 + Uk4 + Uk6 + Uk7 + Uk9");
Memo1-> Lines-> Add ("U9 = Uk1 + Uk5");
Memo1-> Lines-> Add ("U10 = Uk1 + Uk2 + Uk5 + Uk8");
Memo1-> Lines-> Add ("U11 = Uk1 + Uk3 + Uk5 + Uk10");
Memo1-> Lines-> Add ("U12 = Uk1 + Uk2 + Uk3 + Uk5 + Uk6 + Uk8 + Uk10");
Memo1-> Lines-> Add ("U13 = Uk1 + Uk4 + Uk5 + Uk11");
Memo1-> Lines-> Add ("U14 = Uk1 + Uk2 + Uk4 + Uk5 + Uk7 + Uk8 + Uk11");
Memo1-> Lines-> Add ("U15 = Uk1 + Uk3 + Uk4 + Uk5 + Uk9 + Uk10 + Uk11");
Memo1-> Lines-> Add ("U16 = Uk1 + Uk2 + Uk3 + Uk4 + Uk5 + Uk6 + Uk7 + Uk8 + Uk9 + Uk10 + Uk11");}
//------------------------------------------------ ---------------------------
void __fastcall TForm1:: BitBtn1Click (TObject * Sender)
{S = Edit1-> Text.c_str ();
for (int i = 1; i <K +1; i + +)
{L [i-1] = StrToInt (s [i]);}
for (int i = 0; i <N; i + +)
{F = 0;
for (int j = 0; j <K; j + +)
{If (StringGrid1-> Cells [i] [j] == 1)
{F = l [j] + f; if (f == 2) f = 0;
}
l1 [i] = f;
}
}
for (int i = 0; i <N; i + +)
{StringGrid2-> Cells [i] [0] = l1 [i];
}
}
//------------------------------------------------ ---------------------------
void __fastcall TForm1:: Button2Click (TObject * Sender)
{Int ed, nul, i, j, perem [4];
int l2 [16]; int edin1 = 0, edin2 = 0, edin3 = 0, edin4 = 0, edin5 = 0, edin6 = 0;
ed = 0; nul = 0;
for (int i = 0; i <N; i + +)
{L1 [i] = StringGrid2-> Cells [i] [0]. ToInt ();}
for (i = 0; i <N; i + +)
{L2 [i] = l1 [i];}
perem [0] = l1 [0] + l1 [4] + l1 [8] + l1 [12]; perem [1] = l1 [1] + l1 [5] + l1 [9] + l1 [13];
perem [2] = l1 [2] + l1 [6] + l1 [10] + l1 [14]; perem [3] = l1 [3] + l1 [7] + l1 [11] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [10] [0] = 1; edin1 = 10;}
else
{StringGrid3-> Cells [10] [0] = 0;}
//------------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [2] + l1 [8] + l1 [10]; perem [1] = l1 [1] + l1 [3] + l1 [9] + l1 [11];
perem [2] = l1 [4] + l1 [6] + l1 [12] + l1 [14]; perem [3] = l1 [5] + l1 [7] + l1 [13] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [9] [0] = 1; edin2 = 9;}
else
{StringGrid3-> Cells [9] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [2] + l1 [4] + l1 [6]; perem [1] = l1 [1] + l1 [3] + l1 [5] + l1 [7];
perem [2] = l1 [8] + l1 [10] + l1 [12] + l1 [14]; perem [3] = l1 [9] + l1 [11] + l1 [13] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [8] [0] = 1; edin3 = 8;}
else
{StringGrid3-> Cells [8] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [1] + l1 [8] + l1 [9]; perem [1] = l1 [2] + l1 [3] + l1 [10] + l1 [11];
perem [2] = l1 [4] + l1 [5] + l1 [12] + l1 [13]; perem [3] = l1 [6] + l1 [7] + l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [7] [0] = 1; edin4 = 7;}
else
{StringGrid3-> Cells [7] [0] = 0;}
//---------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [1] + l1 [4] + l1 [5]; perem [1] = l1 [2] + l1 [3] + l1 [6] + l1 [7];
perem [2] = l1 [8] + l1 [9] + l1 [12] + l1 [13]; perem [3] = l1 [10] + l1 [11] + l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [6] [0] = 1; edin5 = 6;}
else
{StringGrid3-> Cells [6] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [1] + l1 [2] + l1 [3]; perem [1] = l1 [4] + l1 [5] + l1 [6] + l1 [7];
perem [2] = l1 [8] + l1 [9] + l1 [10] + l1 [11]; perem [3] = l1 [12] + l1 [13] + l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [5] [0] = 1; edin6 = 5;}
else
{StringGrid3-> Cells [5] [0] = 0;}
/ / ПРЕОБРАЗОВАНHOЕ ПОВІДОМЛЕННЯ
if (edin1! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [10]. ToInt ();}
if (edin2! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [9]. ToInt ();}
if (edin3! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [8]. ToInt ();}
if (edin4! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [7]. ToInt ();}
if (edin5! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [6]. ToInt ();}
if (edin6! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [5]. ToInt ();}
for (i = 0; i <N; i + +)
{If (l1 [i] == 1 | | l1 [i] == 3 | | l1 [i] == 5 | | l1 [i] == 7)
{L1 [i] = 1;}
else
{L1 [i] = 0;}
}
//-----------------------------------
int edin7 = 0, edin8 = 0, edin9 = 0, edin10 = 0;
ed = 0; nul = 0;
int perem1 [8];
perem1 [0] = l1 [0] + l1 [8]; perem1 [1] = l1 [1] + l1 [9];
perem1 [2] = l1 [2] + l1 [10]; perem1 [3] = l1 [3] + l1 [11];
perem1 [4] = l1 [4] + l1 [12]; perem1 [5] = l1 [5] + l1 [13];
perem1 [6] = l1 [6] + l1 [14]; perem1 [7] = l1 [7] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [4] [0] = 1; edin7 = 6;}
else
{StringGrid3-> Cells [4] [0] = 0;}
//------------------------------
ed = 0; nul = 0;
perem1 [0] = l1 [0] + l1 [4]; perem1 [1] = l1 [1] + l1 [5];
perem1 [2] = l1 [2] + l1 [6]; perem1 [3] = l1 [3] + l1 [7];
perem1 [4] = l1 [8] + l1 [12]; perem1 [5] = l1 [9] + l1 [13];
perem1 [6] = l1 [10] + l1 [14]; perem1 [7] = l1 [11] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [3] [0] = 1; edin8 = 7;}
else
{StringGrid3-> Cells [3] [0] = 0;}
//----------------------------------
ed = 0; nul = 0;
perem1 [0] = l1 [0] + l1 [2]; perem1 [1] = l1 [1] + l1 [3];
perem1 [2] = l1 [4] + l1 [6]; perem1 [3] = l1 [5] + l1 [7];
perem1 [4] = l1 [8] + l1 [10]; perem1 [5] = l1 [9] + l1 [11];
perem1 [6] = l1 [12] + l1 [14]; perem1 [7] = l1 [13] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [2] [0] = 1; edin9 = 8;}
else
{StringGrid3-> Cells [2] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem1 [0] = l1 [0] + l1 [1]; perem1 [1] = l1 [2] + l1 [3];
perem1 [2] = l1 [4] + l1 [5]; perem1 [3] = l1 [6] + l1 [7];
perem1 [4] = l1 [8] + l1 [9]; perem1 [5] = l1 [10] + l1 [11];
perem1 [6] = l1 [12] + l1 [13]; perem1 [7] = l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [1] [0] = 1; edin10 = 9;}
else
{StringGrid3-> Cells [1] [0] = 0;}
/ / 2-e перетворення
int l3 [11];
if (edin7! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [4]. ToInt ();}
if (edin8! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [3]. ToInt ();}
if (edin9! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [2]. ToInt ();}
if (edin10! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [1]. ToInt ();}
for (i = 0; i <N; i + +)
{If (l1 [i] == 1 | | l1 [i] == 3 | | l1 [i] == 5)
{L1 [i] = 1;}
else
{L1 [i] = 0;}
}
//-------------------------------
int perem2 = 0;
for (i = 0; i <N; i + +)
{If (l1 [i] == 1)
{+ + Ed;}
else
{+ + Nul;}
}
if (nul <ed)
{StringGrid3-> Cells [0] [0] = 1;}
else
{StringGrid3-> Cells [0] [0] = 0;}
}
//------------------------------------------------ ---------------------------
# Include <vcl.h>
# Pragma hdrstop
# Include "Unit1.h"
//------------------------------------------------ ---------------------------
# Pragma package (smart_init)
# Pragma resource "*. dfm"
TForm1 * Form1;
const N = 16;
const K = 11;
char * s;
int f, l [11], l1 [16];
//------------------------------------------------ ---------------------------
__fastcall TForm1:: TForm1 (TComponent * Owner)
: TForm (Owner)
{Int i, j;
for (i = 0; i <N; i + +)
{StringGrid1-> Cells [i] [0] = 1;}
for (i = 0; i <N; i + +)
{StringGrid1-> Cells [i] [1] = 0;
i + +; StringGrid1-> Cells [i] [1] = 1;}
for (i = 0; i <N; i + +)
{StringGrid1-> Cells [i] [2] = 0;
i + +; StringGrid1-> Cells [i] [2] = 0;
i + +; StringGrid1-> Cells [i] [2] = 1;
i + +; StringGrid1-> Cells [i] [2] = 1;}
for (i = 0; i <N; i + +)
{If (i <N / 2)
{StringGrid1-> Cells [i] [4] = 0;}
else
{StringGrid1-> Cells [i] [4] = 1;}
}
for (i = 0; i <N; i + +)
{If (7 <i & & i <12 | | 4> i & & i <8)
{StringGrid1-> Cells [i] [3] = 0;}
else {StringGrid1-> Cells [i] [3] = 1;}
}
int b;
int k1, k2, a = 5;
j = 1; b = 1;
for (j; j <4; j + +)
{For (i = 0; i <N; i + +)
{K1 = StringGrid1-> Cells [i] [b]. ToInt ();
j + +; k2 = StringGrid1-> Cells [i] [j]. ToInt (); j -;
if (k1 == 1 & & k2 == 1)
{StringGrid1-> Cells [i] [a] = 1;}
else
{StringGrid1-> Cells [i] [a] = 0;}
}
a + +;}
b = 2; j = 2;
for (j; j <4; j + +)
{For (i = 0; i <N; i + +)
{K1 = StringGrid1-> Cells [i] [b]. ToInt (); j + +;
k2 = StringGrid1-> Cells [i] [j]. ToInt (); j -;
if (k1 == 1 & & k2 == 1)
{StringGrid1-> Cells [i] [a] = 1;}
else
{StringGrid1-> Cells [i] [a] = 0;}
}
a + +;
}
b = 3; j = 3;
for (j; j <4; j + +)
{For (i = 0; i <N; i + +)
{K1 = StringGrid1-> Cells [i] [b]. ToInt (); j + +;
k2 = StringGrid1-> Cells [i] [j]. ToInt (); j -;
if (k1 == 1 & & k2 == 1)
{StringGrid1-> Cells [i] [a] = 1;}
else
{StringGrid1-> Cells [i] [a] = 0;}
}
}
s = ""; Edit1-> Text = s;
Edit1-> MaxLength = 12;
Memo1-> Text = s;
Memo1-> Lines-> Add ("U1 = Uk1");
Memo1-> Lines-> Add ("U2 = Uk1 + Uk2");
Memo1-> Lines-> Add ("U3 = Uk1 + Uk3");
Memo1-> Lines-> Add ("U4 = Uk1 + Uk2 + Uk3 + Uk6");
Memo1-> Lines-> Add ("U5 = Uk1 + Uk4");
Memo1-> Lines-> Add ("U6 = Uk1 + Uk2 + Uk4 + Uk7");
Memo1-> Lines-> Add ("U7 = Uk1 + Uk3 + Uk4 + Uk9");
Memo1-> Lines-> Add ("U8 = Uk1 + Uk2 + Uk3 + Uk4 + Uk6 + Uk7 + Uk9");
Memo1-> Lines-> Add ("U9 = Uk1 + Uk5");
Memo1-> Lines-> Add ("U10 = Uk1 + Uk2 + Uk5 + Uk8");
Memo1-> Lines-> Add ("U11 = Uk1 + Uk3 + Uk5 + Uk10");
Memo1-> Lines-> Add ("U12 = Uk1 + Uk2 + Uk3 + Uk5 + Uk6 + Uk8 + Uk10");
Memo1-> Lines-> Add ("U13 = Uk1 + Uk4 + Uk5 + Uk11");
Memo1-> Lines-> Add ("U14 = Uk1 + Uk2 + Uk4 + Uk5 + Uk7 + Uk8 + Uk11");
Memo1-> Lines-> Add ("U15 = Uk1 + Uk3 + Uk4 + Uk5 + Uk9 + Uk10 + Uk11");
Memo1-> Lines-> Add ("U16 = Uk1 + Uk2 + Uk3 + Uk4 + Uk5 + Uk6 + Uk7 + Uk8 + Uk9 + Uk10 + Uk11");}
//------------------------------------------------ ---------------------------
void __fastcall TForm1:: BitBtn1Click (TObject * Sender)
{S = Edit1-> Text.c_str ();
for (int i = 1; i <K +1; i + +)
{L [i-1] = StrToInt (s [i]);}
for (int i = 0; i <N; i + +)
{F = 0;
for (int j = 0; j <K; j + +)
{If (StringGrid1-> Cells [i] [j] == 1)
{F = l [j] + f; if (f == 2) f = 0;
}
l1 [i] = f;
}
}
for (int i = 0; i <N; i + +)
{StringGrid2-> Cells [i] [0] = l1 [i];
}
}
//------------------------------------------------ ---------------------------
void __fastcall TForm1:: Button2Click (TObject * Sender)
{Int ed, nul, i, j, perem [4];
int l2 [16]; int edin1 = 0, edin2 = 0, edin3 = 0, edin4 = 0, edin5 = 0, edin6 = 0;
ed = 0; nul = 0;
for (int i = 0; i <N; i + +)
{L1 [i] = StringGrid2-> Cells [i] [0]. ToInt ();}
for (i = 0; i <N; i + +)
{L2 [i] = l1 [i];}
perem [0] = l1 [0] + l1 [4] + l1 [8] + l1 [12]; perem [1] = l1 [1] + l1 [5] + l1 [9] + l1 [13];
perem [2] = l1 [2] + l1 [6] + l1 [10] + l1 [14]; perem [3] = l1 [3] + l1 [7] + l1 [11] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [10] [0] = 1; edin1 = 10;}
else
{StringGrid3-> Cells [10] [0] = 0;}
//------------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [2] + l1 [8] + l1 [10]; perem [1] = l1 [1] + l1 [3] + l1 [9] + l1 [11];
perem [2] = l1 [4] + l1 [6] + l1 [12] + l1 [14]; perem [3] = l1 [5] + l1 [7] + l1 [13] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [9] [0] = 1; edin2 = 9;}
else
{StringGrid3-> Cells [9] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [2] + l1 [4] + l1 [6]; perem [1] = l1 [1] + l1 [3] + l1 [5] + l1 [7];
perem [2] = l1 [8] + l1 [10] + l1 [12] + l1 [14]; perem [3] = l1 [9] + l1 [11] + l1 [13] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [8] [0] = 1; edin3 = 8;}
else
{StringGrid3-> Cells [8] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [1] + l1 [8] + l1 [9]; perem [1] = l1 [2] + l1 [3] + l1 [10] + l1 [11];
perem [2] = l1 [4] + l1 [5] + l1 [12] + l1 [13]; perem [3] = l1 [6] + l1 [7] + l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [7] [0] = 1; edin4 = 7;}
else
{StringGrid3-> Cells [7] [0] = 0;}
//---------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [1] + l1 [4] + l1 [5]; perem [1] = l1 [2] + l1 [3] + l1 [6] + l1 [7];
perem [2] = l1 [8] + l1 [9] + l1 [12] + l1 [13]; perem [3] = l1 [10] + l1 [11] + l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [6] [0] = 1; edin5 = 6;}
else
{StringGrid3-> Cells [6] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem [0] = l1 [0] + l1 [1] + l1 [2] + l1 [3]; perem [1] = l1 [4] + l1 [5] + l1 [6] + l1 [7];
perem [2] = l1 [8] + l1 [9] + l1 [10] + l1 [11]; perem [3] = l1 [12] + l1 [13] + l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem [i] == 1 | | perem [i] == 3)
{Perem [i] = 1; + + ed;}
else
{Perem [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [5] [0] = 1; edin6 = 5;}
else
{StringGrid3-> Cells [5] [0] = 0;}
/ / ПРЕОБРАЗОВАНHOЕ ПОВІДОМЛЕННЯ
if (edin1! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [10]. ToInt ();}
if (edin2! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [9]. ToInt ();}
if (edin3! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [8]. ToInt ();}
if (edin4! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [7]. ToInt ();}
if (edin5! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [6]. ToInt ();}
if (edin6! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [5]. ToInt ();}
for (i = 0; i <N; i + +)
{If (l1 [i] == 1 | | l1 [i] == 3 | | l1 [i] == 5 | | l1 [i] == 7)
{L1 [i] = 1;}
else
{L1 [i] = 0;}
}
//-----------------------------------
int edin7 = 0, edin8 = 0, edin9 = 0, edin10 = 0;
ed = 0; nul = 0;
int perem1 [8];
perem1 [0] = l1 [0] + l1 [8]; perem1 [1] = l1 [1] + l1 [9];
perem1 [2] = l1 [2] + l1 [10]; perem1 [3] = l1 [3] + l1 [11];
perem1 [4] = l1 [4] + l1 [12]; perem1 [5] = l1 [5] + l1 [13];
perem1 [6] = l1 [6] + l1 [14]; perem1 [7] = l1 [7] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [4] [0] = 1; edin7 = 6;}
else
{StringGrid3-> Cells [4] [0] = 0;}
//------------------------------
ed = 0; nul = 0;
perem1 [0] = l1 [0] + l1 [4]; perem1 [1] = l1 [1] + l1 [5];
perem1 [2] = l1 [2] + l1 [6]; perem1 [3] = l1 [3] + l1 [7];
perem1 [4] = l1 [8] + l1 [12]; perem1 [5] = l1 [9] + l1 [13];
perem1 [6] = l1 [10] + l1 [14]; perem1 [7] = l1 [11] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [3] [0] = 1; edin8 = 7;}
else
{StringGrid3-> Cells [3] [0] = 0;}
//----------------------------------
ed = 0; nul = 0;
perem1 [0] = l1 [0] + l1 [2]; perem1 [1] = l1 [1] + l1 [3];
perem1 [2] = l1 [4] + l1 [6]; perem1 [3] = l1 [5] + l1 [7];
perem1 [4] = l1 [8] + l1 [10]; perem1 [5] = l1 [9] + l1 [11];
perem1 [6] = l1 [12] + l1 [14]; perem1 [7] = l1 [13] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [2] [0] = 1; edin9 = 8;}
else
{StringGrid3-> Cells [2] [0] = 0;}
//----------------------------
ed = 0; nul = 0;
perem1 [0] = l1 [0] + l1 [1]; perem1 [1] = l1 [2] + l1 [3];
perem1 [2] = l1 [4] + l1 [5]; perem1 [3] = l1 [6] + l1 [7];
perem1 [4] = l1 [8] + l1 [9]; perem1 [5] = l1 [10] + l1 [11];
perem1 [6] = l1 [12] + l1 [13]; perem1 [7] = l1 [14] + l1 [15];
for (i = 0; i <4; i + +)
{If (perem1 [i] == 1 | | perem1 [i] == 3 | | perem1 [i] == 5 | | perem1 [i] == 7)
{Perem1 [i] = 1; + + ed;}
else
{Perem1 [i] = 0; + + nul;}
}
if (nul <ed)
{StringGrid3-> Cells [1] [0] = 1; edin10 = 9;}
else
{StringGrid3-> Cells [1] [0] = 0;}
/ / 2-e перетворення
int l3 [11];
if (edin7! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [4]. ToInt ();}
if (edin8! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [3]. ToInt ();}
if (edin9! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [2]. ToInt ();}
if (edin10! = 0)
for (i = 0; i <N; i + +)
{L1 [i] = l1 [i] + StringGrid1-> Cells [i] [1]. ToInt ();}
for (i = 0; i <N; i + +)
{If (l1 [i] == 1 | | l1 [i] == 3 | | l1 [i] == 5)
{L1 [i] = 1;}
else
{L1 [i] = 0;}
}
//-------------------------------
int perem2 = 0;
for (i = 0; i <N; i + +)
{If (l1 [i] == 1)
{+ + Ed;}
else
{+ + Nul;}
}
if (nul <ed)
{StringGrid3-> Cells [0] [0] = 1;}
else
{StringGrid3-> Cells [0] [0] = 0;}
}
//------------------------------------------------ ---------------------------