!!§!! Вспомогательная страница к курсу ((:algorithms КОНСТРУКТИВНАЯ АЛГЕБРА))
----
==Задачи==
~~TOC~~
===Коды Хаффмана и Шеннона-Фано==
1.
Построить коды Хаффмана и Шеннона-Фано для алфавита, определить среднюю длину этих кодов и ((:shannon#энтропия энтропию))
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_{} $.
===Шифры==
===Кодировка ==
^ а ^ б ^ в ^ г ^ д ^ е,ё ^ ж ^ з ^ и ^ й ^ к ^ л ^ м ^ н ^ о ^ п ^ р ^ с ^ т ^ у ^ ф ^ х ^ ц ^ ч ^ ш ^ щ ^ ъ ^ ы ^ ь ^ э ^ ю ^ я ^
| 01|02 |03 | 04|05 |06 | 07| 08|09 |10 |11 | 12| 13| 14| 15| 16 |17| 18| 19|20 |21 |22 |23 | 24| 25| 26|27 | 28|29 | 30| 31|32|
^ пробел ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| | | | | | | | | | | | | | 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.
M:=648260107575268814265371780546654840030435733664832906157532874682052921804307894977;
E:=131071;
c:=360116524087175795499279586531945667942674557492700734949391833903672196274133690495;
----
12.
**С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 ^
| 01|02 |03 | 04|05 |06 | 07| 08|09 |10 |11 | 12| 13| 14| 15| 16 |17| 18| 19|20 |21 |22 |23 | 24| 25| 26|
^ space ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| | | | | | | | | | | | | 00 | | | | | | | | | | | | | |
M:=88831556288049781893094489733622009941345390278309270519438478117919601627:
E:=21059796197750960172668055248563150872379386315483177974373332925393127673:
c:=4077137491632769572879370857328973054213777712202424374222171607677933164:
===Шифровки "серьезные"==
1.
((:numtheory#факторизация Метод Ферма))
M:=38156877939390531717103399196833583092738956781697046758805633214857101281543564706150986821166369731473418905754107317271;
E:=7123903;
c:=31467125324198545314913130179632831994033781560098663054299098480847271139768419136815733559406184868426593267189807830213;
----
2.
((:crypto:attacks#метод_полларда Метод Полларда))
M:=146481808053566948606112326494160580676597757390203425433760346556289969224977192583652803722778590707655656624536558761037114144280380743982554672552469432942539798288533;
E:=7770779;
c:=50482193893295118672212227596255206609978317479891567490511905296629661164408165727901970750204892065138791242602754754520133030233374524172418377404891017560153125158450;
----
3.
"Грубой силой" (ключ дешифрования ((:crypto:attacks#ключ_дешифрования_неединствен неединствен)))
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.
Второй простой множитель модуля сгенерирован из первого с помощью ((:crypto:pprime:pockl алгоритма Поклинтона)).
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 $ векторов, составляющих ((:linear_space#сумма_и_пересечение_линейных_подпространств сумму этих линейных подпространств)). Доказать, что $ 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 $((:codes:vspom2 .))
Информационные байты $ X_1,\dots,X_8 $ кодируются с помощью служебных байтов $ Y_1,\dots, Y_{10} $ по правилу ((:codes:cyclic#кодирование систематического кодирования)):
$$ 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\} $.