Линейный код: различия между версиями

21 635 байт убрано ,  11 лет назад
откат неформатного текста, вероятного самопиара.
(откат неформатного текста, вероятного самопиара.)
В области математики и теории информации '''линейный код''' — это важный тип [[Обнаружение и исправление ошибок#Блоковые коды|блокового кода]], использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.
В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации. Совершенно справедливы требования [Питерсон У., Уэлсон Э. Коды, исправляющие ошибки. М.: Мир, 1976, стр.25] к кодам, исправляющим ошибки и аппаратуре, выполняющей эти исправления: «Для того чтобы коды были высокоэффективными, они должны быть длинными, потому что в этом случае влияние шума усредняется по большему числу символов. Такой код может иметь значение гугола возможных кодовых слов и во много раз большее число возможных слов на выходе… тремя аспектами проблемы декодирования являются: 1) построение кодов, способных в должной мере исправлять ошибки (для этого обычно требуется, чтобы коды были длинными); 2) разработка практически осуществимого метода кодирования; 3) отыскание метода принятия решения на приемнике, т.е. метода исправления ошибок». Здесь необходимо добавить четвертое новое требование – возможность выполнения машинной арифметики для этих кодов в режиме реального времени. Всем этим требованиям также удовлетворяют многофазные и интегральные коды, которые обладают возможностью исправлении любого количества ошибок и пачек ошибок в режиме реального времени и также являются цикличискими кодами. Интегральный код представляет собой любую половину многофазного кода, и поэтому все его элементы присущи ему. Интегральный код лежит в основе финитного уточнения формализации арифметики Д. Гильберта [Гильберт Д., Бернайс П. ОСНОВАНИЯ МАТЕМАТИКИ. Логические исчисления и формализации арифметики (Серия: «Математическая логика и основания математики»). М.: Наука, 1979.], где операция порождения цифры или ее фигуры сопровождается добавлением цифры 1; а после каждой цифры 1, не являющейся концом данной фигуры и состоящей из одних единиц, идет следующая за ней единица. Эти коды могут иметь любую длину, а исправление ошибок в этих кодах производится без математических вычислений [см., например, А. с. 987681 (СССР). Регистр // Открытия. Изобретения. 1983. № 1. и Кочергин В.И. Теория многомерный цифровых множеств в приложениях к электроприводам и системам электропита-ния. -Томск: Изд-во Том. ун-та, 2002. - 444 с.] и основывается на существовании непрерывных множеств логических единиц и нулей в их структуре. По этой причине представленное выше определение эффективности линейных совершенных кодов является не-достаточным и фактически устаревшим. Теория многомерных цифро-векторных множеств [Кочергин В.И. Теория многомерных цифро-векторных мно-жеств. Томск: Изд-во Том. ун-та, 2006] позволила внести ясность в ряд существовавших много лет оши-бочных мнений математической формальной теории кодирования информации и машинной арифметики. Это, прежде всего, необоснованное деление кодов на арифметические коды и неарифметические. Практически все современное оборудование основано на использовании «арифметической» двоичной системы счисления, и, следовательно, двоичные коды являются наиболее важными. Тем не менее важны и недвоичные коды. Все коды позиционных систем счисления, и не только позиционных, где в их основе лежит натуральный ряд чисел, являются арифметическими. Ярким примером таких кодов являются многофазные коды, составляющие основу многочисленных электротех-нических устройств. Появление многофазных напряжений связано с именем российского электротехника Михаила Осиповича Доливо-Добровольского, который в 1889 создал трехфазный асинхронный двигатель и осуществил первую электропередачу трехфазного тока. В 70-х годах прошлого века автор разработал серию цифровых устройств, которые нашли отражения в десятках А.С. СССР систем электропитания и электроприводов в многофазных кодах, а также машинную арифметику для этих кодов. Основой геометрических аналогий устройств цифровой техники здесь служить идея упаковки пространства, которая была предложена в «новой геометрии» основоположником современной структурной кристаллографии и петрографии академиком Е.С.Федоровым, и наше предложение нумерации этого цифрового пространства. Особенность этой геометрии – в физическом существовании системы n-мерных измерений, что имеет первостепенное значение в рассматриваемых областях цифровой техники.
 
В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации. Совершенно справедливы требования [Питерсон У., Уэлсон Э. Коды, исправляющие ошибки. М.: Мир, 1976, стр.25] к кодам, исправляющим ошибки и аппаратуре, выполняющей эти исправления: «Для того чтобы коды были высокоэффективными, они должны быть длинными, потому что в этом случае влияние шума усредняется по большему числу символов. Такой код может иметь значение гугола возможных кодовых слов и во много раз большее число возможных слов на выходе… тремя аспектами проблемы декодирования являются: 1) построение кодов, способных в должной мере исправлять ошибки (для этого обычно требуется, чтобы коды были длинными); 2) разработка практически осуществимого метода кодирования; 3) отыскание метода принятия решения на приемнике, т.е. метода исправления ошибок». Здесь необходимо добавить четвертое новое требование – возможность выполнения машинной арифметики для этих кодов в режиме реального времени. Всем этим требованиям также удовлетворяют многофазные и интегральные коды, которые обладают возможностью исправлении любого количества ошибок и пачек ошибок в режиме реального времени и также являются цикличискими кодами. Интегральный код представляет собой любую половину многофазного кода, и поэтому все его элементы присущи ему. Интегральный код лежит в основе финитного уточнения формализации арифметики Д. Гильберта [Гильберт Д., Бернайс П. ОСНОВАНИЯ МАТЕМАТИКИ. Логические исчисления и формализации арифметики (Серия: «Математическая логика и основания математики»). М.: Наука, 1979.], где операция порождения цифры или ее фигуры сопровождается добавлением цифры 1; а после каждой цифры 1, не являющейся концом данной фигуры и состоящей из одних единиц, идет следующая за ней единица. Эти коды могут иметь любую длину, а исправление ошибок в этих кодах производится без математических вычислений [см., например, А. с. 987681 (СССР). Регистр // Открытия. Изобретения. 1983. № 1. и Кочергин В.И. Теория многомерный цифровых множеств в приложениях к электроприводам и системам электропита-ния. -Томск: Изд-во Том. ун-та, 2002. - 444 с.] и основывается на существовании непрерывных множеств логических единиц и нулей в их структуре. По этой причине представленное выше определение эффективности линейных совершенных кодов является недостаточным и фактически устаревшим. Теория многомерных цифро-векторных множеств [Кочергин В.И. Теория многомерных цифро-векторных множеств. Томск: Изд-во Том. ун-та, 2006] позволила внести ясность в ряд существовавших много лет ошибочных мнений математической формальной теории кодирования информации и машинной арифметики. Это, прежде всего, необоснованное деление кодов на арифметические коды и неарифметические. Практически все современное оборудование основано на использовании «арифметической» двоичной системы счисления, и, следовательно, двоичные коды являются наиболее важными. Тем не менее важны и недвоичные коды. Все коды позиционных систем счисления, и не только позиционных, где в их основе лежит натуральный ряд чисел, являются арифметическими. Ярким примером таких кодов являются многофазные коды, составляющие основу многочисленных электротехнических устройств. Появление многофазных напряжений связано с именем российского электротехника Михаила Осиповича Доливо-Добровольского, который в 1889 создал трехфазный асинхронный двигатель и осуществил первую электропередачу трехфазного тока. В 70-х годах прошлого века автор разработал серию цифровых устройств, которые нашли отражения в десятках А.С. СССР систем электропитания и электроприводов в многофазных кодах, а также машинную арифметику для этих кодов. Основой геометрических аналогий устройств цифровой техники здесь служить идея упаковки пространства, которая была предложена в «новой геометрии» основоположником современной структурной кристаллографии и петрографии академиком Е.С.Федоровым, и наше предложение нумерации этого цифрового пространства. Особенность этой геометрии – в физическом существовании системы n-мерных измерений, что имеет первостепенное значение в рассматриваемых областях цифровой техники.
 
 
== Основы ==
 
=== Коды Хемминга ===
ИсторическиИстроически "коды Хемминга" должны называться кодами Р.Фишера, которыйи был представлен в 1942г (Fisher R.A. The theory of confouding in factor to thr theory).
[[Код Хемминга|Коды Хемминга]] — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что ''синдром''
 
: <math>\sum_{i=0}^t {n\choose i} \le 2^{n-k}</math>.
 
Коды, удовлетворяющие этой границе с равенством, называются ''совершенными''. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.
Коды, удовлетворяющие этой границе с равенством, называются ''совершенными''. К совершенным кодам относятся, например, коды Хемминга.{perfect codes - совершенные коды - 1. По Хеммингу это коды с исправлением ошибок, в которых шары Хемминга с центром в кодовых словах заполняют все пространство Хемминга, не пересекаясь. Все эти шары имеют радиус e (т. е. код способен исправлять e ошибок), а их центры (кодовые слова) отделены один от другого расстоянием (2e + 1); при этом шары не соприкасаются между собой (т. е. не имеют общих слов), их поверхности находятся на минимальном расстоянии друг от друга, и этот промежуток не содержит других точек. 2. По теории многомерных цифро-векторных множеств совершенные коды это систематические коды со 100% исправлением, например всех одиночных ошибок, которые содержат информационную и контрольную части кода, а во всех ячейках многомерного цифрового пространства этого кода располагаются штатные цифры и соответствующие им цифры с одной ошибкой в информационной или контрольной его частях. Причем в каждой из ячеек располагается только одна цифра.}
Существует ошибочное мнение о малом числ совершенных и квазисовершенных кодов, исправляющих ошибки с минимальными затратами оборудования. Например, в классической работе [У.Питерсон, Э.Уэлдон Коды, исправляющие ошибки "МИР", 1976 на стр.139 говорится, что "имеются некоторые результаты показывающие, что соверщшенных кодов мало..."]и далее в книге А.М. Яглом и И.М. Яглом Вероятность и информация утверждается, что это "доказано финскмии учеными а. Тиетявяйненом и А. Перко и, независимо от них, В.А. Зиновьевым и В.К. Леоньтьевым в СССР..."
В работах[Кочергин В.И. Теория многомерных цифро-векторных множеств. Томск: Изд-во Том. ун-та, 2006; Кочергин В.И. Теория многомерных цифро-векторных множеств в технических системах управления: Дис. д-ра техн. наук. Томск: ТПУ, 2003.] показано, что число совершенных и квазисовершенных кодов двоичной системы счисления неограниченно велико. Также доказана возможность построения совершенных многофазных кодов. При этом использование двоичных и многофазных совершенных и квазисовершенных кодов стало практически реализуемо при минимальных затратах оборудования в системах передачи, хранения информации и выполнении арифметических операций в режиме реального времени с предельно возможным управляемым быстродействием. Существующая до настоящего времени теория кодирования основана на использовании достаточно сложного аппарата современных абстрактных разделов математики и в первую очередь высшей алгебры. Изложить этот абстрактный материал так, чтобы он был доступен инженеру, практически невозможно. Да и аппаратура, реализующая исправление ошибок на основании представления пространства Хеммингаи требует обработки большого числа поверочных матриц, не позволяет даже только для передачи и приема информации работать в режиме реального времени. При этом вопрос о возможности выполнения машинной арифметики в этих кодах, поскольку они считались неарифметическими, даже не рассматривался.
Доказательство большого числа совершенных кодов опирается на симметрию многомерного пространства Е.С. Федорова. В недалеком прошлом симметрию называли «гармонией мира», а соображения симметрии и инва-риантности давно играют в физике значительную роль. Как отмечал лауреат Нобелевской премии Е.Вигнер, «интуитивные представления о симметрии играли важную роль в мышлении великих физиков прошлого, хотя явное использование симметрии в старой физике ограничивалось в основном кристаллографией», а вывод Е.С. Федоровым 230 кристаллографических пространственных групп «по праву считается шедевром анализа».
Теория многомерных цифро-векторных множеств придала идее упаковки пространства Е.С. Федорова цифро-векторное представление и расширила понятие симметрии цифрового пространства.
 
 
=== Энергетический выигрыш ===