uz
Feedback

Firibgarlarga uchmang! Telemetrio bunday kanallarni topadi va belgilaydi 👉 Belgini ko‘rmoqchi bo‘lsangiz, obuna bo‘ling

Математические байки

Математические байки

Kanalga Telegram’da o‘tish

Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/

Ko'proq ko'rsatish
4 358
Obunachilar
Ma'lumot yo'q24 soatlar
+97 kun
+3930 kun
Postlar arxiv
Возвращаясь к ним-сложению: если взять d=2, то становится понятно, что это близкая история. А именно: d=2 означает, что мы последовательно (в словарном порядке) перечисляем варианты первых (n-1) букв — и пытаемся их дополнить последней буквой — наименьшей из тех, которая ещё не встречалась раньше для слов, отличающихся лишь в одной из первых (n-1) букв.
12 Apr 2020, 10:41

Тот самый код Голея, который применялся для передачи изображений от Вояджеров — который за счёт сокращения скорости вдвое (12 бит передаётся 24-мя) позволяет исправить 3 ошибки в группе (и обнаружить, хоть и не исправить, наличие четырёх: у него кодовое расстояние 8) — https://en.wikipedia.org/wiki/Binary_Golay_code#NASA_deep_space_missions
12 Apr 2020, 10:17

photo content
12 Apr 2020, 10:14

Интересно, что такая "жадная" процедура позволяет породить как код Хэмминга — что заметил ещё Левенштейн — так и код Голея, что заметили Конвей со Слоаном:
12 Apr 2020, 10:14

Для алфавита из {0,1} лексикографические коды рассматривал задолго до того Левенштейн — см. http://mi.mathnet.ru/dan39976 — но связи с теорией игр у него из-за этого не было (а Конвей со Слоаном о его работе, очевидно, не знали).
12 Apr 2020, 10:11

photo content
12 Apr 2020, 10:04

Вот кусочек из работы Конвея и Слоана, "Lexicographic Codes: Error-Correcting Codes from Game Theory" — посвящённый как раз этим утверждениям:
12 Apr 2020, 10:04

То, что ab=1, видно, например, из 2* 001321 = 002132 — в левой части мы знаем всё, кроме "2*3".
12 Apr 2020, 09:59

Но соотношения мы получаем как раз какие надо: в поле из 4 элементов, кроме 0 и 1, для которых 1+1=0, есть ещё два элемента, a и b (те самые наши "2" и "3"), причём a^2=b, b^2=a, ab=1, a+1=b, b+1=a.
12 Apr 2020, 09:55

И вот мы получаем "2*2=3" в поле из 4 элементов {0,1,2,3} — только обычно, конечно, никто не обозначает его элементы 2 и 3, потому что 2 это вовсе не 1+1 (которое там равно нулю).
12 Apr 2020, 09:52

И если верить в теорему выше — то слово 002023 должно быть равно 2*001012, где множитель два — элемент поля из 4 элементов.
12 Apr 2020, 09:49

Например, при B=4 (то есть k=2) и n=6 наш код начнётся со слов 000000 000111 000222 000333 001012 001103 001230 001321 002023 002132 ...
12 Apr 2020, 09:48

Собственно, если взять вместо бесконечного алфавита — алфавит из B=2^{2^k} символов, — а слова ограничить конечной длиной n — то мы получим часть этого кода: слова, у которых лишь последние n символов ненулевые, и которые не выходят за алфавит A={0,1,...,B-1}. И это уже совсем ситуация кодов, с которой этот рассказ начинался.
12 Apr 2020, 09:44

И вот эта теорема совершенно удивительна: вроде бы, мы начинали с лексикографического порядка — а в результате на натуральных числах возникла структура поля, а найденные коды оказались образующими линейное пространство.
12 Apr 2020, 09:21

На самом деле, это поле будет объединением "возрастающей башни" полей из 2^{2^k} элементов (поле из p^m элементов это подполе p^r элементов, если r это степень m). Более того, сложение тут — это то самое ним-сложение (побитовое сложение двоичных записей), которым решается задача о выигрышных позициях в игре в ним.
12 Apr 2020, 09:02

Конечно же, сложение и умножение получаются нестандартными — а поле будет характеристики 2.
12 Apr 2020, 08:55

Но интересного больше. Теорема, которую рассказывал Конвей на лекции — Теорема. Можно так ввести на неотрицательных целых числах сложение и умножение (превратив их в поле), что построенный код будет линейным.
12 Apr 2020, 08:54

Уже на этих словах можно было увидеть какую-то регулярность — и начинать "копать" и разбираться, что же тут интересное.
12 Apr 2020, 08:45

Так вот, мы всё это делали не просто так!
12 Apr 2020, 08:44

И когда мы, проявив упорство, добавим всё бесконечное число слов вида 001*** — первым словом вида 002*** будет 002023. Потому что 00200* слишком близко к 000000, 00201* слишком близко к 001012, 002020 — опять к 000000, 002021 — к 001321 (и это легко пропустить), 002022 — к 000222, ну и 002023 — то, что нужно.
12 Apr 2020, 08:43