Общие обсуждения > Наука и техника

Задачка о ёмкости кода

(1/1)

Toman:
Чисто практическая задачка. Информация о состоянии некого объекта передаётся при помощи двоичного кода (например, включением-выключением некоторого сигнала по границам некоторых периодов равной продолжительности, которую можно считать единичной). Код является периодическим и циклическим, т.е. постоянно повторяется, и начало/конец кодовой комбинации никак не обозначены, т.е. всё, что получается друг из друга циклической перестановкой, считается одним и тем же кодом. При этом длина кодового цикла заранее задана, и кроме того, задано, что цикл обязан состоять из двух половин, являющихся побитной инверсией друг друга.
Вопрос: как посчитать число различимых кодовых комбинаций для любой заданной длины половины цикла (натурального числа)?

Bhudh:
Число асимметричных перестановок?

Toman:

--- Quote from: Bhudh on 20 March 2024, 04:03:01 ---Число асимметричных перестановок?

--- End quote ---
Почему асимметричных?

Toman:
На НЛ Хеллерик дал такую ссылку: https://oeis.org/A000016/list
И формулу, дающую достаточно хорошее приближение (для достаточно длинных кодов): a(n) = 2^n/(2*n)
Вроде да, это тот самый ряд. На длинах в степени двойки принимает значения степеней двойки, как можно заметить - точно соответствующие этой формуле.

Toman:
Что касается самой формулировки задачки - то "двойной" код длиной 2n, состоящий из "ритмически одинаковых", просто побитово инвертированных половинок длины n, можно представить проще - как двоичный код длины n, где каждый разряд соответствует месту, где состояние сигнала меняется или не меняется (соотв. 1 или 0), тогда условие, что половины именно инвертированы, преобразуется в то, что в дифференциальном коде должно быть всегда нечётное число единиц.
Дальше нам надо по-прежнему собрать все возможные такие коды в кучки таких, которые переходят друг в друга при циклическом сдвиге, и пересчитать эти кучки - в чём и состоит суть задачи.

Navigation

[0] Message Index