On 06/12/2023 14:41, Michael S wrote:
> On Wed, 6 Dec 2023 13:06:29 +0100
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 06/12/2023 11:30, Michael S wrote:
>>> Bit sequences with bounded number of continuous '1' bits are useful
>>> for serialization of packetized data.
>>>
>>> For example, if we have a way of converting arbitrary n-bit words to
>>> unique (n+1)-bit extended words with at most L continuous leading
>>> '1' bits, at most T continuous trailing '1' bits and at most M=L+T
>>> continuous inner '1' bits then we can transfer multi-word packets
>>> starting with a header consisting of M+1 '1' bits followed by a
>>> single '0' bit and then by desired number of extended words. Any
>>> gaps between packets are filled with '1' bits.
>>> Receiver can easily synchronize itself to incoming packets and will
>>> quickly and robustly recovers after media errors.
>>> Such conversions have are other application as well. They always
>>> have.
>>>
>>> For me, a case of n=16 (16-bit words, 17-bit extended words) is of
>>> particular practical interest.
>>>
>>> Brute force counting proves that both for (L=1,T=3) and for
>>> (L=2,T=2) there exist more than 2**16 extended words with desired
>>> properties. For those interested, 76735 and 83665 extended words,
>>> respectively. So, desired 16b-to-17b conversions certainly exist
>>> for M=4. The problem is that I know of no simple "algorithmic" way
>>> of implementing such conversion short of using big look-up tables.
>>> Neither in software nor in simple compact hardware.
>>> That is in strong contrast to case of M=5 (both L=1,T=4 and L=2,T=3)
>>> where I know many such algorithms.
>>>
>>> Any ideas?
>>> May be, somebody had seen such methods in patents, preferably old
>>> and outdated?
>>> Or, better, in books or articles?
>>>
>>>
>>
>> Usually the interest is in limiting length of repeats at any point in
>> the data, not just the start and end. After all, it's not going to
>> help anyone if the start and end of the word are limited to no more
>> than 2 consecutive ones if you have a run of 10 ones in the middle of
>> the word.
>
> Please read again my original post. It's all covered.

Not as far as I can see. Maybe I have misunderstood you, or maybe you
have not understood me. Correct me if I am wrong below.

For L = 2, T = 2 (as an example), your coding would not allow

1100 1110 0101 1011 1

because it ends in 3 ones. (The spaces are just to make it easier to
read.) Your aim is to avoid the join of two packets having more than 4
ones in a row, so that if the receive sees 5 or more ones in a row, it
knows it is an inter-packet idle period.

But you /would/ allow :

1000 1111 1111 1000 1

This has no more than 1 leading or trailing one. But it has 8 ones in a
row. A receiver that is trying to synchronise would see a run of 8 ones
and interpret it as an inter-packet idle gap.

Additionally, how is the receiver supposed to identify the number of
ones at the start of a packet, after a gap? If it sees a sequence of 10
ones, then a zero (and then other values), how does it know if the
packet is starting with 0, 10, or 110 ?

Synchronisation for the start of a frame in communication is always done
with specific patterns containing at least one transition. For example,
with good-old-fashioned UART communication, break (inter-character
pauses) are a string of at least 10 ones, and the start of a character
frame is always a zero with the line going from high to low (either
after a break, or after the previous character's stop bit).

>
>>
>> It is also common to want to combine other encoding features at the
>> same time. Limiting the lengths of both zeros and ones means you
>> have transitions, which are needed for clock recovery and
>> synchronisation. For many transmissions, approximately 0 DC balance
>> is highly desirable. And you may also want forward error correction
>> or at least error detection.
>>
>
> In my case of interest the bits are encoded as NRZI so mere presence of
> '1' bits in headers and gaps guarantees that there are at least M
> transitions per packet.

OK, but you still have to make sure there are a suitable minimum number
of ones per frame. As it stands, a run of 17 zeros would fit your
requirements.

> It is sufficient for clock phase recovery
> at receiver (a.k.a Data Phase Alignment). Clock frequency recovery is
> not necessary, because clocks at both sides of the link are derived from
> the same source.

Fair enough. It is convenient when you have that!

> Anyway, when somewhat higher density of transitions is desirable, say,
> one transition (i.e. logical 1) per 25 or 30 bits, it's absolutely
> trivial to add at no additional coding cost since 76735 is sufficiently
> large than 65736.

Certainly you can make sure you have enough ones in the packet. (I
would not say it is "trivial" until you have found a simple algorithm
for coding and decoding to match your requirements - but it is unlikely
to make the problem any harder.)

>
> DC balance is not required in my case. When DC balance is required at
> all, the balance requirements tend to be rather strict. Weak balance is
> rarely of interest.

Weak balance - a statistical or probabilistic balance - is certainly of
interest in some systems. PCIe communication, for instance, maintains
an approximate balance by using a scrambler. Some DC "leakage" through
the terminators is enough to deal with the remainder, if I have
understood things correctly.

Other systems use active DC balance tracking to keep a stricter control,
and transmit different encodings to minimise the DC imbalance. But even
then, it is never perfect - no line drivers are equally strong for high
and low drives, and there are always differences in the latencies for
high and low transitions. Even with an ideal 50% duty cycle coming in,
there will be a small DC bias that must be leaked away. So DC balancing
in the encoding is /always/ weak, if you look closely enough.

> Typically disparity should be bounded to few
> percents over rather short intervals of few dozens of bit times. Or
> better. In order to achieve that you need rather higher coding rates
> than 17/16 or rather longer coding blocks than 16 bits. Or sometimes
> both. In other words, you have to play completely different game.
>
>> Maybe you have some specialised use in mind?
>>
>
> I do have a specialized use in mind, but for my specialized use the
> schemes that limit the number of continuous '1' bits to 4 are not
> necessary. Limit of 5 is perfectly o.k. and as I mentioned in original
> post, it's easy. In fact, if 5 was not so easy, from practical
> perspective I would be satisfied with significantly higher limit, like 7
> or 8.
>
> The question about bound of 4 is more of theoretical than of
> practical interest. Yesterday it surprised me to find out that such
> codes exists not just for 16b-to-17b, but for much longer words as
> well, up to 30b-to-31b. But there is a big difference between knowing
> that the code exists and finding a way to implement it in
> environment with limited resources.
>
>> Otherwise, these links might be of interest to you, on related ideas :
>>
>> <https://en.wikipedia.org/wiki/64b/66b_encoding>
>> <https://en.wikipedia.org/wiki/8b/10b_encoding>
>> <https://en.wikipedia.org/wiki/Bit_stuffing>
>>
>>
>
> Don't you know me long enough to guess that I had read that much and
> more?
>

I try to answer questions as I see them, rather than attempting to keep
track of what everyone knows.

When I see a post that looks like someone is trying to invent a new
technique in an existing field, and their ideas are noticeably different
from standard solutions, there are various possible explanations. One
is that they have a very niche use-case so the standard ideas don't
suit. Another is that they have come up with something truly original
and exciting. Most common, however, is that they don't know much about
the field and are not very aware of existing methods, and are currently
just playing about with ideas for solutions. Option 3 is the first
assumption until demonstrated otherwise. It looks like option 1 applies
to you here.

I can't say that I really understand why you have the requirements you
are asking for here - they don't make sense to me. Obviously I don't
have a full view of your system, but I cannot currently imagine a system
for which your requirements would be the best way to solve the problem.