Convolutional Codes that guarantee zero AC content

Are there convolutional codes that guarantee an encoded signal with equal 
numbers of zeros and ones?  Are they useful?

I'm thinking of a convolutional equivalent to the 8b10b block code used 
in Ethernet.

And in case you're wondering -- I'm mostly just curious.

Tanks.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

On 3/27/2013 12:38 PM, Tim Wescott wrote:

> Are there convolutional codes that guarantee an encoded signal with equal
> numbers of zeros and ones?  Are they useful?

In the class of binary, linear, non-trivial codes, none.

VLV

On Wed, 27 Mar 2013 12:38:13 -0500, Tim Wescott <tim@seemywebsite.com>
wrote:

>Are there convolutional codes that guarantee an encoded signal with equal 
>numbers of zeros and ones?  Are they useful?
>
>I'm thinking of a convolutional equivalent to the 8b10b block code used 
>in Ethernet.
>
>And in case you're wondering -- I'm mostly just curious.
>
>Tanks.

Usually DC balance, if needed, is done separately.   The all-ones
sequence and the all-zeroes sequence are both valid codes for
convolutional codes, so they don't do DC balance on their own.

In most non-optical comm systems a scrambler is used to maintain
entropy, and that essentially does the job of maintaining a reasonable
DC balance.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

Tim Wescott <tim@seemywebsite.com> wrote:
> Are there convolutional codes that guarantee an encoded signal with equal 
> numbers of zeros and ones?  Are they useful?

Probably, but you probably lose too much to use them.
 
> I'm thinking of a convolutional equivalent to the 8b10b block 
> code used in Ethernet.

Well, ethernet has to go through a transformer to get the common
mode signal low enough. 

As well as I remember the ethernet codes, the code words have
either an equal number of ones and zeros, or two more or less.

Well, first I recommend "Gigabit Ethernet" by Rich Seifert,
who designed much of the standard.

With an even number of bits, the difference has to be even.

The requirements for the 8B10B code are:

  1) Generate no more than four consecutive ones or zeros.
  2) Have the 10 bits comprise either 5 ones/5 zeros, 
     six ones/four zeros, or four ones/six zeros.

Each 8B codes to either one or a pair of complementary
codes with 5 ones/5 zeros code point, or a six ones/four 
zeros and four ones/six zeros pair. There are some code 
points left over for other signaling functions.

The transmitter then keeps track of the running disparity, 
and chooses the code point appropriately. Also, the running
disparity is updated as needed, such that it is either + or -.

Among other things, the book mentioned above includes the whole
code table for 8B10B gigabit ethernet.
 
> And in case you're wondering -- I'm mostly just curious.

and a quote from the book"

  "Cole's Law: Network standards are like sausages: If you intend
   to use them, you really don't want to see how they are made."

(Attributed to Gerald Cole from UCLA, not to a salad made
from cabbage.)

-- glen

Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
> On Wed, 27 Mar 2013 12:38:13 -0500, Tim Wescott <tim@seemywebsite.com>
> wrote:
 
>>Are there convolutional codes that guarantee an encoded signal with 
>> equal numbers of zeros and ones?  Are they useful?

>>I'm thinking of a convolutional equivalent to the 8b10b block code used 
>>in Ethernet.

>>And in case you're wondering -- I'm mostly just curious.
 
> Usually DC balance, if needed, is done separately.   The all-ones
> sequence and the all-zeroes sequence are both valid codes for
> convolutional codes, so they don't do DC balance on their own.

I suppose I should have mentioned that 8B10B for ethernet is not a 
convolutional code. Its purpose is to get the bits through the wire
and allow them to be extracted at the other end. The assumption is
that there is enough signal, and a CRC is done to detect noise
that changes the bits.
 
> In most non-optical comm systems a scrambler is used to maintain
> entropy, and that essentially does the job of maintaining a reasonable
> DC balance.

I suppose, but the 8B10B code is specifically designed to maintain DC
balance, at least enough to get through transformers, and not to have
too many consecutive zeros or ones, such that the receiver can extract
the bits.

By the way, there is comp.dcom.protocols.ethernet.

-- glen

On Wednesday, March 27, 2013 10:38:13 AM UTC-7, Tim Wescott wrote:
> Are there convolutional codes that guarantee an encoded signal with equal 
> numbers of zeros and ones?  Are they useful?
> 
> I'm thinking of a convolutional equivalent to the 8b10b block code used 
> in Ethernet.

Error correcting codes and dc-balanced codes are usually not designed together. Ie 8b10b coding has no error correction capability by itself. 
Coding usually includes a scrambler which generates uniformly distributed (iid) data so it is somewhat dc-balanced but not with the strict requirement that 8b10b has. Codes similar to 8b10b have too high an overhead and they are being abandoned by less strictly dc-balanced codes these days.
By the way, a scrambler is no guarantee that the resulting bitstream will be anything close to dc-balanced. 100B-TX has a design bug where it's possible to transmit a certain packet aligned with the scrambler state so that there is a huge dc wander generated which was fatal to most initial receivers. Someone from Motorola reverse-engineered the scrambler and found the packet and it still in the phy verification suite so that all phys can receive and tolerate this packet.

On Wed, 27 Mar 2013 14:23:40 -0700, muzaffer.kal wrote:

> On Wednesday, March 27, 2013 10:38:13 AM UTC-7, Tim Wescott wrote:
>> Are there convolutional codes that guarantee an encoded signal with
>> equal numbers of zeros and ones?  Are they useful?
>> 
>> I'm thinking of a convolutional equivalent to the 8b10b block code used
>> in Ethernet.
> 
> Error correcting codes and dc-balanced codes are usually not designed
> together. Ie 8b10b coding has no error correction capability by itself.
> Coding usually includes a scrambler which generates uniformly
> distributed (iid) data so it is somewhat dc-balanced but not with the
> strict requirement that 8b10b has. Codes similar to 8b10b have too high
> an overhead and they are being abandoned by less strictly dc-balanced
> codes these days. By the way, a scrambler is no guarantee that the
> resulting bitstream will be anything close to dc-balanced. 100B-TX has a
> design bug where it's possible to transmit a certain packet aligned with
> the scrambler state so that there is a huge dc wander generated which
> was fatal to most initial receivers. Someone from Motorola
> reverse-engineered the scrambler and found the packet and it still in
> the phy verification suite so that all phys can receive and tolerate
> this packet.

I had been under the impression that one could do some limited FEC with 
8b10b.  Damn.

I have a pretty strict limit on the consecutive ones and zeros (four is 
long but barely acceptable), a need for FEC, and the fewer raw bits I can 
waste on coding, the better.

(And no, it's not Ethernet.  It's really oddball.  And I don't know how 
close the customer wants to keep their cards to their chest, so I can't 
just describe it all in detail).

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

On 27 Mar., 18:38, Tim Wescott <t...@seemywebsite.com> wrote:
> Are there convolutional codes that guarantee an encoded signal with equal
> numbers of zeros and ones? &#4294967295;Are they useful?
>
> I'm thinking of a convolutional equivalent to the 8b10b block code used
> in Ethernet.
>
> And in case you're wondering -- I'm mostly just curious.
>
> Tanks.
>

maybe something in this:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.3386&rep=rep1&type=pdf

-Lasse

On Wed, 27 Mar 2013 20:28:24 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>Tim Wescott <tim@seemywebsite.com> wrote:
>> Are there convolutional codes that guarantee an encoded signal with equal 
>> numbers of zeros and ones?  Are they useful?
>
>Probably, but you probably lose too much to use them.
> 
>> I'm thinking of a convolutional equivalent to the 8b10b block 
>> code used in Ethernet.
>
>Well, ethernet has to go through a transformer to get the common
>mode signal low enough. 
>
>As well as I remember the ethernet codes, the code words have
>either an equal number of ones and zeros, or two more or less.
>
>Well, first I recommend "Gigabit Ethernet" by Rich Seifert,
>who designed much of the standard.
>
>With an even number of bits, the difference has to be even.
>
>The requirements for the 8B10B code are:
>
>  1) Generate no more than four consecutive ones or zeros.
>  2) Have the 10 bits comprise either 5 ones/5 zeros, 
>     six ones/four zeros, or four ones/six zeros.
>
>Each 8B codes to either one or a pair of complementary
>codes with 5 ones/5 zeros code point, or a six ones/four 
>zeros and four ones/six zeros pair. There are some code 
>points left over for other signaling functions.
>
>The transmitter then keeps track of the running disparity, 
>and chooses the code point appropriately. Also, the running
>disparity is updated as needed, such that it is either + or -.
>
>Among other things, the book mentioned above includes the whole
>code table for 8B10B gigabit ethernet.
> 
>> And in case you're wondering -- I'm mostly just curious.
>
>and a quote from the book"
>
>  "Cole's Law: Network standards are like sausages: If you intend
>   to use them, you really don't want to see how they are made."
>
>(Attributed to Gerald Cole from UCLA, not to a salad made
>from cabbage.)
>
>-- glen

Decades ago I heard it quoted as:

Cole's Law:  Anything that can possibly go wrong with cabbage, will go
wrong.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

On 3/27/2013 5:09 PM, Tim Wescott wrote:
> On Wed, 27 Mar 2013 14:23:40 -0700, muzaffer.kal wrote:
>
>> On Wednesday, March 27, 2013 10:38:13 AM UTC-7, Tim Wescott wrote:
>>> Are there convolutional codes that guarantee an encoded signal with
>>> equal numbers of zeros and ones?  Are they useful?
>>>
>>> I'm thinking of a convolutional equivalent to the 8b10b block code used
>>> in Ethernet.
>
> I had been under the impression that one could do some limited FEC with
> 8b10b.  Damn.

The 8b10b is not code but state machine: the encoding of the current 
group depends on history. And it is DC free only in the long run.

For DC free coding with low overhead, I've coded 6 useful bits into 8 
channel bits. There are 68 combinations of 8 bits that are exactly zero 
DC. It maps nicely into 6 bits of data and 4 special combinations to use 
as markers. The coding provides error detection/correction capabilities 
as well.

Vladimir Vassilevsky
DSP and Mixed Signal Designs
www.abvolt.com