О возможностях увеличения мощности линейных корректирующих кодов
Р.Р. Варшамов
КИБЕРНЕТИКА И ТЕОРИЯ РЕГУЛИРОВАНИЯ Р. Р. ВАРШАМОВ О ВОЗМОЖНОСТЯХ УВЕЛИЧЕНИЯ МОЩНОСТИ ЛИНЕЙНЫХ КОРРЕКТИРУЮЩИХ кодов (Представлено академиком Б. Н. Петровым 3 VII Hfi'I) Одной из основных задач алгебраической теории кодов является пробле ма разработки конструктивных методов построения помехоустойчивых систем кодирования, обладающих максимальной скоростью передачи ин формации (или, что то же самое, максимальной мощностью кодовых под множеств) при заданных ее основных параметрах и, t п <?, где пблоко вая длина кода, tчисло исправляемых ошибок, qоснование кода.В за метке приводятся некоторые результаты относительно возможностей по строения в метрике Хемминга помехоустойчивых систем сигналов, мощ ность кодовых подмножеств которых намного превосходит мощность всех аналогичных известных в литературе наилучших линейных кодов.Наша основная концепция заключается в следующем.Теорема 1, Как бы велико ни было число 0 и каков бы ни был метод построения линейных корректирующих кодов, исправляющих t симметри ческих ошибок, опираясь на него, всегда можно указать такие значения па раметров п и q, для которых можно строить новые классы кодов, мощность кодовых подмножеств которых более чем в 0 раз будет превосходить мощ ность соответствующих кодов, построенных первоначальным способом-, при этом сохраняется их прежняя корректирующая способность.Мы будем считать, что задан метод построения систем кодирования, ис правляющих фиксированное число t ошибок, если указан вполне определен ный способ, позволяющий для произвольных п и q строить такие системы.Рассмотрим на примерах кодов Хемминга и Боуза -Чоудхури -Хоквингема, какую физическую интерпретацию допускает теорема 1. 1. Коды Хемминга.Как известно ('), кодами Хемминга называ ют класс линейных кодов, исправляющих одиночные симметрические ошиб ки.Эти коды, хотя и являются оптимальными в классе линейных кодов, од нако относятся к разряду кодов, для которых разработан метод построения.А поэтому согласно утверждениям теоремы 1 должна существовать конст руктивная возможность, позволяющая увеличивать (даже неограниченно) их мощность.Условимся в дальнейшем через g(n, q) обозначать мощность наилучше го кода Хемминга длины п и основания q, а также &q(n) =ql}oetnl, где [ж]наименьшее целое, не превосходящее х, и {х}=х-[ж].Случай q=3 * .* В случае q~2 наш метод неэффективен.
•Jan 1, 1975•0 citations