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

1.1.

1.2.

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

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.

M:=648260107575268814265371780546654840030435733664832906157532874682052921804307894977;

E:=131071;

c:=360116524087175795499279586531945667942674557492700734949391833903672196274133690495;

12.

Сode chart

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. Второй простой множитель модуля сгенерирован из первого с помощью алгоритма Поклинтона.

M:=68279496425898075950266968065586412561333035171910872531705337687171857266652614768491760336772187917038902402063089703114707613266827355951107317223329;

E:=20695704892405605169718592309414224630269961361448389881288915440703097629292764120778495337544728304487995001384482687390651011791007868295732918184661;

c:=1909049019315227130269888122521268323760308346299782885009035555457910932106370103606709550531848220025477932876971854940350282582438364426189374206213.

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

M:= 10569099686598115280572425936884803247492504152712534709638709002080141504197905180970411035667203895670791462367736271483438693985393492562809357092999032549;

E:=77777777777;

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

D:=2310739329568690598298133398870797186733463902196941863656341052171332673362256753289624242463662936556136845699643143045132095984852330096782304797739596797.

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

E1:=7777777777777777777,

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

c:=7943587685191243004457068759714674026176034115802088702532268583596839683057916153359166565654394321330756777638998792758429928404460298469084511047154767040.

Mm:=11123124002019062506030100011206111806320031172906030924010815745794759347585743707034598975904130141516993834908682683650731156906426563008706197799949609202996304843670166275359339203;(185 цифр)

Em:=25092119;

1. $$ \begin{array}{ccccccccccc} - 5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ -2817 & -1884 & - 1089 & -512 & - 145 & -12 & -159 & -514 & - 1185 & -2160 & -3457 \end{array} $$

2.

$$ \begin{array}{ccccccccccc} - 5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 185 & 129 & 93 & 56 & 25 & 2 & -19 & -64 & - 37 & -40 & -35 \end{array} $$

3. $$ \begin{array}{ccccccccccccc} -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ -781 & - 310 & -93 & -22 & -15 & -6 & 32 & 122 & 253 & 362 & 419 & 330 & 113 \end{array} $$

4. $$ \begin{array}{ccccccccccccc} -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ -343 & - 148 & -65 & -64 & -13 & -4 & 7 & -40 & -197 & -548 & -1201 & -2288 & -3960 \end{array} $$

5. $$ \begin{array}{ccccccccccccc} -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ -450 & - 169 & -30 & 13 & 10 & 3 & 46 & 185 & 470 & 943 & 1658 & 2660 & 4000 \end{array} $$

Вычислить $ \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 приведен следующий алгоритм исправления ошибок в циклическом коде¹⁾.

Пусть $ 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\} $.