УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к курсу КОНСТРУКТИВНАЯ АЛГЕБРА


Коды Хаффмана и Шеннона-Фано

1. Построить коды Хаффмана и Шеннона-Фано для алфавита, определить среднюю длину этих кодов и энтропию

1.1.

e t a o n r i h s d
вероятность 0.175 0.121 0.115 0.108 0.095 0.088 0.085 0.081 0.078 0.054

1.2.

e t a o n r i h s d \ell_{}
вероятность 0.168 0.116 0.110 0.103 0.090 0.084 0.081 0.077 0.075 0.051 0.045

2. Количество двоичных разрядов кода Хаффмана для буквы алфавита S_j, имеющей вероятность P_j, не превосходит \lceil \log_2 P_j \rceil. Всегда ли верно это утверждение? Здесь \lceil A \rceil обозначает наименьшее целое число превосходящее A_{}.

Шифры

Кодировка

а б в г д е,ё ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
0102 03 0405 06 07 0809 10 11 12 13 14 15 16 17 18 1920 21 22 23 24 25 2627 2829 30 3132
пробел
00

Шифровки обычные

1.

M:=201906250603000112061118061000311773244621158601400946888593605553995981;

E:=78910975532289220935753515625017094783121510124107731793252244976855061;

c:=2286788192763459173214787438763086831991337526673752242547389576641553;


2.

M:=622155891532439224608224121181518987294943918107726259160930642901415303;

E:=363391103509586870271720155598896381953471200698345931024527062419175601;

c:=295219331281603935865490086544586226856167677528296688144882147338624341;


3.

M:=6866668545940922074908014569814547864349352664613085324215218559854749;

E:=371141760349502611840571333249700586477849123165009272031606918872233;

c:=1858160360128579128726056126970913077388960916292272343787100436573729;


4.

M:=87938099056667387502699616929504740078435638151822120660333872686511;

E:=20917472554482321082464931619291998384412194446704670559346863587371;

с:=46313182863904963268033988419985899193064032129620696542131190846796;


5.

M:=64609769579611429997353694966383437261513111047091761154563552911357;

E:=48065638707770555338831231217031917564303159626730871598644464074467;

c:=39884319333375821769923105040126640733677785692045012810179363873377;


6.

M:=546472911447379420092489211703343424357323909547477947863606544254401;

E:=169653548828601360273983836939630290079378121133489465146563736686269;

c:=425358833577329072964488691659373050440030274027537685960019326754444;


7.

M:=1148285936379729603191237775175300844601714012792980566867726085486797;

E:=33281748319244107017616106353162118826359031926583924722704126845889;

c:=482770786368849986982168013837936271185928240129900833099129264564894;


8.

M:=267286023468127811237456852727383953576497792996544723370123750737;

E:=217194106495094429330842417450473225954381026295609158085699307921;

c:=198789437358690720768151855951918393164298966734494932511660361748;


9.

M:=423957441810454286477471709354132352924475106024912896571144853261416249442379668129;

E:=169290536533851680079962817041033605478571723750120416518080757723681512639461417273;

c:=413923465311778547334244940628879181205079121649256861060875309288673251751931030850;


10.

M:=648260107575268814265371780546654840030435733664832906157532874682052921804307894977;

E:=111999379827693161117158283088023881181180919868782416776584794778670574577330138419;

c:=622603425162818795366722251992062839540662569230360069592403595458588578294362269309;


11.

Сode chart

a b c d e f g h i j k l m n o p q r s t u v w x y z
0102 03 0405 06 07 0809 10 11 12 13 14 15 16 17 18 1920 21 22 23 24 25 26
space
00

M:=88831556288049781893094489733622009941345390278309270519438478117919601627:

E:=21059796197750960172668055248563150872379386315483177974373332925393127673:

c:=4077137491632769572879370857328973054213777712202424374222171607677933164:

Шифровки "серьезные"

1. Метод Ферма

M:=38156877939390531717103399196833583092738956781697046758805633214857101281543564706150986821166369731473418905754107317271;

E:=7123903;

c:=31467125324198545314913130179632831994033781560098663054299098480847271139768419136815733559406184868426593267189807830213;


2. Метод Полларда

M:=146481808053566948606112326494160580676597757390203425433760346556289969224977192583652803722778590707655656624536558761037114144280380743982554672552469432942539798288533;

E:=7770779;

c:=50482193893295118672212227596255206609978317479891567490511905296629661164408165727901970750204892065138791242602754754520133030233374524172418377404891017560153125158450;


3. «Грубой силой» (ключ дешифрования неединствен)

M:=9613446207196760465265550772396282011688328975583766866478433072787610046364647672928483668662126373713147;

E:=1733083321784945072242332532597091505043371130605301519657982898470859115128777785579573177143061586122183;

c:=3749348489128656036183724837562853897726179340249603541464488050651523920742856056497795387433000363629409;


4. Атака «малых показателей»

M_1:=39019872114650490565656726120949795718447441501355748193872215486631299366943417270072829553408804569592841;

c_1:=5553981688493884961215872422136918654146307847582570407629691326271556780196541068768266407809908202308413;

M_2:=480315733974479079535757225644107075404254750084615569566793312330968613057798782886865928167609155838747;

c_2:=211594077959659879149619186864253742923568755703075264920968112168072435327321609710156883876404900243650;

M_3:=88163452352292054404338751236135405169837433431930150283460737329548730880081812127430897691430890475113627;

c_3:=72726538492586395413794327840834032298698133522451808268997078866999740284940113940934122069567372127153154;


5. Второй простой множитель модуля сгенерирован из первого с помощью алгоритма примера 8.12.

M:=68279496425898075950266968065586412561333035171910872531705337687171857266652614768491760336772187917038902402063089703114707613266827355951107317223329;

E:=20695704892405605169718592309414224630269961361448389881288915440703097629292764120778495337544728304487995001384482687390651011791007868295732918184661;

c:=1909049019315227130269888122521268323760308346299782885009035555457910932106370103606709550531848220025477932876971854940350282582438364426189374206213.


6. Ключ шифрования агента 007:

M:= 10569099686598115280572425936884803247492504152712534709638709002080141504197905180970411035667203895670791462367736271483438693985393492562809357092999032549;

E:=77777777777;

В результате оперативных действий контрразведки «Смерш» удалось добыть ключ дешифрования

D:=2310739329568690598298133398870797186733463902196941863656341052171332673362256753289624242463662936556136845699643143045132095984852330096782304797739596797.

Заподозрив неладное, агент 007 меняет ключи шифрования и дешифрования:

E1:=7777777777777777777,

но не меняет модуль шифрования M_{}. Докажите ему, что он абсолютно не прав и дешифруйте:

c:=7943587685191243004457068759714674026176034115802088702532268583596839683057916153359166565654394321330756777638998792758429928404460298469084511047154767040.

Ключ АУ

Mm:=4077599079861103062161070927516158477409733157845537591441632356483314364489065340039377643553910891;(100 цифр)

Em:=25092117;

Поля Галуа

Вычислить \mathfrak a \cdot \mathfrak b, \mathfrak a / \mathfrak b для элементов поля \mathbf{GF}(2^8) при заданном порождающем полиноме f(x).

1. f(x)=x^8+x^4+x^3+x^2+1, \mathfrak a=(11100111), \mathfrak b = (01010101);

2. f(x)=x^8+x^6+x^5+x^4+1, \mathfrak a=(11100111), \mathfrak b = (10101010);

3. f(x)=x^8+x^4+x^3+x+1, \mathfrak a = (01010101), \mathfrak b=(11100111);

4. f(x)=x^8+x^7+x^5+x^4+1, \mathfrak a = (01100110), \mathfrak b=(11100111);

Будет ли (a) (00000011); (б) (00000111); (в) (00001001) примитивным элементом поля? В случае положительного ответа, вычислить дискретные логарифмы элементов \mathfrak a и \mathfrak b, и проверить правильность операции деления.

Линейные коды

2. Линейный (8,4)-код задан соотношениями

\begin{array}{rrrrr} x_4= & x_1 & +x_2 & +x_3 & \\ x_6=& x_1 & +x_2 & & +x_5 \\ x_7=& x_1 & &+x_3 & +x_5 \\ x_8=& & x_2 & +x_3 & +x_5 \end{array}

Каково его кодовое расстояние?

3. (7,4)-код Хэмминга дополняется до (8,4)-кода присоединением дополнительного разряда проверки четности:

x_8 = x_1+\dots+x_7 \pmod{2} \ .

Какой вид имеет проверочная матрица нового кода? Каково его кодовое расстояние?

4. Циклический код порожден полиномом g_{}(x). Исправить ошибки в полиноме \tilde G(x) для

4.1. g(x)= 1+x+x^2-x^3-x^4-x^5+x^6+x^7+x^8 ,\ n=18,

\tilde G(x)= 10+4\,x+8\,x^2-15\,x^3-9\,x^4-12\,x^5+12\,x^6+13\,x^7+18\,x^8+8\,x^9-8\,x^{11}-11\,x^{12}-5\,x^{13}+4\,x^{14}+9\,x^{15}+9\,x^{16}+2\,x^{17} \ ;

4.2. g(x)= 1+2\,x+3\,x^2+3\,x^3+3\,x^4+3\,x^5+3\,x^6+2\,x^7+x^8, n=21,,

\begin{array}{ccl} \tilde G(x)&=& -1+7\,x+14\,x^2+23\,x^3+23\,x^4+28\,x^5+24\,x^6+15\,x^7-3\,x^8-17\,x^9-33\,x^{10}-38\,x^{11}-40\,x^{12}-30\,x^{13}- \\ & & -17\,x^{14}-7\,x^{15}+2\,x^{16}+7\,x^{17}+12\,x^{18}+9\,x^{19}+2\,x^{20}; \end{array}

4.3. g(x)=1+x+x^2+x^{12}+x^{13}+x^{14}, \ n=24,

\begin{array}{ccl} \tilde G(x)&=& -1+8\,x+7\,x^2+9\,x^3+5\,x^5-3\,x^6-11\,x^7-15\,x^8-2\,x^9+3\,x^{10}+5\,x^{11}+8\,x^{13} + \\ && +7\,x^{14}+9\,x^{15}+5\,x^{17}-3\,x^{18}-11\,x^{19}-15\,x^{20}-3\,x^{21}+5\,x^{22}+5\,x^{23}; \end{array}

4.4. g(x)=1-x+x^4-x^6+x^8-x^{11}+x^{12}, \ n=20,

\begin{array}{ccl} \tilde G(x)&=& -1+x+8\,x^2-7\,x^3-2\,x^4+4\,x^5+x^6+13\,x^7-17\,x^8+3\,x^9+4\,x^{10}+6\,x^{11}+3\,x^{12}- \\ && -11\,x^{13}+10\,x^{15}-4\,x^{16}+8\,x^{17}-12\,x^{18}+8\,x^{19} ; \end{array}

5. Кодовое слово закодировано стандартной кодировкой и далее несистематическим способом кодирования циклическим кодом, порожденным полиномом g_{}(x). Исправить ошибки в полиноме \tilde G(x) и декодировать исходное сообщение для

5.1. g(x)= 1-2\,x^2+2\,x^4-2\,x^6+2\,x^8-x^{10} ,\ n=20,

\begin{array}{ccl} \tilde G(x)&=& 1 + 9\,x - 2\, x^2 - 17\, x^3 + 3\, x^4 + 16\, x^5 - 4\, x^6 - 12\, x^7 + 3\, x^8 + 9\, x^9 - x^{10} - x^{11} + 2\,x^{12}- \\ & & - 7\, x^{13} - x^{14} + 6\, x^{15} - 2\, x^{17} - x^{19} \ ; \end{array}

5.2. g(x)= -1+2\,x-2\,x^2+2\,x^3-2\,x^4+2\,x^5-2\,x^6+2\,x^7-2\,x^8+2\,x^9-2\,x^{10}+x^{11} ,\ n=22,

\begin{array}{ccl} \tilde G(x)&=& -1-6\,x+13\,x^2-14\,x^3+15\,x^4-19\,x^5+24\,x^6-27\,x^7+29\,x^8-33\,x^9+38\,x^{10}-39\,x^{11}+32\,x^{12}-25\,x^{13}+\\ & & +24\,x^{14}-23\,x^{15}+18\,x^{16}-13\,x^{17}+13\,x^{18}-9\,x^{19}+5\,x^{20} \ ; \end{array}

6. Кодовое слово закодировано стандартной кодировкой и далее систематическим способом кодирования циклическим кодом, порожденным полиномом g_{}(x). Исправить ошибки в полиноме \tilde G(x) и декодировать исходное сообщение для

6.1. g(x)=1-x^2+x^6-x^{10}+x^{12} ,\ n=24,

\begin{array}{ccl} \tilde G(x)&=& 1+12\,x+x^2+11\,x^3+x^4-x^5+4\,x^7+x^8+14\,x^9+x^{10}+5\,x^{11}+x^{12}+3\,x^{13}+ \\ && +6\,x^{15}+8\,x^{17}+9\,x^{19}+x^{20}+5\,x^{21} \ ; \end{array}

6.2. g(x)=-1+2\,x^2-2\,x^4+2\,x^6-2\,x^8+x^{10} ,\ n=20,

\begin{array}{ccl} \tilde G(x)&=&-5-59\,x+7\,x^2+73\,x^3-6\,x^4-61\,x^5+6\,x^6+70\,x^7-5\,x^8-55\,x^9+x^{10}+6\,x^{11}+2\,x^{12}+8\,x^{13}+\\ && +3\,x^{15}+6\,x^{17}+x^{18}+9\,x^{19} \ . \end{array}

7. В книге

Акритас А. Основы компьютерной алгебры с приложениями. М. Мир. 1994

на сс.248-249 приведен следующий алгоритм исправления ошибок в циклическом коде1).

Пусть g_{}(x) — порождающий полином кода, \deg [g(x)]=r, и пусть a_{k-1}, a_{k-2},\dots,a_0 — сообщение с k=n-r информационными битами. Тогда этот полином рассматривается как полином над \mathbf{GF}(2) и кодируется как G(x)= a(x)g(x).
Декодирование. Полученный полином \tilde G(x) делим на g_{}(x) (остаток от этого деления — это синдром полинома \tilde G(x) ). Если в результате деления получен ненулевой остаток, то должна иметь место ошибка передачи. Чтобы распознать ошибку e(x), мы вычисляем произведение e(x)h(x) \pmod{x^n-1}, где h_{}(x) — проверочный полином кода. В соответствии со сделанными ранее замечаниями \tilde G(x)h(x)=(G(x)+e(x))h(x) = 0 + e(x)h(x) \pmod{x^n-1}. Тогда разделив произведение на h_{}(x), получим полином ошибки e(x), и G(x)= \tilde G(x) - e(x). Разделив G_{}(x) на g_{}(x), мы получаем переданное сообщение.

Найти ошибку в этом рассуждении. Привести контрпример.

8. Пусть циклический n_{}-код C_1 порождается полиномом g_1(x), а циклический n_{}-код C_2 порождается полиномом g_2(x). Назовем пересечением кодов C_1 и C_2 множество C_1 \cap C_2 векторов, принадлежащих как C_1, так и C_2; назовем суммой кодов C_1 и C_2 множество C_1 + C_2 векторов, составляющих сумму этих линейных подпространств. Доказать, что C_1 \cap C_2 и C_1 + C_2 будут циклическими n_{}-кодами и найти их порождающие полиномы.

9. Cуществуют ли в поле \mathbf{GF}(2^n) решения уравнения а) \mathfrak x^2 =\mathfrak e; б) \mathfrak x^3 =\mathfrak e, отличные от \mathfrak x =\mathfrak e ?


§

В следующих примерах вычисления ведутся в поле \mathbf{GF}(2^5) при \mathfrak a=(0,0,0,1,0) и умножении, определенному по модулю 2, x^5+x^2+1.

10. При записи информационной строки, состоящей из пятибитных блоков

X_1=(1,1,1,0,0),\ X_2=(1,1,0,1,1),\ X_3=(*,*,*,*,*),\ X_4=(*,*,*,*,*),X_5=(1,0,1,0,1),X_6=(*,*,*,*,*)

произошла потеря содержимого указанных блоков. Восстановить это содержимое по известным значениям синдромов:

\sum_{i=1}^6 X_i=(0,1,1,0,0);\ \sum_{i=1}^6 X_i\mathfrak a^{i-1}=(1,0,1,0,1);\ \sum_{i=1}^6 X_i\mathfrak a^{2(i-1)}=(1,1,1,1,0)\ .

11. Информационные пятибитные блоки X_1,\dots,X_5 кодируются с помощью служебных блоков Y_1,\dots, Y_7 по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a) \sum_{i=1}^5 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^7 Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(0,0,1,1,0),\ \tilde Y_2=(1,0,1,0,0),\ \tilde Y_3=(1,1,0,0,0),\ \tilde Y_4=(1,1,0,1,1),\ \tilde Y_5=(1,0,1,0,0),\tilde Y_6=(1,0,1,0,0),
\tilde Y_7=(0,0,1,1,0) \ .

Один из этих блоков ошибочен. Исправить его и восстановить \{X_i\}.

12. Информационные пятибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_8 по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^8 Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(1,1,1,0,0),\ \tilde Y_2=(0,0,1,1,0),\ \tilde Y_3=(0,0,1,0,0),\ \tilde Y_4=(1,0,1,0,0),\ \tilde Y_5=(0,0,1,0,1),\tilde Y_6=(1,0,0,0,0),
\tilde Y_7=(1,0,0,0,0),\ \tilde Y_8=(1,1,1,0,0) \ .

Один из этих блоков ошибочен. Исправить его и восстановить \{X_i\}.

13. Информационные пятибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{10} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{10} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(1,0,0,1,0),\ \tilde Y_2=(1,1,0,0,1),\ \tilde Y_3=(1,1,1,1,0),\ \tilde Y_4=(0,1,0,0,1),\ \tilde Y_5=(1,1,1,1,1),
\tilde Y_6=(1,1,1,0,0),\ \tilde Y_7=(1,1,0,1,1),\ \tilde Y_8=(0,0,1,1,0), \ \tilde Y_9=(0,1,1,1,1),\ \tilde Y_{10}=(0,1,1,0,0) .

Два из этих блоков ошибочны. Исправить их и восстановить \{X_i\}.

14. Информационные пятибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{9} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{9} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(1,0,0,0,0),\ \tilde Y_2=(*,*,*,*,*),\ \tilde Y_3=(0,1,0,1,0),\ \tilde Y_4=(0,1,1,1,1),\ \tilde Y_5=(1,1,1,1,0),
\tilde Y_6=(0,1,1,0,1),\ \tilde Y_7=(0,1,0,0,0),\ \tilde Y_8=(0,0,1,1,1), \ \tilde Y_9=(0,1,1,0,0)\ .

Произошла потеря содержимого указанного блока и ошибка при передаче еще одного блока (номер которого неизвестен, но \ne 2). Исправить ошибки и восстановить \{X_i\}.


Информационные пятибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{10} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{10} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков, два из которых ошибочны. Исправить их и восстановить \{X_i\}.

14.1.

\tilde Y_1=(1,1,1,0,0),\ \tilde Y_2=(0,1,0,0,1),\ \tilde Y_3=(0,0,0,0,1),\ \tilde Y_4=(0,1,0,0,1),\ \tilde Y_5=(0,0,0,1,0),
\tilde Y_6=(0,0,0,1,1),\ \tilde Y_7=(0,0,0,0,1),\ \tilde Y_8=(1,0,1,1,1), \ \tilde Y_9=(0,1,0,1,0),\ \tilde Y_{10}=(1,0,0,0,1) .

14.2.

\tilde Y_1=(0,1,1,1,1),\ \tilde Y_2=(0,0,1,1,1),\ \tilde Y_3=(0,1,1,1,0),\ \tilde Y_4=(0,0,1,1,1),\ \tilde Y_5=(0,0,1,1,1),
\tilde Y_6=(0,0,1,1,0),\ \tilde Y_7=(1,1,0,1,1),\ \tilde Y_8=(1,1,1,0,0), \ \tilde Y_9=(1,1,0,1,1),\ \tilde Y_{10}=(0,1,1,1,0) .

14.3.

\tilde Y_1=(1,1,0,0,1),\ \tilde Y_2=(1,0,0,0,0),\ \tilde Y_3=(1,1,1,1,0),\ \tilde Y_4=(1,1,1,1,0),\ \tilde Y_5=(1,1,1,1,1),
\tilde Y_6=(1,0,0,0,1),\ \tilde Y_7=(1,1,1,0,1),\ \tilde Y_8=(1,0,1,1,0), \ \tilde Y_9=(0,0,1,0,0),\ \tilde Y_{10}=(1,1,1,1,1) .

Информационные пятибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{12} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3)(\mathfrak x+ \mathfrak a^4) (\mathfrak x+ \mathfrak a^5)\sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{12} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков, два или три из которых ошибочны. Исправить их и восстановить \{X_i\}.

14.4.

\tilde Y_1=(0,0,1,1,0),\ \tilde Y_2=(1,1,1,1,0),\ \tilde Y_3=(1,1,0,1,0),\ \tilde Y_4=(1,1,1,0,1),\ \tilde Y_5=(1,0,0,0,1),
\tilde Y_6=(0,0,0,1,0),\ \tilde Y_7=(1,1,0,1,0),\ \tilde Y_8=(1,0,0,0,1), \ \tilde Y_9=(1,1,1,0,1),\ \tilde Y_{10}=(1,1,0,0,1),
\tilde Y_{11}=(0,1,1,1,1), \tilde Y_{12}=(0,1,1,0,0) \, .

14.5.

\tilde Y_1=(1,1,1,0,1),\ \tilde Y_2=(1,0,0,0,0),\ \tilde Y_3=(1,1,0,1,1),\ \tilde Y_4=(1,1,0,0,0),\ \tilde Y_5=(0,1,0,1,1),
\tilde Y_6=(1,0,0,1,0),\ \tilde Y_7=(0,0,0,0,1),\ \tilde Y_8=(1,1,0,1,0), \ \tilde Y_9=(0,0,0,1,1),\ \tilde Y_{10}=(1,1,1,1,0),
\tilde Y_{11}=(1,0,0,0,1), \tilde Y_{12}=(0,0,0,1,0) \, .

14.6.

\tilde Y_1=(0,0,1,1,1),\ \tilde Y_2=(0,1,0,1,1),\ \tilde Y_3=(1,0,0,1,1),\ \tilde Y_4=(1,0,1,1,1),\ \tilde Y_5=(1,1,1,1,1),
\tilde Y_6=(0,1,1,1,0),\ \tilde Y_7=(0,1,1,1,0),\ \tilde Y_8=(0,1,1,1,0), \ \tilde Y_9=(0,1,0,0,1),\ \tilde Y_{10}=(1,1,0,1,1),
\tilde Y_{11}=(0,0,1,1,1),\ \tilde Y_{12}=(1,0,0,0,1).

14.7.

\tilde Y_1=(1,1,0,0,0),\ \tilde Y_2=(0,1,1,1,0),\ \tilde Y_3=(1,0,0,0,0),\ \tilde Y_4=(1,1,0,0,0),\ \tilde Y_5=(1,1,0,0,0),
\tilde Y_6=(0,0,1,0,1),\ \tilde Y_7=(0,0,1,0,0),\ \tilde Y_8=(0,1,0,1,0), \ \tilde Y_9=(1,1,0,0,0),\ \tilde Y_{10}=(0,0,1,0,1),
\tilde Y_{11}=(1,1,0,0,0),\ \tilde Y_{12}=(0,0,0,0,1).
§

В следующих примерах вычисления ведутся в поле \mathbf{GF}(2^6) при \mathfrak a=(0,0,0,0,1,0) и умножении, определенному по модулю 2, x^6+x+1.

15. Информационные шестибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{10} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{10} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(0,0,1,1,0,0),\ \tilde Y_2=(0,1,1,0,0,1),\ \tilde Y_3=(1,1,1,0,0,1),\ \tilde Y_4=(1,0,1,1,1,0),\ \tilde Y_5=(0,1,0,1,0,0),
\tilde Y_6=(1,1,0,0,1,0),\ \tilde Y_7=(0,0,0,1,0,1),\ \tilde Y_8=(1,1,1,0,1,1), \ \tilde Y_9=(0,1,1,1,0,0),\ \tilde Y_{10}=(0,1,1,0,0,0) .

Один или два из этих блоков ошибочны. Исправить их и восстановить \{X_i\}.

16. Информационные шестибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{9} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{9} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(1,0,1,1,0,0),\ \tilde Y_2=(1,1,1,1,1,1),\ \tilde Y_3=(0,0,1,1,1,0),\ \tilde Y_4=(1,0,0,1,1,1),\ \tilde Y_5=(0,1,0,0,1,1),
\tilde Y_6=(1,1,0,1,0,1),\ \tilde Y_7=(0,0,0,1,1,0),\ \tilde Y_8=(1,0,0,0,1,0), \ \tilde Y_9=(0,0,0,0,1,0)\ .

Известно, что два подряд идущих блока ошибочны. Придумать алгоритм для их исправления и восстановить \{X_i\}.

17. Информационные шестибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{10} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{10} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(0,1,0,1,0,0),\ \tilde Y_2=(0,0,1,0,0,0),\ \tilde Y_3=(0,0,0,0,1,1),\ \tilde Y_4=(0,1,0,1,0,1),\ \tilde Y_5=(0,1,1,1,0,0),
\tilde Y_6=(1,1,0,0,0,0),\ \tilde Y_7=(1,1,0,1,0,0),\ \tilde Y_8=(0,1,0,1,0,0), \ \tilde Y_9=(0,1,1,1,0,0),\ \tilde Y_{10}=(0,1,1,0,1,0) .

Один или два из этих блоков ошибочны. Исправить их и восстановить \{X_i\}.


§

В следующем примере вычисления ведутся в поле \mathbf{GF}(2^6) при \mathfrak a=(0,0,0,0,1,0) и умножении, определенному по модулю 2, x^6+x^5+x^2+x+1.

18. Информационные шестибитные блоки X_1,\dots,X_6 кодируются с помощью служебных блоков Y_1,\dots, Y_{10} по правилу:

(\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3) \sum_{i=1}^6 X_i\mathfrak x^{i-1} \equiv \sum_{\ell=1}^{10} Y_{\ell}\mathfrak x^{\ell-1}\ .

На выходе канала связи получена строка, состоящая из блоков

\tilde Y_1=(1,0,1,0,1,1),\ \tilde Y_2=(0,0,1,1,1,1),\ \tilde Y_3=(0,1,1,0,1,0),\ \tilde Y_4=(1,0,1,0,1,0),\ \tilde Y_5=(1,0,1,0,1,0),
\tilde Y_6=(0,1,0,1,1,1),\ \tilde Y_7=(1,1,0,0,1,0),\ \tilde Y_8=(1,0,0,0,0,0), \ \tilde Y_9=(0,1,0,1,1,0),\ \tilde Y_{10}=(1,0,1,1,0,1) .

Один или два из этих блоков ошибочны. Исправить их и восстановить \{X_i\}.


19. [Маров А.В.]

В настоящем примере вычисления ведутся в поле \mathbf{GF}(2^8) при \mathfrak a=(0,0,0,0,0,0,1,0) и умножении, определенному по модулю 2, x^8+x^4+x^3+x^2+1. Информационные байты X_1,\dots,X_8 кодируются с помощью служебных байтов Y_1,\dots, Y_{10} по правилу систематического кодирования:

Y_1=X_1,\dots,Y_8=X_8 ,

а Y_9,Y_{10},Y_{11},Y_{12} определяются как коэффициенты остатка

Y_9 \mathfrak x^3+Y_{10} \mathfrak x^2+Y_{11} \mathfrak x+Y_{12}

от деления полинома \mathfrak x^4 \left(\sum_{i=1}^8 X_i\mathfrak x^{8-i} \right) на (\mathfrak x+\mathfrak e)(\mathfrak x+ \mathfrak a)(\mathfrak x+ \mathfrak a^2)(\mathfrak x+ \mathfrak a^3). На выходе канала связи получена строка, состоящая из байтов

\tilde Y_1=(0,0,0,0,0,0,0,0),\ \tilde Y_2=(0,0,0,0,0,1,1,1),\ \tilde Y_3=(0,0,0,0,0,0,0,0), \tilde Y_4=(0,1,1,1,0,1,1,0),
\tilde Y_5=(0,0,0,0,1,0,1,1),\ \tilde Y_6=(0,0,0,0,0,0,0,0),\ \tilde Y_7=(1,1,0,0,1,1,0,1),\ \tilde Y_8=(1,1,1,0,1,0,1,1),
\ \tilde Y_9=(0,0,0,0,0,0,0,0),\ \tilde Y_{10}=(0,0,1,1,0,0,0,0),\ \tilde Y_{11}=(0,0,1,1,1,1,0,0),\ \ \tilde Y_{12}=(0,1,0,1,1,0,1,1) ,

некоторые из которых ошибочны. Исправить их и восстановить \{X_i\}.

1) Я немного изменил обозначения.

2018/12/10 00:14 редактировал au