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

Введение 1 (для тех, кто не знаком с вопросом). Совершенный код – это блочный (q, n, k, t)-код (где: n – длина кодового слова, q – позиционность алфавита, t – максимальная кратность исправляемых ошибок, k – число информационных элементов в слове), лежащий на границе Хемминга, т. е. параметры которого удовлетворяют равенству: $$ (1) \;\;\;\;\; \sum_{i=0}^t C_n^i(q-1)^i=q^{n-k}. $$ В двоичном случае это равенство принимает вид: $$ (2) \;\;\;\;\; \sum_{i=0}^t C_n^i=2^{n-k}. $$ Удивительным свойством совершенного (n,q,t,k)-кода является то, что $% q^k $% шаров радиуса t, с центрами в точках кода 1) не пересекаются и 2) заполняют все пространство последовательностей длины n над q-ичным алфавитом. Известны двоичные совершенные коды: Хемминга с параметрами: t=1, n-k=2, 3,..., $% n=2^{n-k}-1 $% и код Голея: $% t=3, n=23, k=12, $% Из недвоичных (q-ичных) известны совершенные коды Хемминга с параметрами: q – степень простого числа, $% t=1, n-k=2, 3,... , n=q^{n-k}-1 $% и троичный код Голея: q=3, t=2, n=11, k=6. Для параметров всех указанных совершенных кодов, как легко проверить, выполняется равенство (1) (и в частном случае (2)). Вместе с тем выполнение равенств (1), (2) при некоторых значениях q, n, k,t не гарантирует существование кода с такими параметрами. Так, для t=1, n-k=2 равенство (1) выполняется при всех q, однако для составных алфавитов (q не есть степень простого числа) не известно ни одного такого кода. Более того установлено несуществование такого кода при q=6.

Задача 1 (не сложная, но интересная). Легко проверить, что числа n=90, k=78, t=2 удовлетворяют равенству (2). Докажите, что совершенного двоичного кода с такими параметрами не существует. (Пожалуй, с этого начинают все специалисты по теории кодирования).

Введение 2. При кодировании с обратной связью предполагается возможность формирования каждого следующего символа n-последовательности в зависимости от результата приема предыдущих символов («есть ошибка - нет ошибки»). Код с одноранговой обратной связью (или одноранговый псевдокод) формирует последовательность символов (например, k символов), а затем, по результатам их приема приемником (передатчик знает этот результат) – оставшиеся символы.

Задача 2 Постройте одноранговый совершенный псевдокод с параметрами n=90, k=78, t=2. Непросто, но очень интересно.

задан 7 Окт '13 2:10

изменен 7 Окт '13 2:20

С задачей 1 я ознакомился, и теперь знаю, как она решается. Трюк с числом 88, не делящимся на 3, выглядит очень красиво! Я, кстати, не знал даже о том, что суммы трёх биномиальных коэффициентов для 90 дают степень двойки. Постановку второй задачи хотелось бы лучше понять. Какими данными могут обмениваться передатчик и приёмник?

(7 Окт '13 13:37) falcao

@Falcao, действительно, доказательство несуществования основывается на свойствах делимости целых чисел. Попросил бы Вас через несколько дней (когда сочтете нужным) его выложить, чтобы обсудить с заинтересовавшимися участниками. По вопросу об обмене данными: передатчику известна вся картина относительно приема приемником ранее переданных передатчиком символов. При этом при построении однорангового псевдокода (с начальным подблоком длины k) полагают, что на момент формирования передатчиком конечного подблока длины n-k передатчику известна конфигурация ошибок, наложенная на начальный подблок.

(7 Окт '13 17:11) Urt

@Urt: выложить решение первой задачи я могу хоть сейчас, но я должен предупредить, что не сам его придумал "с нуля", а просто узнал основную идею и осмыслил её. В принципе, решение красивое, и я согласен с тем, что кому-то из участников форума может быть интересно это решение прочитать. По поводу второй задачи: сейчас вроде бы условие понятно, но я хотел бы уточнить одну вещь. Верно ли я понимаю, что код здесь строится по такому принципу, что сначала передаются k информационных символов, и уже только в конце передаются вспомогательные, с учётом специфики ошибок при передаче k символов?

(7 Окт '13 17:27) falcao

@Falcao, да, это так. Вместе с тем конструкция однорангового кода может быть несколько более общей: сначала передается блок v символов (0 < v < n) и затем с учетом конфигурации наложенных на них ошибок - оставшиеся n-v символов

(7 Окт '13 17:49) Urt

@Urt: вот что ещё хочется уточнить. Допустим, мы передали k символов, и при этом зафиксировано две ошибки. Тогда это можно считать "везением", так как "лимит" исчерпан, больше ошибок не будет, и тогда просто посылаем код ошибки напрямую. А если ошибок не было, то надо быть готовым к тому, что они могут быть. Правда, в первом случае тоже не всё так просто, поскольку принимающая сторона не знает того, что знает передающая, то есть она должна сама сориентироваться. Это я лишний раз хочу проверить, правильно ли мной понят "сюжет".

(7 Окт '13 17:59) falcao

@Falcao, точно - "сюжет" именно такой. (Временно прервусь - предстоит перелет, уже на старте). Спасибо за ответ. К сожалению, детально ознакомиться смогу только завтра.

(7 Окт '13 19:57) Urt
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
1

Итак, попробую изложить свой пересказ решения первой задачи. Насколько мне известно, излагаемая идея принадлежит автору по фамилии Tompkins; изначальное решение конца 50-х годов, принадлежащее Golay и Zaremba, было чуть сложнее.

Задачу можно переформулировать так. Имеется множество вершин $%n$%-мерного куба ($%n=90$%). Расстоянием Хэмминга между двумя вершинами называется количество несовпадающих координат у соответствующих векторов. Естественным образом определяются сферы и шары.

Легко видеть, что объём шара радиусом 2 с центром в любой вершине равен $%1+90+C_{90}^2=4096=2^{12}$% (само по себе это числовое равенство представляет интерес). Здесь учтена сама вершина, $%90$% вершин с отличающейся одной координатой (от координат центра), и $%C_{90}^2$% вершин с отличающимися двумя координатами.

В связи с этим возникает вопрос, можно ли все вершины $%90$%-мерного куба покрыть общим количеством шаров радиуса 2 в количестве $%2^{78}$%? Если да, то шары попарно не пересекаются. Ответ на этот вопрос отрицателен, что и означает невозможность построения соответствующего кода Хэмминга с исправлением двух ошибок.

Чтобы читателю было яснее, рассмотрю пример $%n=5$%. Здесь шар радиусом 2 состоит из $%1+5+C_5^2=16=2^4$% точек, и двумя такими шарами всё легко покрывается: их центрами надо назначить вершину с нулевыми координатами и вершину с единичными координатами. Это простой случай, для которого решение оказывается положительным.

Итак, предположим, что искомое покрытие $%90$%-мерного куба имеется. Если к координатам всех вершин прибавить (по модулю 2) фиксированный вектор, то расстояния не изменятся. Поэтому один из центров шаров можно поместить в начало координат, то есть сделать нулевым. В шар попадут в точности все вершины, у которых среди координат имеется не более двух единиц.

Из этого следует, что центры покрывающих шаров не могут располагаться в вершинах, у которых единичных координат меньше пяти: это сразу бы дало пересечение.

Рассмотрим теперь векторы (вершины), у которых две последние координаты равны 1, и ещё одна из координат равна 1, а остальные -- нули. Пусть $%v_i$% ($%1\le i\le88$%) -- такие векторы с равной 1 координатой с номером $%i$%. Каждая из этих вершин лежит в каком-то шаре покрытия, и центр такого шара непременно должен иметь ровно пять единичных координат. Для вершины $%v_i$% рассмотрим центр $%w_i$% такого шара; у него равны 1 две последние координаты, координата с номером $%i$%, и какие-то ещё две координаты с номерами от $%1$% до $%88$%.

Проверим, что при $%1\le i < j\le88$% не может так оказаться, что у центров шаров покрытия $%w_i$% и $%w_j$% имеется общая единичная координата среди первых $%88$%. Допустим, это $%k$%-я координата; тогда по определению шары будут иметь общую вершину $%v_k$%, что невозможно.

Таким образом, $%88$% первых координат должны поровну распределиться тройками между шарами покрытия. Поскольку $%88$% не кратно трём, это невозможно. Эффект основан на том, что шару с центром $%w_i$% соответствуют какие-то три из $%88$% первых координат, равных 1 для этого вектора. Разным шарам одинаковые координаты, как было сказано выше, соответствовать не могут. Но любая из $%88$% координат чему-то обязана соответствовать: по условию, $%v_i$% лежит в шаре с центром $%w_i$%, где $%i$% -- произвольное число от $%1$% до $%88$%. Это даёт окончательное противоречие.

Добавление. Сейчас пришли в голову идеи по поводу решения второй задачи. Здесь я решал сам, никуда не заглядывая. Рассуждение пока не доведено до конца, но я запишу то, что получилось, а потом попробую продумать завершающий этап.

Пусть мы отправили 78 информационных бит, и знаем при этом, какое число ошибок (не более двух) было допущено. Если ошибок нет, то далее нужно отправить какой-то 12-битный код -- например, из одних единиц, допуская, что при этом может быть допущено не более двух ошибок при передаче. Это соответствует шару радиуса 2 объёмом $%1+12+C_{12}^2=79$%: всякое принятое сообщение из этой области должно соответствовать тому, что первые 78 бит сообщения верны.

Далее, пусть ошибка была всего одна. Тогда 12-битный дополнительный код должен содержать указание на номер бита, в котором допущена ошибка. На эти последние 12 бит полагается не более одной ошибки, что соответствует шару радиуса 1, объём которого равен 13. Нам нужно 78 таких шаров, каждый из которых по договору указывает на один из 78 номеров. Эти шары не должны пересекаться между собой, а также не должны иметь пересечений с шаром радиуса 2. Общий объём таких шаров должен составить $%78\cdot13=1014$%.

Остаётся случай, когда ошибок при передаче было две. Это значит, что далее можно послать 12-битное сообщение, которое дойдёт без искажений и укажет на одну из $%C_{78}^2=3003$% пар бит, в которых имеется ошибка при передаче. Этим случаям соответствуют шары радиуса 0, то есть точки.

Общий объём всех упомянутых шаров составляет в точности $%79+1014+3003=4096=2^{12}$%. Тем самым, задача сводится к тому, чтобы указать в 12-мерном двоичном (вершинном) кубе один шар радиуса 2 (его мы уже задали) и 78 шаров радиуса 1, чтобы это всё попарно не пересекалось. На оставшихся $%3003$% местах будут шары нулевого радиуса. "Шпаргалка" для разгадывания будет включать в себя координаты шаров радиуса 1, так как они всё определяют (шар радиуса 2 считается заданным).

Сначала мне показалось, что искомое расположение указать просто, но по ходу дела возникли трудности с реализацией. Поэтому я пока на этом прерву своё "повествование". Совпадение суммы чисел со степенью двойки наводит на мысль, что план реализуем, хотя "упаковка" может оказаться достаточно "жёсткой".

Добавление 2. Если я ничего не упустил, то рассмотренный выше план реализуется достаточно просто. Нам надо разместить 78 шаров радиуса 1 и шар радиуса 2 в пределах 12-мерного вершинного куба, чтобы шары попарно не пересекались. Шар радиуса 2 размещаем в точке с единичными координатами. Далее поступаем так: используем стандартные коды Хэмминга с исправлением одной ошибки. Коды будут 12-битные, и при этом 8 бит будут информационными, а 4 оставшиеся -- вспомогательными. Строение кода такое: $%a_1,\ldots,a_8$% задаются произвольно, $%a_9=a_1+a_3+a_5+a_7$%, $%a_{10}=a_2+a_3+a_6+a_7$%, $%a_{11}=a_4+a_5+a_6+a_7$%, $%a_{12}=a_8$%. Таких кодовых слов всего $%2^8=256$%, но нам подходят не все, так как нельзя задевать шар радиуса 2. Чтобы не было пересечений с этим шаром, надо выбирать кодовые слова (центры будущих шаров радиуса 1) так, чтобы среди 12 бит было по крайней мере 4 нуля. Положим $%a_{8}=a_{12}=0$%, после чего в нашем распоряжении остаётся $%2^7=128$% кодовых слов. Удалим такие, у которых среди чисел $%a_1,\ldots,a_7$% имеется всего один ноль или ни одного. Таких случаев всего 8, и в нашем распоряжении остаётся $%120$%. А нам достаточно было указать $%78$%, то есть "норму" мы перевыполнили. Это завершает рассуждение (если я нигде не ошибся).

ссылка

отвечен 7 Окт '13 19:52

изменен 8 Окт '13 20:42

@Falcao, все Ваши статьи я читаю с удовольствием. Представленное здесь решение также меня весьма порадовало – красиво проведено и изложено !!! В первой задаче у меня подход был другой, постараюсь описать. Во второй аналогичен Вашему (с точностью до обозначений). После постановки и решения увидел, что результаты уже известны.
Возможно, для понимания имеет смысл кратко описать идею кодирования и декодирования. Ответ задержал – неувязки (по недоработке банка с автооплатой жизнеобеспечивающих ресурсов) – были отключены эл-во, вода, Интернет..., но все прекрасно...

(9 Окт '13 19:50) Urt

Мне, кстати, вторая задача показалась проще первой. Возможно, по той причине, что я за это время лучше вдумался в проблематику. Но в первой задаче так или иначе требуется догадка олимпиадного характера, а во второй всё как-то само постепенно получается. На последнем этапе нет "жёсткости" в выборе, так как там почти всё состоит из точек, поэтому запаса для шаров там хватает вполне. Что касается декодирования, то во второй задаче у нас есть "шпаргалка" из центров шаров радиуса 1. По последним 12 битам определяем, в какой шар мы попали. (продолжение ниже)

(9 Окт '13 19:59) falcao

Все одноточечные множества упорядочиваем лексикографически, и по номеру в списке определяем код ошибки -- какие два бита из 78 требуется исправить. Соответственно, считается, что все сочетания из 78 по 2 тоже упорядочены каким-то естественным образом. С шарами радиуса 1 поступаем аналогично. Интересно было бы узнать другие способы решения первой задачи.

(9 Окт '13 20:02) falcao
10|600 символов нужно символов осталось
1

Привожу свои решения задач. Решение второй задачи, по сути, совпадает с решением, приведенным @Falcao - несколько отличаются использованные упаковки пространства разнотипными шарами.

Сначала небольшое отступление.

Решения используют еще одно уникальное свойство совершенных кодов (далее СК), для формулировки которого напомню понятия спектра расстояний и спектра весов.

Пусть $% E_q^n $% – пространство всех последовательностей длины n над q-ичным алфавитом. Под спектром расстояний кода $% A \subseteq E_q^n $% относительно слова a понимается последовательность (целых неотрицательных) чисел $% < N_0(a)=1, N_1(a),... N_n(a)>, $% где $% N_i(a) $% – число кодовых слов, находящихся от a на расстоянии i. Очевидно, что для любого линейного кода спектр расстояний не зависит от слова a и совпадает со спектром весов кода: $% < N_0=1, N_1,... N_n>, $% где $% N_i $% – число кодовых слов веса i.

К уникальным свойствам СК относится то, что это утверждение также справедливо для любого СК (содержащего в качестве кодового слова 0=(0,0,...,0), как линейного, так и нелинейного. Более того, спектр весов СК легко определить на основе рассуждений, которые я приведу лишь для случая t=2 – их легко обобщить для любого t. При этом вместо выражения «последовательность x принадлежит шару радиуса t с центром в слове a» будем для удобства говорить «последовательность x может быть получена из слова a»). Учитывая, что каждая последовательность из $% E_2^{90} $% может быть получена только из одного кодового слова, легко заключить: 1) $% N_0=1 $%; 2) $% N_1= N_2= N_3= N_4=0 $%; 3) поскольку все последовательности веса 3 могут быть получены только из кодовых слов веса 5, причем из каждого слова веса 5 может быть получено $% C_5^2 $% таких последовательностей, то $% C_n^3= C_5^2N_5 $%, откуда $% N_5= C_n^3/C_5^2 $%; 4) поскольку все последовательности веса 4 могут быть получены только из кодовых слов весов 5 или 6, причем из каждого слова веса 5 может быть получено 5 таких последовательностей, а из каждого слова веса 6 может быть получено $% C_6^2 $% таких последовательностей, то $% C_n^4= 5N_5+ C_6^2N_6, $% откуда $% N_6= (C_n^4-5N_5)/C_6^2. $%.

Продолжая далее, придем к рекуррентной формуле: $$ N_i= (C_n^{i-2}-(i-1)N_(i-1))/C_i^2, i=5,6,...,n. $$ Решение задачи 1 сводится к вычислению по этой формуле значения $% N_7 $% , которое оказывается нецелым числом.

Примечание: Попытки доказать таким образом несуществование q-ичных СК над составными алфавитами с t=1, n=q+1, k=q-1 (лежат на границе Хемминга) и других кодов с t=1 на границе Хемминга не дают результата, т. к. вычисленные по рекуррентным формулам значения $% N_i $% целочисленные.

Решение задачи 2 сводится к пониманию теоретико-множественной сущности задачи (замечательно описана @Falcao), состоящей в упаковке пространства $% E_2^{12} $% системой шаров: $% C_{78}^0=1-м $% шаром радиуса 2, $% C_{78}^1=78-ю $% шарами радиуса 1 и $% C_{78}^2 = 3003-мя $% шарами радиуса 0 (это просто точки, не попадающие в шары радиусов 2 и 1). Построение такого кода легко понять из представления числа всевозможных ошибок в виде: $% 2^{12}=С_{90}^0+ С_{90}^1+ С_{90}^2= С_{78}^0(С_{12}^0+ С_{12}^1+ С_{12}^2)+ С_{78}^1(С_{12}^0+ С_{12}^1)+ С_{78}^2С_{12}^0. $% При использовании такой упаковки кодирование осуществляется следующим образом: если в блоке длины 78 произошло i ошибок, то передатчик посылает слово длины 12, являющееся центром шара (соответствующего конфигурации ошибки) радиуса 2-i, а декодер приемника сначала восстанавливает переданный передатчиком подблок длины 12, а затем по результату восстановления определяет конфигурацию ошибки в первом подблоке длины 78 и соответственно переданный первый подблок длины 78.
Упаковку $% E_2^{12} $% указанными шарами я осуществлял следующим образом. Точка 0 бралась за центр шара радиуса 2, Затем модифицировал (2,15,11,1)-код Хемминга: укорачивал его на 4 до (2,11,7,1)-кода, затем в результате проверки на четность получал код с параметрами: n=12. k=7 и кодовым расстоянием d=4. Любые 78 кодовых слов (кроме 0) этого кода имеют вес Хемминга $% d \ge 4 $% и, поскольку шары радиуса 1 с центрами в кодовых словах не пересекаются с шаром радиуса 2 с центром в 0, то эти слова могут быть взяты в качестве центров единичных шаров. Оставшиеся, еще не выбранные последовательности из $% E_2^{12}, $% принимаются в качестве центров шаров нулевого радиуса, т. е. в качестве точек, представляющих двойные ошибки в первых 78 символах.

Примечания.

1) Берлекэмпом в начале 60-х годов установлено, что для любых q, n, k, t, удовлетворяющих границе Хемминга, существует (q, n, k, t )-псевдокод (использовались другие термины). Дальнейшие усилия в этом вопросе направлялись на построение кодов с определенной структурой (например, линейных), а также с заданной «ранговостью» (напрмер, одноранговых).

2) Изучаются коды, соответствующие упаковкам систем шаров с разными радиусами. В этом направлении получено множество различных кодов, в том числе совершенных. К кодам такого типа можно придти при решении задач кодирования для каналов с различными параметрами достоверности.

ссылка

отвечен 10 Окт '13 3:10

@Urt: Спасибо за интересную информацию! Метод доказательства, основанный на подсчёте мощностей сфер (спектров) весьма интересен. Он выглядит достаточно универсальным -- в этом его преимущество. То есть он не требует каких-то догадок, взятых неизвестно откуда. У меня возникала мысль применить такую идею, но я остановился на том, что $%C_{90}^3$% делится на $%C_{5}^3$%, а дальше в этом направлении идти не стал.

(10 Окт '13 9:32) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×30

задан
7 Окт '13 2:10

показан
1481 раз

обновлен
10 Окт '13 9:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru