Языковая политика
Общие обсуждения => Наука и техника => Topic started by: Toman on 20 March 2024, 03:05:08
-
Чисто практическая задачка. Информация о состоянии некого объекта передаётся при помощи двоичного кода (например, включением-выключением некоторого сигнала по границам некоторых периодов равной продолжительности, которую можно считать единичной). Код является периодическим и циклическим, т.е. постоянно повторяется, и начало/конец кодовой комбинации никак не обозначены, т.е. всё, что получается друг из друга циклической перестановкой, считается одним и тем же кодом. При этом длина кодового цикла заранее задана, и кроме того, задано, что цикл обязан состоять из двух половин, являющихся побитной инверсией друг друга.
Вопрос: как посчитать число различимых кодовых комбинаций для любой заданной длины половины цикла (натурального числа)?
-
Число асимметричных перестановок?
-
Число асимметричных перестановок?
Почему асимметричных?
-
На НЛ Хеллерик дал такую ссылку: https://oeis.org/A000016/list
И формулу, дающую достаточно хорошее приближение (для достаточно длинных кодов): a(n) = 2^n/(2*n)
Вроде да, это тот самый ряд. На длинах в степени двойки принимает значения степеней двойки, как можно заметить - точно соответствующие этой формуле.
-
Что касается самой формулировки задачки - то "двойной" код длиной 2n, состоящий из "ритмически одинаковых", просто побитово инвертированных половинок длины n, можно представить проще - как двоичный код длины n, где каждый разряд соответствует месту, где состояние сигнала меняется или не меняется (соотв. 1 или 0), тогда условие, что половины именно инвертированы, преобразуется в то, что в дифференциальном коде должно быть всегда нечётное число единиц.
Дальше нам надо по-прежнему собрать все возможные такие коды в кучки таких, которые переходят друг в друга при циклическом сдвиге, и пересчитать эти кучки - в чём и состоит суть задачи.