Две задачи по теории кодирования. Совершенные коды

Введение 1.
Удивительным свойством совершенного (n,q,t,k)-кода является то, что шары радиуса t, с центрами в точках кода 1) не пересекаются и 2) заполняют все пространство последовательностей длины n над q-ичным алфавитом. k – число информационных символов кода.
Для совершенных кодов неравенство (граница) Хемминга выполняется с точностью до равенства, поэтому говорят, что совершенные коды лежат на границе Хемминга. Это равенство является необходимым условием существования совершенного кода.
Из нетривиальных кодов (т. е. кодов с k>1) известны совершенные коды Хемминга (t = 1, q – степень простого числа, n – подходящие числа на границе Хемминга) и два совершенных кода Голея: (23,2,3,12) и ( 11,3,2 ,6).
Для понимания, о чем речь, убедитесь, что коды с данными параметрами лежат на границе Хемминга.
Задача 1.
Параметры (90,2,2,78) лежат на границе Хемминга (т. е. необходимые условия существования совершенного кода с такими параметрами выполняются). Докажите, что совершенного (90,2,2,78)-кода не существует. Это несложно.
Введение 2.
При кодировании с обратной связью предполагается возможность формирования каждого следующего символа n-последовательности в зависимости от результата приема предыдущих символов («есть ошибка - нет ошибки»). Код с одноранговой обратной связью (или одноранговый псевдокод) формирует последовательность символов (например, k символов), а затем, по результатам их приема – оставшиеся символы.
Задача 2
Постройте одноранговый совершенный (90,2,2,78)-код.
Непросто, но очень интересно.



Редактировалось 3 раз(а). Последний 24.07.2011 10:13.

Решения этих задач на форуме Математика здесь: обсуждение деталей постановки, варианты решений, немного истории,