Приветствую! Подскажите плз некий код Грея, только равномерный: в обычном рефлексном коде Грея биты неизменны 2 такта, а надо больше и равномернее. Сейчас объясню, что бы мне хотелось.
Берём обычный 2-битный код Грея. В нём каждый бит неизменен 2 такта. Это здОрово по сравнению с обычным бинарным кодом, в котором бит может меняться каждый такт. Однако берём тот же обычный код Грея на 3 разряда. Всё равно неизменность 2 такта. Берём 10 разрядов - всё равно 2 такта.
А мне бы хотелось иметь некий код, интервал неизменности каждого разряда которого увеличивался бы с увеличением числа бит в коде. Т.е. берём 2-битный код - имеем неизменность по одной линии 2 такта. Берём 4-битный код - неизменность 4 такта. Берём 10-битный код - неизменность 10 тактов по одной линии. Ну может не так линейно, например, для 10 битов неизменность 7 или 8 тактов, но всё равно, чтобы интервал неизменности увеличивался с числом бит кода.

Ну и при этом нужно, чтобы свойство кода Грея оставалось: в каждом такте меняется только один бит.

Такое вообще возможно?

Наверное да. Но не в бинарной логике, а например в тринарной.

надо некий компромисс
в бинарной

Если из нескольких слов грея такой код составить?

Например

00 00
00 01
01 01
01 11
11 11
11 10
10 10
10 00

Просто, мне кажется, что цифра 2 берется от того, что код бинарный. Если брать тринарный код, то цифра будет 3, т.е бит в коде будет меняться за 3 такта. Ну и так далее, т.е это число определяется реализацией системы счисления.

Легко показать, что для такого двоичного счетчика с периодом N и неизменностью N, период счета неизбежно равен 2N. Такой счетчик - это сдвиговый регистр, в который сначала вдвигается до полного заполнения единица, а потом - нуль. При N=2 он же есть счетчик в коде Грея. Но Вы, наверное, имеете в виду полный счетчик с периодом 2^N при N>2?

При N=3 код с неизменностью 2 - это код Грея.
При N = 4 если код с неизменностью 3 существует, то его несложно подобрать компьютером.
Если не существует - над этим фактом можно будет задуматься

Кнут говорит что такие коды ищутся только полным перебором. См. том 4, вып 2. рис 14 - пример 8-ми битного длинносерийного кода с длиной серии 5. Там же дана асимптотическая оценка максмимальной длины серии N-битного кода как N-log(N). Серии больше двух начинаются с 5-ти битного кода с длиной серии 4. Номера изменяющихся битов в этом коде: 0123042103210423 и еще раз повторить ту же последовательность (см формулу 30 в Кнуте).

Том 4?
А я его пропустил. Спасибо.

Я как-то раз решал похожую задачу: нужен был тикающий счётчик в EEPROM, и надо было сделать wear-leveling, то есть чтобы при каждом приращении счётчика менялся только 1 байт, и частота изменения байтов счётчика была приблизительно одинаковой. У Вас не та же задача?
Пришёл к некому решению. Поиск по патентам США привёл к патенту, в котором та же задача решена точно так же :-) Если надо, могу попробовать снова найти этот патент.

Спасибо всем за ответы, извините, что долго молчал - уезжал на недельку в отпуск.
Судя по ответам пришёл к выводу, что я ничего не понимаю в комбинаторике, а всё, что хоть как-то понимал - полностью выветрилось. Сейчас попробую как-то попытаться понять ваши сообщения.

Если не сильно у Вас отниму время - то был бы благодарен за информацию.


Давайте я попробую обрисовать задачу, зачем мне это понадобилось.
Сразу скажу, что всё реализуется в ПЛИС. Есть счётчик (грубо говоря счётчик времени) с тактовой частотой 100 МГц, значения с его выхода поступают по шине в некий блок, в который заходит тактовая частота 30 МГц, другой нет. В этом блоке на частоте 30 МГц необходимо защёлкнуть значения времени, изменяющиеся с частотой 100 МГц. Поскольку частоты разные - при обычной бесхитростной реализации "в лоб" очень часто будет возникать метастабильность, гонки фронтов и т.п., в результате чего правильные значения времени будут защёлкиваться далеко не всегда. Поэтому невозможно гарантировать безошибочное защёлкивание показаний времени (пусть хотя бы с погрешностью, связанной с изменяющимся взаимным положением фронтов частот 100 МГц и 30 МГц), т.е. могут быть не только погрешности, но и грубые промахи отсчётов, когда, скажем, в результате метастабильности, неправильно защёлкнулся старший разряд.
Для подавления метастабильности зачастую используют код Грея, т.к. у него в один момент изменяется только 1 бит, и последовательно сменяющиеся значения могут приобрести ошибку всего на единицу: либо счётчик в момент защёлкивания останется в предыдущем состоянии (без изменений), либо защёлкнется новое значение. Однако применение кода Грея для борьбы с метастабильностью имеет смысл только, когда частоты сигналов приблизительно одинаковые, но фронты не синхронные.
В моём же случае частоты существенно разные: 100 МГц и 30 МГц. При использовании кода Грея я смогу получить изменение одного разряда с тактовой частотой в 2 раза ниже, чем 100 МГц, т.е. 50 МГц. А защёлкиваю я эти значения на частоте 30 МГц, т.е. ещё почти в 2 раза медленнее. Таким образом, из-за гонок фронтов, связанных с разностью длин связей отдельных разрядов шины данных, я опять не могу гарантировать отсутствие промахов (грубых ошибок) измерения временных отсчётов.
Ладно, если частота защёлкивания 30 МГц уже ближе к 50 МГц, уже можно что-то придумать. Но уже появился спортивный интерес найти универсальное решение, работающее в общем случае, не только, когда частоты близки друг к другу.
Вот тут и возникает потребность, как я писал в первом сообщении, в некоем коде Грея, только равномерном, интервал неизменности каждого разряда которого увеличивался бы с увеличением числа бит в коде. Т.е. берём 2-битный код - имеем неизменность по одной линии 2 такта. Берём 4-битный код - неизменность 4 такта. Берём 10-битный код - неизменность 10 тактов по одной линии. Ну может не так линейно, например, для 10 битов неизменность 7 или 8 тактов, но всё равно, чтобы интервал неизменности увеличивался с числом бит кода.
Ну и при этом нужно, чтобы свойство кода Грея оставалось: в каждом такте меняется только один бит.

Тогда: имея такой код, я получу тактовую частоту изменения сигнала по каждой линии шины данных в несколько раз (пусть в N) ниже исходной тактовой (в обычном коде Грея - всего в 2 раза, что меня не устраивает). В таком случае я смогу защёлкивать значения счётчика на частоте, в N раз меньшей тактовой частоты самого счётчика.

Согласны?

Спасибо, судя по Вашему примеру - то, что мне нужно.
... правда я пример понял, а как это образуется, какими формулами описывается и какие свойства (правда ли на всём диапазоне счёта будет изменяться не более 1 цифры за раз, правда ли частота повторения каждого разряда во всём диапазоне счёта ниже в несколько раз тактовой частоты исходного счётчика) у такого кода - не понял. Не разжуёте немножко теорию?


Видимо, не совсем так. В двоичной системе такое тоже возможно, как показал уважаемый Oldring в этом сообщении.

Мне кажется, вы переусложняете. Защелкиваете вы на 30 мегагерцах, но все триггера быстрые и окно неопределенности у каждого отногсительно 30-МГц фронта небольшое. А все выходы счетчиков изменяются с некоторым достаточно фиксированным разбросом относительно общего фронта 100 МГц клока. Поэтому Вам нужно всего-лишь как-то обконстрейнить счетчики и защелки в доменах таким образом, чтобы суммарный разброс времен в различных линиях между доменами был меньше такта счета, т. е. 10 нс, минус окно триггеров. Как обконстрейнить - навскидку не скажу, но наверняка это возможно и не очень сложно.

Точно! Спасибо за подсказку, я сразу про сдвиговый регистр не догадался.

Да, с обычным периодом 2^N. Сдвигового регистра мне было бы мало, точнее он бы отожрал слишком много ресурсов в ПЛИС.

У меня N - большое число, может больше 10. Вообще значения точного времени передаются по 64 бита, но, возможно, я такие большие разрядности использовать не стану, обойдусь меньшими. Так что, наверное, подбирать последовательность будет затруднительно. К тому же кодек по произвольной последовательности будет весьма сложен в реализации и также отожрёт много ресурсов ПЛИС (по сравнению, например, с кодеком Грея).

Да, Вы правы, я усложнил свою задачу искусственно. Но это лишь потому, что появился спортивный интерес найти решение для общего случая, а не для частного случая соотношения частот, такого, как у меня: 100 МГц и 30 МГц.
В своём случае у меня такая мысль (если не придумаю ничего интереснее, навроде равномерного кода Грея): расположить рядом (чтобы длина связей была не большая) со счётчиком 100 МГц регистр, в который производить запись значений счётчика по сигналу, пришедшему из модуля на другом конце ПЛИС (в котором есть только 30 МГц) и пропущенному через цепь подавления метастабильности (2 D-триггера последовательно). Но такое решение не очень хорошее, т.к. потребителей значений времени много, в разных концах ПЛИС, и на каждый потребуется вводить такой регистр с цепью подавления метастабильности.

Вот констрейнить и не хотелось бы, т.к. при переходе на другую плиску это всё может не сработать. Хочется получить идеальное решение, которое бы работало само по себе, без констрейнтов.

Ещё раз перечитал Ваше сообщение, и пришла такая идея:
А что, если реализовать необходимую мне задачу путём смешивания свдигового регистра и кода Грея? Под младшие биты используется сдвиговый регистр, под старшие - код Грея в обычной форме. Правда, тут получится, что 2 бита могут измениться одновременно: один в части кода Грея, один в сдвиговой части. А это плохо... Или в данном случае это нестрашно? Что-то не могу сообразить сразу навскидку.
Идея расчёта следующая. Предположим, что нам нужно принимать изменяющиеся данные на частоте в N раз меньше частоты изменяющихся данных. Учитываем, что код Грея "понижает" частоту изменения в 2 раза. Таким образом, нам нужно получить оставшееся понижение на сдвиговом регистре, т.е. понижение в N/2 раз. Из приведённой выше цитаты получается, что при неизменности N/2 период счёта равен N. А число разрядов сдвигового регистра - log2(N).
Да... всё красиво, только надо получить изменение не более 1 разряда в 1 такт...
Или не годится вообще такая идея?

"Идеальное решение"?
IMHO при переходе на ПЛИС другого производителя может посыпаться много чего ещё. Идеала не существет.
Тем более, когда дело касается тайминга и метастабильностей, всё очень технологически зависимо.

Ну как минимум я хочу к этому приблизиться, насколько возможно и не требует уж очень из кожи вылезать. А в данном случае, я чувствую, что решение есть.
А про посыпаться - не соглашусь с Вами. То, что написано на том же Verilog'e, без применения FPGA-specific примитивов, будет работать на любой плисине. Если, конечно, времена допустимые. Но, если у меня все цепи работают на 30 МГц и я хочу добавить ещё одну цепь, которая тоже способна работать на 30 МГц, то с её работой не будет сложностей, если остальные цепи на 30 МГц работают без проблем.
Метастабильность подавляется на любой плисине примерно одинаково: 2 D-триггера.