Відповіді до задач

 

Частина I  Розділ 1

(біт/сим), (біт/сим);

HX=1,75 (біт/cим),(біт/сим),

(біт/сим),

(біт/сим),

(біт/сим);

(біт/сим), HX1=HX2=2 (біт/сим),

(біт/сим);

I(X, Y)= I(Y, Y)=1 (біт/сим);

I(Z, X1)= I(X1, X1)=HX1=1 (біт/сим); HZ=2 (біт/сим); I(Z, X1)= I(X1, X1)  X1 =f(Z);

HX1=1 (біт/сим), HY=1,5 (біт/сим), I(Y, X1)=0,5 (біт/сим);

(біт/сим);

HX=1,75 (біт/сим),(біт/сим), (біт/сим), I(Z, X)=1,75 (біт/сим), (біт/сим);

HX=1 (біт/сим),(біт/сим), (біт/сим);

(біт/сим),HX2=1(біт/сим),(біт/сим),(біт/сим),(біт/сим);

HX=1,5 (біт/сим), (біт/сим),

(біт/сим),1(біт/сим), (біт/сим);

HX=2 (біт/cим), HZ=3,25 (біт/cим), I(Z, X1)=I(Z, X2)=1,25 (біт/cим);

HX=HY=2 (біт/cим), HZ=3,875 (біт/cим), I(Z, X)=1,875 (біт/cим);

(біт/cим),(біт/cим);

HX=HY=1,75 (біт/cим),

 (біт/cим),

(біт/cим),(біт/cим);

I(Z, X1)=0 (біт/cим), I(Z, X2)=1 (біт/cим), HX1=HZ=1 (біт/cим);

HX1=HX2=1,585 (біт/сим); (біт/сим); (біт/сим);(біт/сим).

 Частина I  Розділ 2

H(Y/x1)0,222 (біт/сим), H(Y/x2)0,705 (біт/сим), H(Y/x3)0,593 (біт/сим), H(Y/X)0,504 (біт/сим), H(X/y1)0,598 (біт/сим), H(X/y2) 0,861 (біт/сим), H(X/y3) 0,184 (біт/сим),  H(X/Y)0,467 (біт/сим);

H(X/y1)= 0,954  (біт/сим), H(X/ y2)=0,592  (біт/сим), H(X/y3)=1,522 (біт/сим), H(X/Y)=0,969 (біт/сим), I(X,Y)=0,367 (біт/сим);

H(X/y1)1,116 (біт/сим), H(X/y2)1,485(біт/сим), H(X/y3)1,579 (біт/сим), H(X/y4)1,502 (біт/сим), H(X/Y)1,422 (біт/сим), I(X,Y)0,572 (біт/сим);

H(X/y1)0,244 (біт/сим), H(X/y2)0,336(біт/сим), H(X/y3) 0,161(біт/сим), H(X/Y)0,221 (біт/сим), I(X,Y) 1,264 (біт/сим);

H(X/y1)=0,364 (біт/сим), H(X/y2)=0,974 (біт/сим), H(X/y3)=1,406 (біт/сим), H(X/Y)= 0,621 (біт/сим);

I(X,Y) 0,683 (біт/сим), I(100) 68 (біт), 100H(X/Y)1000,55355 (біт);

H(X/Y)0,216  (біт/сим), C1,37103 (бод), Vи855 (сим/с);

H(X/Y)0,221 (біт/сим), Vк1,26103 (бод);

I(X,Y)0,42  (біт/сим), C434 (бод);

C0,0864 (кбод); безпомилкова передача по каналу неможлива;

H(X/ Y) 0,621 (біт/сим); C964 (бод); безпомилкова передача неможлива.

 

Частина II  Розділ 3

 (біт/сим), =1;

(біт/сим), к0,02;

Для коду Шеннона-Фано і коду Хаффмена  (біт/сим), надлишковість коду к0,01;

HX 2,175 (біт/сим), для коду Шеннона-Фано  (біт/сим), для коду Хаффмена (біт/сим);

1) (біт/сим), 2)  (біт/сим), 3)  (біт/сим); 4) (біт/сим);

1) (біт/сим), 2)  (біт/сим), 3) (біт/сим);

 

Частина II  Розділ 4

 (біт/сим);

(біт/сим), (біт/сим);

(біт/сим);

 (біт/сим),  (біт/сим),  (біт/сим);

 (біт/сим),  (біт/сим);

L(X)=7 (біт), R(X)=0,7;

L(X)=13 (біт), L(X)=6 (біт);

L(X)=9 (біт);

 

Частина II  Розділ 5

Шеннона-Фано, Хаффмена (біт/сим), арифметичний (біт/сим);

Шеннона-Фано, Хаффмена (біт/сим), арифметичний (біт/сим);

Шеннона-Фано, Хаффмена  (біт/сим), арифметичний  (біт/сим);

Шеннона-Фано, Хаффмена  (біт/сим), арифметичний  (біт/сим);

Шеннона-Фано, Хаффмена L(X)=6 (біт), арифметичний L(X)=1 (біт);

L(X)=4 (біт);

L(X)=9 (біт);

BAABCB;

BBABB;

BAABC;

а) 000100; б) 000001; в) 010000;

 

Частина II  Розділ 6

Код повідомлення: ‘A’10‘B’00‘C’000‘D’00011001111100110011001, довжина стиснутого повідомлення Lcode(X)=62 (біт), довжина вхідного коду LASCII+(X)=112 (біт);

Код повідомлення: ‘К’0‘И’00‘Б’100‘Е’000‘Р’1100‘Н’1111000‘Т’1001 10111, довжина стиснутого повідомлення Lcode(X)=85 (біт), нестиснутого - LASCII+(X)=88 (біт);

Закодоване повідомлення AFXAFFXFXAXAFFA, довжина коду стиснутого повідомлення Lcode(X)=52 (біт), довжина ASCII+- коду LASCII+(X)=120 (біт);

Закодоване повідомлення DBBCAABCCB, довжина стиснутого повідомлення Lcode(X)=53 (біт), довжина ASCII+- коду LASCII+(X)=80 (біт);

Код повідомлення: ‘М’0‘А’00‘Т’100‘Е’101001000‘И’0000‘К’10, довжина стиснутого повідомлення Lcode(X)=69 (біт),  довжина коду вхідного повідомлення LASCII+(X)=80 (біт);

Закодоване повідомлення: BDCBDDCDCBCBDDB, довжина стиснутого повідомлення Lcode(X)=52 (біт), нестиснутого – LASCII+(X)=120 (біт);

Закодоване повідомлення: КРАСНАЯ КРАСКА, довжина коду стиснутого повідомлення Lcode(X)=91 (біт), нестиснутого – LASCII+(X)=112 (біт);

Код повідомлення: ‘П’0‘Р’00‘О’100‘Г’11000‘А’1000‘М’0101011, довжина стиснутого повідомлення Lcode(X)=70 (біт), довжина коду вхідного повідомлення LASCII+(X)=72 (біт);

Код: ‘Т’0‘Е’00‘О’100‘Р’000‘И’1100‘Я’1000‘  ’1010100‘Н’11100‘Ф’ 10001011000‘М’01100‘А’01000‘Ц’0000, довжина стиснутого повідомлення Lcode(X)=150 (біт), нестиснутого – LASCII+(X)=136 (біт);

Закодоване повідомлення: ВО ДВОРЕ ДВОРНИК, довжина коду стиснутого повідомлення Lcode(X)=117 (біт), нестиснутого – LASCII+(X)=128 (біт);

Закодоване повідомлення: XFZFXZAXFFX, довжина коду стиснутого повідомлення Lcode(X)=53 (біт), нестиснутого – LASCII+(X)=88 (біт);

 

Частина II  Розділ 7

LZ77: <0,0,‘A’> <11,1,‘B’> <0,0,‘C’> <0,0,‘D’> <7,2,‘C’> <11,1,‘C’> <5,2,‘B’> <0,0,‘B’>; Lcode=120 (біт). LZSS: 0‘A’ 1<11,1> 0‘B’ 0‘C’ 0‘D’ 1<7,2> 1<8,1> 1<11,1> 1<10,2> 1<5,1> 1<2,1> 1<11,1>; Lcode=92 (біт);

LZ77: <0,0,‘К’><0,0,‘И’><0,0,‘Б’><0,0,‘Е’><0,0,‘Р’> <0,0,‘Н’> <9,1,‘Т’> <5,1,‘К’> <0,0,‘И’>; Lcode=135 (біт). LZSS: 0‘К’ 0‘И’ 0‘Б’ 0‘Е’ 0‘Р’ 0‘Н’ 1<9,1> 0‘Т’ 1<5,1> 1<3,2>; Lcode=84 (біт);

LZ77: <0,0,‘С’> <0,0,‘Т’> <0,0,‘Р’> <0,0,‘А’> <0,0,‘Н’> <11,1,‘Ы’> <0,0,‘Й’> <0,0,‘  ’> <3,4,‘Н’> <11,1,‘И’> <0,0,‘К’>; Lcode=165 (біт). LZSS: 0‘С’ 0‘Т’ 0‘Р’ 0‘А’ 0‘Н’ 1<11,1> 0‘Ы’ 0‘Й’ 0‘  ’ 1<3,4> 1<3,2> 0‘И’ 0‘К’; Lcode=111 (біт);

LZ77: <0,0,‘B’> <0,0,‘D’> <0,0,‘C’> <9,2,‘D’> <8,1,‘D’> <6,2,‘C’> <4,3,‘B’> <10,2,‘D’><3,1,‘C’>; Lcode=135 (біт). LZSS: 0‘B’ 0‘D’ 0‘C’ 1<9,2> 1<8,2> 1<6,3> 1<4,4> 1<9,2> 1<10,2> 1<3,2>; Lcode=76 (біт).

AABCDAACCCCDBB; =120 (біт); =92 (біт);

/WED/WE/WED/WEB/WEE/WEB/WEE/E;=150(біт);=101(біт);

ВО ДВОРЕ ТРАВА НА ТРАВЕ ДРОВА;=225 (біт);=192 (біт);

LZ78: <0,‘A’> <1,‘B’> <0,‘C’> <0,‘D’> <1,‘A’> <3,‘C’>  <6,‘D’> <0,‘B’> <0,‘B’>; Lcode=108 (біт). LZW: 0‘A’ 0‘A’ 0‘B’ 0‘C’ 0‘D’ <256> 0‘C’ <262> <259> 0‘B’ 0‘B’; Lcode=99 (біт);

LZ78: <0,‘К’> <0,‘И’> <0,‘Б’> <0,‘Е’> <0,‘Р’> <0,‘Н’> <4,‘Т’> <2,‘К’> <0,‘И’>; Lcode=108 (біт). LZW: 0‘К’ 0‘И’ 0‘Б’ 0‘Е’ 0‘Р’ 0‘Н’ 0‘Е’ 0‘Т’ 0‘И’ <256>; Lcode=90 (біт);

 LZ78: <0,‘C’> <0,‘Т’> <0,‘Р’> <0,‘А’> <0,‘Н’> <5,‘Ы’> <0,‘Й’> <0,‘  ’> <1,‘Т’> <3,‘А’> <5,‘Н’> <0,‘И’> <0,‘К’>; Lcode=156 (біт). LZW: 0‘С’ 0‘Т’ 0‘Р’ 0‘А’ 0‘Н’ 0‘Н’ 0‘Ы’ 0‘Й’ 0‘  ’ <256> <258> <260> 0‘И’ 0‘К’; Lcode=126 (біт);

LZ78: <0,‘B’> <0,‘D’> <0,‘C’> <1,‘D’> <2,‘C’> <5,‘B’> <3,‘B’> <2,‘D’> <4,‘B’> <2,‘B’> <0,‘C’>; Lcode=132 (біт). LZW: 0‘B’0‘D’0‘C’ <256> <257> <257> 0‘B’ <258> 0‘D’ 0‘D’ <256> <266> 0‘C’; Lcode=117 (біт);

AABCDAACCCCDBB; =108 (біт); =99 (біт);

/WED/WE/WED/WEB/WEE/WEB/WEE/E;=168(біт);=144 (біт);

ВО ДВОРЕ ТРАВА НА ТРАВЕ ДРОВА;=234 (біт); =207 (біт).

 

Частина III  Розділ 9

P(Y=00/X=00)=pp, P(Y=00/X=01)=pq, , P(Y=00/X=11)=qq,  ;

 0,3%;  7,7 %;

Даний код є лінійним систематичним блоковим; ; ; код здатний виявляти 2 і виправляти 1 помилку;

000 0000000, 001 0011001, 010 0101010, , 111 1111111; код виявляє помилки кратності 2 і виправляє помилки кратності 1; Pпом=3p4q3+3p3q4+q73p4q3+3p3q4; 1001100100, 01010110101010 010, 00111010011001 001;

0000000, 0010010, 0100101, 0110111, 100 1001, 1011011, 1101100, 1111110; dmin=1; Pпом=p3q+3p2q2+3pq3; код виявляє тільки три ситуації наявності однієї помилки в коді з чотирьох можливих ;

dmin=3, код виявляє 2 і виправляє 1 помилку; Pпом=2p3q3+q62p3q3; 101110101010;010100010101;101111111111;

; Pпом=9p5q4+6p3q69p5q40,899610-15;

1101110011100111100110000;

;

00110000000001110011000000000011001000000;

00000011111011110000001111001111000001110;

01010000000001110100000000000101010000000;  надлишковість коду до0,44.

 

Частина III  Розділ 10

; S=(y2+y3+y4, y1+y2+y5, y1+y2+y3+y6);

101101011, 001001110; 011001011101011, 110100110110110, 001111 001110001;

S=(y1+y4+y5, y2+y5+y6, y3+y4+y6); 000000000, 001001101, 010010011, 011 011110, , 111111000;

S=(y1+y2+y3+y4+y5, y1+y3+y4+y6, y1+y2+y4+y7, y1+y2+y3+y8);

S=(y1+y2+y5, y3+y4+y6, y1+y3+y7, y2+y4+y8, y1+y2+y3+y4+y9); код виявляє помилки кратності 3 і виправляє помилки кратності 1;

00100010011, 10101010101, 11101110010; S=(y1+y2+y4+y5, y1+y2+y3+y6, y2+y3+y4+y7); код виявляє помилки кратності 2 і виправляє помилки кратності 1;

00100010111, 10101010001, 11101110010; 101010110100011010, 00101010010111 0010; S=(y1+y3+y4+y5, y1+y2+y3+y6, y2+y3+y4+y7); код здатний виявляти 2 і виправляти 1 помилку;

0110010 0110011 0110, 1101001 1101, 0111100  0111, 0011110  0010110   0010;

1101001 1100; 0110011 0010; 0111100 0110; 0011110 0011;

; n=7, k=4; dmin=3;

.

 

Частина III  Розділ 11

1100110 10111000110, 1010111 10110101111;

;  надлишковість коду к0,364;

1010 1011010, 1100 0111100; 1011 0110011; ;  к0,429;

11001111110011, 10100101101000, 10110  011001100; ; надлишковість к0,444;

110011110, 101101101, 011110011, 111001011; ; надлишковість к=0,5;

11111010110 011111101010110;

011001 1000110101; 100011 0010000011; к=0,4;

011001010001101010; 100011111100001111; к0,364;

01100100 100011010100, 10001101 001100011101;

110110001010110  11001010110;

11011001001100 0100; 10111011010101 1101; 1010101 1101.

 

Частина III  Розділ 12

0100 01100010100, 10001101110011101111001, 11110 100011100110;

;

010111101011111011111101011111;

,  10010111011

 111110010111011, код виявляє 2 і виправляє 1 помилку;

dmin=4; код виявляє 3 і виправляє 1 помилку;  Pпом=7p3q46,99810-16;

1100100011110101100, 0011110101100100011; dmin=6; код здатний виявляти помилки кратності 5 і виправляти помилки кратності 2, ймовірність невиявлення помилки Pпом=p9q6+7p8q7+3p7q8+p5q10;

0111011 0111010, 1011010 1011000;

01110110111001, 10111011011100;

;

1101011 1001011 011, 1110011 1110010 010;

0111010011, 1101001110, 1010011101.

Список використаної та рекомендованої літератури

 

Блейхер Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.

Жураковський Ю.П., Полторак В.П. Теорія інформації та кодування: Підручник. – К.: Вища школа, 2001. – 255 с. 

Кузьмин И. В. Основы теории информации и кодирования. – Минск: Вышэйшая школа,1986.

Лидовский В.В. Теория информации: Уч. пособие. - М.: Компания Спутник+, 2004. - 111 с.

Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 1976.

Стратонович Р.Л. Теория информации. – М: Изд-во “Сов. Радио”, 1975.

Хемминг Р.В. Теория информации и теория кодирования. – М. Радио и связь, 1983.

Цымбал В.П. Теория информации и кодирование. – К. Вища школа, 1992. – 263 с.

Чисар И., Кернер Я. Теория информации. – М.: Мир, 1985.

Шеннон К.-Э. Работы по теории информации и кибернетике. – М.: Изд-во иностр. Лит., 1963. 830 с.

Шульгин В. И. Основы теории передачи информации: Учебное пособие. Ч. I. Экономное кодирование. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2002. - 100 с.

Шульгин В. И. Основы теории передачи информации: Учебное пособие. Ч. II. Помехоустойчивое кодирование. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2002. – 90 с.