Сжатие и кодирование: RLE, Хаффман, LZ77, LZW, код Хэмминга (7,4) — авторское изложение

ru · official · sha256:8c0441d0d1c4885948e2d0f8b1868820f7d340b94a5df703e6ca9b5ea3ec93e5RU

§1. Код, префиксность, энтропия и различение сжатия от кодирования Код — отображение символов либо слов входного алфавита в слова выходного. Код однозначно декодируем, когда всякая последовательность кодовых слов разбирается единственным образом. Префиксный код — тот, у которого ни одно кодовое слово не является префиксом другого; всякий префиксный код однозначно декодируем, а обратное неверно. Префиксность есть достаточное, а не необходимое условие. Это различие обязано называться: изложения, объявляющие префиксность необходимой, ошибаются. СЖАТИЕ и ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ решают противоположные задачи. Первое убирает избыточность, второе её добавляет ради обнаружения и исправления ошибок. Смешивать их нельзя: код Хэмминга §7 не сжимает, а удлиняет, и это его назначение. Сжатие без потерь восстанавливает вход в точности. Ни один такой метод не сжимает всякий вход: отображение из множества слов длины n в множество более коротких слов не может быть инъективным. Отсюда следует, что всякое утверждение о степени сжатия относится к КЛАССУ входов, а не ко всем входам, и класс обязан называться. Энтропия источника по Шеннону есть нижняя граница средней длины кодового слова при посимвольном кодировании независимых символов. Код Хаффмана достигает этой границы с точностью до единицы на символ — утверждение источника, доказательство остаётся в нём. Расстояние Хэмминга между двумя словами равной длины — число позиций, в которых они различаются. Код исправляет одну ошибку, когда минимальное расстояние между его словами не меньше трёх: тогда искажённое одной ошибкой слово ближе к исходному, чем к любому другому кодовому. Скользящее окно — участок уже обработанного входа, доступный как источник совпадений. Словарь — растущий набор слов, каждому из которых приписан номер. Оба суть способы сослаться на уже встреченное, и различие между LZ77 и LZW состоит именно в этом способе.

Referencing norms: AnswersHere, f-05321aaa6eaafa4fc922161f, f-14b9f1490117bae7ba813900, f-1d19f591ddd52348471aa87e, f-1f1194d167bf3186855ad4a5, f-331d103ec360ee5d7ea6edad, f-3b108cafa913f78b87a342a7, f-3bed76e684776d2e27f0ac44, f-451db3a998b0c61c83121d52, f-4a832247a1052c2d45cbd485, f-52b09e77bc57c5bce981b547, f-57aa14b7df9bb45aa6e575d5, f-5d7a1307c97c6cc4cd3bf50e, f-5fb003cc9905ae32508668f9, f-69f86138460b704821842bd8, f-6b34d2ded7cc438f9201f33a, f-729a8a3fe7b088a05284f316, f-80550dc0a767a962cda95dd4, f-879c7fad24e7983a2d108265, f-9a46467af549c0c9a85cba98, f-a17d74deab4d9a6d6da87eb8, f-aeacecd542f4f4f5df6ac340, f-b51b778e01f8d0b251bd36ab, f-bfa00a4bc975d6b20eae70b8, f-d3d2099208c1ae4d7399a719, f-d6acc58acd1e3eb4c6bae85a, f-e52c557942b060aea732e336, f-e73016eece0c8ffe8296c1b8, f-f38f6f34cc0f363cd9626ef9, f-f3a5fe571f830776a730bed0, f-f7b79f67b08af925651db44a, f-ff777e3c505d8595382051a7

ru · official · sha256:17ccedc1d3de7b2ff4720930523247adeae3313e350aaa5c8fc2948e92dda7b4RU

§2. Кодирование длин серий Задача: по последовательности символов получить кодирование, заменяющее серии одинаковых подряд идущих символов парой «длина, символ». Вариант — посимвольный проход со счётчиком текущей серии. Проход идёт слева направо. Пока очередной символ равен текущему, счётчик увеличивается. При смене символа либо конце входа выдаётся пара «счётчик, символ», и счётчик начинается заново. Крайние случаи обязаны называться, и их два. Первый: вход без повторов кодируется ДЛИННЕЕ исходного — пара на каждый символ. Второй: длина серии может превысить предел кодового поля, и тогда серия обязана разбиваться на несколько пар; изложение, не называющее предела длины, неполно. Инвариант: выданная часть кода при декодировании даёт в точности пройденную часть входа. Метод выгоден на данных с длинными сериями — растровых изображениях с большими одноцветными областями, факсимильных данных. На тексте естественного языка он вреден, и это свойство КЛАССА входов, а не дефект метода. Оценка: один проход, время линейно по длине входа, дополнительная память постоянна.

Referencing norms: f-00a058ecb9d4e82dcf59b385, f-03d9286172eda5ab7a297895, f-0630266a18ed6ded82d56a5e, f-06f1bb3b4f5c8b20d8aae498, f-0deec547a6fc9e02c0b44850, f-14297361104ccb8801c9198a, f-23ccb49d6af9faadc1e11fb0, f-2509d6468cc4b28020a51fd0, f-251928e2c6c2df3fd2bbc68d, f-296a1d666dd188a1a49457f4, f-2ac9570aaeed99a8c47e60e7, f-2ce4950159f467a06f4dba41, f-2d6d669796b6432c1570bbb9, f-2fc62d0f2eb31ae54d93ab0a, f-319e98c87458df8d41ca8312, f-32088e3bdf58d5b142686474, f-321acd5360d113eb8952d361, f-359c5d557e539f358940aff5, f-3b766cb99827670662e7de90, f-3d481caace22b062ec84c3f1, f-3dde286f727cc2984a2f581a, f-401ca7295b3d4195807e0bef, f-417e712ddda4b06baea2ff45, f-42c320ee79b73067aea149a9, f-43a9942008fcc76125194e41, f-4761d9ab785fa77a5a8e6577, f-4cac8a58cca14f2681ff90ed, f-4ebc5d2dc87cec06e3496a1d, f-4ef703c52a59f6db15572616, f-513609cda854df1443f04ea2, f-51f0050cc7364c37d93c4536, f-59f59ab68f826f4f67f2ba7e, f-5a76ca197a8b3d8c3110cc28, f-5b65bf41fa7958df04993d51, f-5ee7b9860280d10245807205, f-5fc1fd9b777b4f9d57996007, f-60b24d4ec1b0728951707470, f-650a47983cb7304f29b942c1, f-665725bd19f25636de811b01, f-67c52a321c7de7fea10d52ef, f-6892922a2374d99bdb771d0a, f-69509cd44f4ed2a6e5352afe, f-6ac5517a37c90d2b13a0f462, f-6c1d2cdebbaee920581cdbc7, f-6f1f6eab7b4d3677f9304120, f-7844b4adc9cf9ce621fa071f, f-7ff5839508597795992f43f7, f-8105fd57027c985c09451560, f-82449b809c642f7ab64f343a, f-825e39e575cea9e23eac405a, f-83f6a75203b752f9276cb4ff, f-895729d9d350b0d8636b0f90, f-8e307a4a4122403b23f1d993, f-98e2a6c9b4d96b64292113b1, f-9e6bc73c266328fd8a8d7e93, f-a1afc849e77cca67e9642cd6, f-a3b7097217e2df585857862a, f-a3be53021f43876b48874c53, f-a44a58e681dc24cf7dad01b5, f-b5a5695e1dfe0aebf511c520, f-b7f2530b505a87b6ba8902a8, f-bccdfdf4d9f1069b07034eb5, f-c1769f1d014ac5775664ea6f, f-c25f1eb0e3003c023b1c98a9, f-c27e8117bf7029a47e1539a5, f-c51591d582c5f074ac3f89c4, f-c82ba31dd02313add8b02dca, f-ce56f88ef008ad283ba322ad, f-ddbdbf2de8015ee65d49b7f7, f-e2c0f152cf8afccedb58fcba, f-e5c5dffc9e0254c2ed638427, f-edbd9a95512a11a346119585, f-efeaa6a097c1dfec48b23dd9, f-f276d3f358ae5b245a66b7aa, f-f2829d645f41f7dc3ebd19bd, f-f38456064209a593de6ed860, f-f3956f7045ab4076d92b4ac6, f-f3e95c00cfe5d96a5c4222d8, f-f7e76f85c5058675add98c5b, f-f99c2ac2b7d342a902ed6fc5, f-fa44d45f77df0654a21fa89f, f-fbd57d8b27d20eb64c2816a8, f-ff9dfe4d13da77b536cbf3ac

ru · official · sha256:a2edf3d8b6b515e94459afa63c31362088ab66aa9dab3ba94da3c37f3cbc4ad5RU

§3. Построение кода Хаффмана Задача: по алфавиту с заданными частотами символов построить префиксный код наименьшей средней длины. Вариант — восходящее слияние двух наименее частых узлов через приоритетную очередь. Каждому символу отводится узел с его частотой; все узлы помещаются в приоритетную очередь. Пока в очереди больше одного узла, извлекаются два наименьших, создаётся новый узел с суммой их частот и этими двумя в качестве потомков, и он возвращается в очередь. Последний оставшийся узел есть корень дерева кода; кодовое слово символа читается путём от корня к его листу. Основание — жадный обмен: в некотором оптимальном коде два наименее частых символа имеют кодовые слова наибольшей и равной длины и различаются последним битом. Отсюда слияние двух наименьших не теряет оптимальности. Утверждение принадлежит источнику. Оптимальность код Хаффмана даёт среди ПОСИМВОЛЬНЫХ префиксных кодов. Арифметическое кодирование даёт меньшую среднюю длину, не будучи посимвольным, и это не опровержение оптимальности Хаффмана, а иная постановка. Ограничение обязано называться. Крайние случаи: алфавит из одного символа — дерева нет, и кодовое слово обязано быть назначено соглашением, обычно одним битом; символы с равными частотами — код не единственен, и разные порядки извлечения дают разные коды одинаковой средней длины. Декодеру нужно САМО ДЕРЕВО либо длины кодовых слов; их передача есть часть формата, а не деталь. Изложение, умалчивающее об этом, описывает лишь половину метода. Оценка: построение стоит порядка n·log n при n символах — по одному извлечению и вставке на слияние.

Referencing norms: f-09784895c065cd96cff8a848, f-100b97255a2dac9b7c1896d5, f-104ec8b494b6d7b99e848d9b, f-17b4f36095c0847736b74978, f-180991744b4716035d4fd677, f-1af8835fa9d79f567fed2dc8, f-1be51a5159416eadb6702f97, f-23860220f1f694416011ec3d, f-265daf4edd455a92ce408111, f-2c0c5dc3b8c23860cd2c84f8, f-304412b7e5053ec1a40ad96e, f-306e1d9e22fb61cd10296d45, f-30ce93c25aecdb9fbeeec218, f-3146af7f91dab8ad7c08a969, f-3309493e2343a22bf82176dd, f-3342e83b3789eead80c77288, f-36a653f4d611f301cf7f635b, f-36fcf8eb9e5eec7646a22368, f-3b7341b4a67d8b7dbc5d9fdb, f-3c7921f5e458468aaf8d4f15, f-52a61d266b5d9c8912b51500, f-53eaa4462856a860bac6f4a1, f-580ab9a89009af9c6885ba3b, f-5dad98c97941cca4836fcd65, f-5e0521a1952c1a18ef21a3bd, f-62709dead7a939d24c983107, f-6521e7e58829729bfa8b4237, f-6580677268a07e9324c8dfae, f-676e472b6566f2ce8aeb8af4, f-6e617f3ef5d368a7f0782c12, f-7831d1752cdbdca8f90cbbb7, f-7b27889bc4911673fd9b1b6a, f-7c6568e90bc59ad0304d50ea, f-7f945880ad321801104be3fa, f-802ab5f675f32bfc8bc50c2c, f-8487f9003c9eefc040030ace, f-85a86de98fc5ec3fd2901b34, f-8c9be2d6d259b9551536f7a4, f-8caa7011c8660d6663499b36, f-8e02852d73321bc0f3d3c0d7, f-8e76a2762d8e987973ebd159, f-8e7e8495857b6b9f5d3729c6, f-9377eeb2e5e3ab2f82bb02e3, f-9713e1ee8b7fdfbd170caf8e, f-98959c81cb357d8136351cb4, f-a0b20c9195b9019d99f9a0e6, f-a2564e1d121a0a0bf973cc63, f-a5ce5b71aea490219e875f3c, f-af4d9cf1b5312fc681677c67, f-afbc694c2d04527fd539f9c0, f-b0e4e7b0ca424c2b6f472a43, f-b12fe3e3babd22423438e7ef, f-b2b9b3d2e9e20ad0ac873b86, f-b422069580c6524a1719825a, f-b89da08e3fd8eae1af6166af, f-bef091ee4d9d648e1d72a82c, f-c003003b7b26e440e02703f7, f-c5c5d21e99cb21fbe199d6b2, f-c89c8fcf401b303d4ee6dd4c, f-c96b0f5387dcb4e0c41929d8, f-cb4fa13663fa059d77b372c5, f-d362e8fc1986a76a7acfa6f1, f-d36a907cdaefd6980a27a2a1, f-d3b6ba9e7f4db7103a7ffb26, f-d9984f2c5a107463b52eb0ed, f-e58445d9487430c3e087e1e2, f-e80f6495a38f0e9e93ae1083, f-ec0b0480b2d83d3df619eb48, f-f0b1ea576494bf5a973330f2, f-f1fb177c1c24520935d4bd23, f-f2a7bc84e08d8b9df8711ed5, f-f6476904c2342b2a91431be0, f-f89aac50533ae57fc97282fc, f-fa2e824d57b88ee2eb79eed3, f-fb6201a188d5bc39e811f182, f-fdf95d7677c4b01454dc1f34, f-fff6d4e15cb6de62ad0f6cb1

ru · official · sha256:efc2716074c78ffd5fd22cf7be1436b1651a8aa8ea5a5943732fd16f5a227fa4RU

§4. Сжатие методом LZ77 Задача: по последовательности символов получить кодирование ссылками на уже встреченные участки. Вариант — скользящее окно с тройками «смещение, длина, следующий символ». Поддерживаются окно уже обработанного входа и буфер предпросмотра. На каждом шаге ищется самое длинное совпадение начала буфера с участком окна. Выдаётся тройка: смещение назад до начала совпадения, длина совпадения и первый несовпавший символ. Затем окно и буфер сдвигаются на длину совпадения плюс единица. Совпадение допускается ПЕРЕКРЫВАЮЩИМСЯ с буфером: ссылка на участок, который ещё дописывается при декодировании, законна и даёт эффективное кодирование серий. Это самое неочевидное место метода и обязано называться прямо. При отсутствии совпадения выдаётся тройка с нулевыми смещением и длиной и самим символом. Отсюда и худший случай: вход без повторов кодируется длиннее исходного. Инвариант: по выданной части кода декодер восстанавливает в точности пройденную часть входа, и окно декодера совпадает с окном кодера. Размер окна и максимальная длина совпадения суть ПАРАМЕТРЫ варианта: они определяют и степень сжатия, и стоимость поиска. Изложение без них неполно. Оценка: при наивном поиске совпадения стоимость есть произведение длины входа на размер окна; хеш-таблицы и деревья суффиксов её снижают и составляют другие описания.

Referencing norms: f-02f149ef2e5a48b98b8ffe03, f-03c0f7f96fcd2f7c2d9c9671, f-04ac776e0b79d2e2ef1f0866, f-05d29aef39d9578e4b5656cd, f-0720403adcbfb9dda161c224, f-0b94ed33797a19efabd264b9, f-0bd39acbc0b19037d663e198, f-0f144d96449008e187eff49b, f-0f9c136a15e29cea4052369d, f-11efc308ffc11c70c68331d1, f-120696c816f32852c666807e, f-13b0995f72ee682acfd4a92c, f-14705c74851dace309245333, f-17db75aff1e7dbc8b584956b, f-18b57c0bec66fb33bab864d6, f-194fb47f2743332132adec30, f-1fd8d74f858ee5e9d9bf7073, f-20e6d6714cb87b5e31155272, f-227ae4076719b2df236f716c, f-27a455dcb5145ee50fb18a53, f-28edf38df5084be9327a888e, f-29a26773bc534b1c929e06a9, f-2f18914d35c46f4e98704f85, f-2fa3b6696a8b2fa192b7a3e6, f-32176f1cc0e47cf727875d17, f-351d10804efea8dd12b430f7, f-352a02cda18a9d86a97550a8, f-4b02e5fe71aa3fbb8a2f7b5f, f-4ff13c80ad196a545e641c55, f-53730795f85a09097d4cd87b, f-5761735f414680d7a29a947f, f-58393a23077e0169801ccb3b, f-5ce93395d91ca76afb0471a7, f-5e97eae1164d57e81c5cacf7, f-6259a02fb92266efc700a1c2, f-65871d9f0092f92c1f7d1cd7, f-6610fff416362f6d554253ee, f-6a30224a31acecffd35ca241, f-6cb4223c139ff1c83b9ec352, f-6e49c30ac57c0fad2b5509cf, f-73f1095530c35f2dbb850492, f-7f3f64abb56c6d46f94faaff, f-84ccd3033ba2dce548b22ac5, f-8ca49cdaad64a1c9a24f7b7c, f-8d12dc16c159611f809172b7, f-965518c197019e78b26f612c, f-a6457d22dc1cc78a3a026f4e, f-abcd537a40bd62382a618a84, f-ac6b53e7926deb8481613bc3, f-b5b300f2b601a95f0933c916, f-b5d898ab5708ad01ece29983, f-b71f32ba08bde5504a48c7e0, f-b976cdf9c7d46384cd8bd51c, f-bcd426f19a86625b7b665d74, f-bd84502ee499e92d922f8d0c, f-c01cdf5fb07d0b009fcd6511, f-c0f3bb1e4e979d162da5ab65, f-c71ac201cf569190b3d2660a, f-c957844af7fcdc9866e955dc, f-ca3aee75029f397c51fe775b, f-ce1efffb805d08a4218aac6a, f-cee290eb2ec998214a00e964, f-d0e378cd673f281e3d0f6b6b, f-d381094c0eef352d5e3c7945, f-d770b3e8072362a104d664ca, f-db274d87737c4a3a9d663501, f-dd03d31a98c736bb5cb1ff97, f-de3334f01995f358c4d55f4a, f-e100721737d7c5226f23126b, f-e3f5ece991f8a44ae48929c0, f-e4b3a1d481a8026ec5fdebfc, f-e6f4478050aa64e906e445f8, f-ef43738610c2845b2df8f201, f-efd85c797bf90e3b1dec9c81, f-f0570907ac874e992d2e8b02, f-f31be8dbf7ea7fa91384712c, f-f59a320ba42a5be245ed1a9c, f-f5f308185497ac0fb820cf7a, f-f737da6bc56465f555b1b71b, f-f9769be3f624e4f7a14195d4, f-fb158155d155d95d896c349d

ru · official · sha256:97eade8d4642af3561ec28416fb3ebdb7b14b2578763d5ab25be1146de330d97RU

§5. Сжатие методом LZW Задача та же. Вариант — растущий словарь без явных ссылок: выдаются только номера словарных слов. Словарь начинается со всех односимвольных слов. Поддерживается текущая строка. Для очередного символа: если строка вместе с ним есть в словаре, символ присоединяется к строке; иначе выдаётся номер строки, строка вместе с символом добавляется в словарь новым номером, а текущей строкой становится сам символ. По исчерпании входа выдаётся номер оставшейся строки. Отличие от LZ77 существенно и называется прямо: LZW не передаёт ни смещений, ни длин — только номера, а словарь ДЕКОДЕР СТРОИТ САМ по тем же правилам. Синхронность словарей кодера и декодера есть инвариант метода. Отсюда единственный тонкий случай, который обязан быть назван: декодер получает номер, которого в его словаре ещё нет. Это происходит, когда кодер только что добавил слово и сразу его использовал; такое слово имеет вид «предыдущая строка вместе с её первым символом», и декодер обязан обработать этот случай отдельно. Изложение, его не называющее, описывает неверный декодер. Крайние случаи: переполнение словаря — требуется соглашение о сбросе либо о прекращении роста; пустой вход — код пуст. Оценка: один проход, время линейно по длине входа при словаре с постоянным временем поиска; память определяется размером словаря, который есть параметр варианта.

Referencing norms: f-026890cce4d72a6f85211b99, f-03badd07cc727e7bb07589ef, f-0643da2d45bca7164a48b737, f-0beaca928f4d5f3cae2bacb2, f-0fbde525c9a74f265c076e54, f-10b1b5d040cf497d7d89622e, f-15ceb94781625c2c8b7163e6, f-18f79b4ae4be4faa29a61bc9, f-1932cda1b2081d1a48fdbf04, f-19cf3ce0ed91b70d26fdb802, f-1ee5cb283be356f7b8c04351, f-1fceb6586d35e22632db3eba, f-26b152bf3263fe5dc9db260a, f-27c5caec08e396a4a786814a, f-28a5271502ac5fecced36662, f-2acb4fc31860b0ed4eac6f1f, f-36670bd95c139768259d552a, f-36cb5d7848d5db8ed71f09dd, f-38db65fe7f81b8add3e1f6e7, f-3d08ae5332ac3e2ab6b3ca1e, f-422a3757d09da650cbe7b876, f-490e3ce5048af9aa2582f2ae, f-49604020ce53c47fe90283a5, f-4c16e8f06b1c26ec4eabf9db, f-4dda0fdb99088bafc25262d8, f-4df55689ba58e8d39c710546, f-5071b85f16a378d7bc729fb3, f-51adbc65016cfaa1389e56c6, f-592f393fe281d2fc583812ca, f-5b23cfdeeb3a4783448db404, f-5d3b081419bdcb733c497d28, f-63971eeb615c305d66a35c6c, f-641b0d4d02d279948f630b90, f-64eb2e82d84ce29b62479c2d, f-6590e30f905d7e1c7bb7b270, f-659ebde0cd93edcc6d63f003, f-65f984846589a4a7a7bc9924, f-68de0328c40da522d0a50bea, f-6d0a669002cec7589a9bdf91, f-6dc16535a171ab7513e9f5b9, f-70d4a607b277ca7e0dd9d9ec, f-730498a27a43abc4f82a28bc, f-79ee531a7c5e25ed92b723e6, f-7a07607418c45e53d1bbb1fa, f-7bfd9704f7aa4f9357226f1b, f-816f2bc67615a385b80422b6, f-866a8c0e3cf81f7b55aae1ed, f-88c791381951822e84b39609, f-8b7e3e1f33c1a7486f82c7c6, f-8c42a95be498680ca88bf178, f-8cdeb8849227cbfc4372079d, f-8d9a80d2ce360afe9b8508bc, f-8f73bd9d5ae7c822fdf7ebf8, f-91de2ac9b8dd2f0806ee796a, f-996544c55d99f0c768e5fcaf, f-9b3cbe3e9ee6d396b13f5bb4, f-9b440825da0acc43f3570b29, f-9bde7e1a35109b5f7a80e7fd, f-afa87f6695b358ae4eb42c60, f-b08eb0e451e03128e0550547, f-bacb7226a0d624c14c2bd817, f-bb4e677e6ffa665b79fb5a0f, f-bfb236d4d1978bc06b8eb1b0, f-c23bab87f65c8988628ce8ae, f-c30d06e9768dca8cf504138d, f-c49d8624d03a08f8b34f5b07, f-c95870925f930ec7038c390d, f-cb3009d392def5872fc3271a, f-cba7fca53bf3c4fa95c6f806, f-cc9cbc65ee148542eaee1bde, f-cd263acd62378bbd3810aae8, f-ce1343550142fc1723b36efa, f-d0ffd14a03b1e5d6693a0116, f-d676bcf1cc4ec94b08493cbd, f-da2f00cb374a12914b7fba32, f-de5654bca90fe22ae2c922b4, f-e166da3131d7239047d17bf9, f-e419462612ac00fb1637c921, f-e48b4fd4d71d3032b603badf, f-ea6a3e38407165d7a9a3e10d, f-eb1715c06e0901e9705017eb, f-ebbb622546d49ba8932035c9, f-efbb53fbed28526ad3c52b94, f-effe2c66b21cdb9b7e31eb6c, f-f17b48a8af77fad752f789a3, f-f4613523c53b141c669e9177, f-f5c6fc4f1bf092f79e7bef48, f-f9843d2b12cab82fe3ad72f3, f-fa12d9ec30970bcaf521233c, f-fa9233e917c89a4892df6d86

ru · official · sha256:fa72057fe4347e50ccd99fda80a651bd85246056056ea60aef942ed6117cab7eRU

§6. Кодирование кодом Хэмминга (7,4) Задача: по четырём информационным битам построить семибитовое кодовое слово, позволяющее исправить одну ошибку. Три проверочных бита ставятся в позиции, являющиеся степенями двойки — первую, вторую и четвёртую; информационные занимают остальные. Каждый проверочный бит равен сумме по модулю два тех информационных, номера позиций которых содержат соответствующий разряд в двоичной записи. Выбор позиций степеней двойки не произволен: он и делает синдром §7 прямым двоичным номером ошибочной позиции. Иная расстановка требует таблицы соответствия, и это другой вариант. Минимальное расстояние кода равно трём. Отсюда, по §1, он исправляет одну ошибку и ОБНАРУЖИВАЕТ две, но исправить две не может: слово с двумя ошибками ближе к другому кодовому, и «исправление» даст неверный результат молча. Это ограничение обязано называться вместе с кодом. Кодирование удлиняет данные с четырёх бит до семи. Избыточность добавлена намеренно: код не сжимает, а защищает.

Referencing norms: f-03ad2bdb0b616f99c7952297, f-059dc45638502bca8eee30ec, f-084c557e8ebf6625a4068422, f-0bdf2f10efc8b8b93c6d8a8d, f-18165ea051b53428f6ee041b, f-183589d204f85993b1af6668, f-18a7b376ae0f46b1f117f8d5, f-1b464e1246066b9f40029850, f-1be762ddd649dc7773c4257e, f-23cba4c91566d3bf3a3b6f12, f-2b0ae2c78f28060a84ed5964, f-2bf44eb50a29e5ea4056af07, f-3ab0c0e3123a6aa2f2bae8f9, f-481d4ef218cfa25050cfb127, f-4901ee80a3837633b65e2f12, f-4b14832c139e032ec2267cdf, f-4c350b182a25cd139125fd0e, f-4eb8dd6a375131703ac6fe7f, f-5a369ef20c1b81b24cb7b2cc, f-5f39622c3706f9c0491db8ab, f-622d6e30532e269943071bab, f-638b221c3005b212a15478a9, f-66d96e87dae7e092d215efb6, f-6995086540ba220460e70bd1, f-6a6db77ebfe9bab5d1b9bd2f, f-6b2d12818fabbaa879409600, f-6e6ffb9fa43ae6c06f106c81, f-749047bdb2895b2c854907dc, f-7c4ef1c8b0319855e7529de4, f-8285ee95296de1a9f0490a99, f-859e9f6dfbe23eb25a067c55, f-903abaa127b5b37934121fec, f-91205c2c99d212eb761068b9, f-93110cd3ec40e48065893f0c, f-931b8863ff955ae2022147a3, f-93ef11962583892926e63d04, f-95aa685e4ab4e67df0f56b05, f-9850043b7e91f38c1074a9b4, f-9fc29941e52104ed11cd6a2b, f-9fce84a247686688a97b1c2d, f-a0bfc2c98a61ad138af8a5bc, f-a4d2f19f6aff76b5ae468293, f-a4ef97589ddb473434d9e229, f-aa0c037545dd577da0b0ba0c, f-ab4463d9d2bc556e0253c514, f-b07a1aa17789ec44e1c647b0, f-b1047b3da7f8c4cc4d7c282d, f-b33e3eb274e8fbc62f293546, f-b8e35ebd46879b4ed14827b7, f-bb7bd31b8c5da1ae7ffcbe6d, f-bdda77a638807b102bdf21bd, f-c048867fdb41ce53916f0aed, f-c0a1d6c5d4bdc6204819b0d3, f-c5a56827529ac38cdf1835a1, f-d215019113c783e44a49f921, f-d28ef85cb23bc05746e2ab06, f-d30674652dd1e0a2c135f45d, f-d4775087dcb9cb3ecbc74d47, f-e57698519dc5211084c224b3, f-e7a616ec7ae1ca0000e45cfb, f-eb8ec8b1aaf9ff9c42b6502a, f-f0b73a45e528f07b25e39ecc, f-f11842332d4ddc6d7ca6e1a0, f-f8f16d1623c735e32fb9990c, f-f9246fcfa8dd25ff6d258703, f-f9fdd48a90b415d5b1bcf312, f-fa19cc5b69d839b6b42a9ee0

ru · official · sha256:5beea663199858138bfae1ded71dbe50b3001ca66830c67ff966648a2e1469dbRU

§7. Исправление одиночной ошибки кодом Хэмминга (7,4) Задача: по принятому семибитовому слову обнаружить и исправить одиночную ошибку. Вычисляются три проверочные суммы по тем же правилам, что при кодировании. Полученные три бита, взятые как двоичное число, образуют СИНДРОМ. Нулевой синдром означает отсутствие обнаруженной ошибки. Ненулевой синдром есть прямой номер искажённой позиции, и её бит инвертируется. То, что синдром есть прямой номер позиции, а не индекс в таблице, целиком обязано расстановке проверочных битов по степеням двойки §6. Это и есть содержание кода. Ограничение обязано предъявляться вместе с исправлением: при ДВУХ ошибках синдром ненулевой и указывает на позицию, которая ошибочной не является. Описание «исправит» неверный бит и выдаст неверное слово, не сообщив об этом. Обнаружение двух ошибок требует расширенного кода (8,4) с дополнительным битом общей чётности — другой вариант. Крайние случаи: нулевой синдром при трёх ошибках — они складываются в другое кодовое слово, и ошибка не обнаруживается вовсе; ошибка в самом проверочном бите — синдром указывает на него же, и исправление верно. Оценка: постоянное число операций на слово, повторений в описании нет.

Referencing norms: f-07ed9b60a9e071d2140fa970, f-0a24063ea5065e004b9a3b2f, f-0df685de8a50e1c41f964458, f-114a79808c9a716567811552, f-12ce7541b96c237afb9d5bc4, f-145b3582c3e2d26adb4f3a1d, f-14cf0d5cc0ab9eab63da3857, f-153f157acba251b2e9e98f92, f-155d6caa4ba57954f0200dda, f-1c883fa9c0b7cc94b335d427, f-1cbb6587f6a8f9f0612d2d7c, f-2687b7d9357ec50fd2b74884, f-2894941a054f5530c461751e, f-2a5e7d989cb02379f1aa572a, f-2f4dcd76a6fa9a7bd856ca2f, f-3a72a773ae4922ef25e4b29c, f-3cca4c7f7c20056d9985d971, f-3d0db3ecbaa4ecc9b6f88da9, f-410ce392ddddd64fb5c60157, f-456961616ef3ad043d5238b3, f-473e2c26b827620507b29a61, f-4ba594d7000442c61cc3e980, f-4c5af57816fcf3c822bc7596, f-4cc5f21fa01a79cc538803db, f-515711cf56ff1a40751d04a9, f-54e8c387ab91bee1ed1efb34, f-581f7235230922afd09effea, f-583c8c72e1cf3cb0473afd0e, f-60ee569260aae5aa2e0791e5, f-6292c62e4b711a97f0643763, f-675077b171311b25bda6e344, f-67fdf06e66cc409593058d6f, f-6960af119f4746e0d9cd6de6, f-6eac280e7b62b2da8c95c70b, f-6f4f9ae74032df0def5e6db5, f-717887826513820eb5200558, f-75f38ddb2db292c40c206244, f-765f2444137cefd892333b3e, f-797b48f28b20a963fe8ac314, f-7a4b186df1ff7d160d3fc43a, f-7b736081ca4b1c781ee67e7d, f-7e2544ee105cad22816ad544, f-83fe4c5821cc97fa1e9376dd, f-8558d09e04d05a5947db69cf, f-87937fc076f8aa28dc1e372f, f-87c96eb444db814391cfb73d, f-8d4a703f09e05dd94c269055, f-9142120f7be4135c5120eba9, f-95caf85180c09b53391f9a56, f-9ff1d0bdc10346a708697a65, f-a3f119edbf03c15a13bb45e8, f-a6f3efb9154997ab129fac1d, f-add00f15f5f7186afa7e5c15, f-af8dfa97a7928023ed424823, f-b00eb7dc60d117ff4e564667, f-b1d57f365fca69fc78d54ad0, f-b510cd7f3829642842336521, f-b5a909db46d6b48f405eff18, f-bf2301c1d430f6bf2e9f5ee5, f-c0a307bb720b167c30130ce1, f-c3dacd53606d8fd1cb12de13, f-c59d30e84afb039ac7774c78, f-cbcbecc5271348ace7d5baa5, f-cca6d1cd895a2c1620e3aedb, f-cfd9b8965ae285bb6e04861d, f-d6ec00d38eca10f9b6217ab7, f-de0eb727f55675e08285e917, f-deea504976db09908d435861, f-e2fac8f631e5130d42b9496e, f-e3b00e09bd8f6a0fd439ac12, f-e405b913ea2b124d029fb003, f-e5cf07d1e13341f93274ccfb, f-e8a71958e58eb5e8d93457f5, f-f7b29dd4ec59f16dd75f3fca, f-fa94c863eadb646d50291307, f-fe68a2b40927e2f7374305ee

ru · official · sha256:3ceaa8ffa7f580299c1406e4d5ef5796de6372e13de35685102726790f0812f7RU

СЖАТИЕ И КОДИРОВАНИЕ: RLE, ХАФФМАН, LZ77, LZW И КОД ХЭММИНГА (7,4) Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство шести алгоритмов: кодирования длин серий, построения кода Хаффмана, сжатия методами LZ77 и LZW, а также кодирования и исправления одиночной ошибки кодом Хэмминга (7,4). Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни один поток здесь не сжимается.