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

[Toman]

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

[Hellerick]

Как это теоритечески объясняется, я не уверен, но вообще вот эта последовательность: https://oeis.org/A000016/list

n		a(n)
0		1
1		1
2		1
3		2
4		2
5		4
6		6
7		10
8		16
9		30
10		52
11		94
12		172
13		316
14		586
15		1096
16		2048
17		3856
18		7286
19		13798
20		26216
21		49940
22		95326
23		182362
24		349536
25		671092
26		1290556
27		2485534
28		4793492
29		9256396
30		17895736
31		34636834
32		67108864
33		130150588
34		252645136
35		490853416

[Hellerick]

Хорошее приближение дает формула a(n) = 2^n/(2*n).

[Toman]

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

[Hellerick]

Я банально перебрал варианты.

Код Выделить Развернуть

for halflength in range(1, 21):
    binaryformat = '{:0'+str(halflength)+'b}'
    combinations = set()
    for i in range(2**halflength):
        code = binaryformat.format(i)
        code = code+''.join(['1' if c=='0' else '0' for c in code])
        normalizedcode = min([code[j:]+code[:j] for j in range(len(code))])
        combinations |= {normalizedcode}
    combinations = sorted(list(combinations))
    print(f'Length {halflength}, combinations {len(combinations)}')
    #print(combinations)


Length 1, combinations 1
Length 2, combinations 1
Length 3, combinations 2
Length 4, combinations 2
Length 5, combinations 4
Length 6, combinations 6
Length 7, combinations 10
Length 8, combinations 16
Length 9, combinations 30
Length 10, combinations 52
Length 11, combinations 94
Length 12, combinations 172
Length 13, combinations 316
Length 14, combinations 586
Length 15, combinations 1096
Length 16, combinations 2048
Length 17, combinations 3856
Length 18, combinations 7286
Length 19, combinations 13798
Length 20, combinations 26216