bit stuffing in serial protocols

On 01.04.2016 23:01, Eric Jacobsen wrote:
(snip)

> I was trying to sort out how to map the constellation, since there
> isn't a power-of-two number of points.   Even mapping across multiple
> symbols isn't straightforward, since 3 doesn't go into 2^N evenly for
> practical N.

Some simple choices to map binary to ternary words (with some ternary 
words left unused) could be
2^11 into 3^7 (losing 0.3 dB), or
2^19 into 3^12 (losing 0.06 dB), or
2^84 into 3^53 (losing 0.009 dB), or
2^659 into 3^359 (losing 0.0046 dB), or
2^1054 into 3^665 (losing 0.0002 dB).
Mapping could be done by simple division. But that would have bad 
implications for error propagation, i.e. a single error in a 3-tuple 
would (on average) corrupt half of a binary word.

[OT] That was seemingly a hot topic back in 1960s. E.g., in a 1967 
article by Franaszek there's a scheme to map 2^4 into 3^3 words:
http://sci-hub.io/10.1002/j.1538-7305.1968.tb00034.x

Perhaps a more smart option would be to let the code do the mapping, 
too. E.g., a convolutional code that outputs ternary digits while 
receiving binary digits. Such a code was proposed in 2002 by Nakamura 
and Torii in their article "Ternary phase shift keying and its performance":
http://sci-hub.io/10.1109/WPMC.2002.1088386

That article seems to be the most comprehensive study of TPSK at the 
moment, and the authors have only considered Viterbi decoding of their code.

It would be interesting to see BER-SNR curves for turbo (or LPDC) codes 
with TPSK modulation. Seemingly it hasn't been reported yet.

Evgeny


>
> It might make a really cool way to do an R = 1/3 code, though.  ;)
>
>
> Eric Jacobsen
> Anchor Hill Communications
> http://www.anchorhill.com
>

On 02.04.2016 12:21, Evgeny Filatov wrote:
> On 01.04.2016 23:01, Eric Jacobsen wrote:
> (snip)
>
>> I was trying to sort out how to map the constellation, since there
>> isn't a power-of-two number of points.   Even mapping across multiple
>> symbols isn't straightforward, since 3 doesn't go into 2^N evenly for
>> practical N.
>
> Some simple choices to map binary to ternary words (with some ternary
> words left unused) could be
> 2^11 into 3^7 (losing 0.3 dB), or
> 2^19 into 3^12 (losing 0.06 dB), or
> 2^84 into 3^53 (losing 0.009 dB), or
> 2^659 into 3^359 (losing 0.0046 dB), or
> 2^1054 into 3^665 (losing 0.0002 dB).
> Mapping could be done by simple division. But that would have bad
> implications for error propagation, i.e. a single error in a 3-tuple
> would (on average) corrupt half of a binary word.
>
> [OT] That was seemingly a hot topic back in 1960s. E.g., in a 1967
> article by Franaszek there's a scheme to map 2^4 into 3^3 words:
> http://sci-hub.io/10.1002/j.1538-7305.1968.tb00034.x
>
> Perhaps a more smart option would be to let the code do the mapping,
> too. E.g., a convolutional code that outputs ternary digits while
> receiving binary digits. Such a code was proposed in 2002 by Nakamura
> and Torii in their article "Ternary phase shift keying and its
> performance":
> http://sci-hub.io/10.1109/WPMC.2002.1088386
>
> That article seems to be the most comprehensive study of TPSK at the
> moment, and the authors have only considered Viterbi decoding of their
> code.
>
> It would be interesting to see BER-SNR curves for turbo (or LPDC) codes
> with TPSK modulation. Seemingly it hasn't been reported yet.
>
> Evgeny
>

The last claim is not correct. Turbo codes for TPSK (including BITO, 
i.e. binary-input ternary-output) were reported in 2013 ("Non-Binary 
Turbo Coded Spatial Modulation" by Hashimoto, Ishii, Ogose). That comes 
with BER-SNR curves. And they have shown than the option to include 
mapping within the encoder (i.e. binary-input ternary-output) is 
superior to the option to separate mapping and coding.

However, they have only considered a single code rate, i.e. 2/3. But the 
real strength of turbo codes is in the region of lower code rates. So, 
it looks like there are still open questions in that field.

Evgeny

On Sat, 02 Apr 2016 12:21:43 +0300, Evgeny Filatov wrote:

> On 01.04.2016 23:01, Eric Jacobsen wrote:
> (snip)
> 
>> I was trying to sort out how to map the constellation, since there
>> isn't a power-of-two number of points.   Even mapping across multiple
>> symbols isn't straightforward, since 3 doesn't go into 2^N evenly for
>> practical N.
> 
> Some simple choices to map binary to ternary words (with some ternary
> words left unused) could be 2^11 into 3^7 (losing 0.3 dB), or 2^19 into
> 3^12 (losing 0.06 dB), or 2^84 into 3^53 (losing 0.009 dB), or 2^659
> into 3^359 (losing 0.0046 dB), or 2^1054 into 3^665 (losing 0.0002 dB).
> Mapping could be done by simple division. But that would have bad
> implications for error propagation, i.e. a single error in a 3-tuple
> would (on average) corrupt half of a binary word.


4B3T, which maps 4 bits into 3 ternary symbols, was (still is?) used for 
basic rate ISDN (144kb/s useful data rate on phone lines) in Europe.
This is baseband signalling, and some of the redundancy was used to 
create a null at DC, and some was used for framing.

2B1Q (2 bits mapping to 4 levels) was (is?) used for basic rate ISDN 
outside Europe.
There was no null at DC.

Basic rate ISDN is transformer coupled.  I vaguely recall designing a 
transformer for this a long time ago, and the design was much more 
difficult for 2B1Q because of the low frequency response needed.

2B1Q gave better reach because of the lower symbol rate though.

Regards,
Allan

On 02.04.2016 14:18, Allan Herriman wrote:
> On Sat, 02 Apr 2016 12:21:43 +0300, Evgeny Filatov wrote:
>
>> On 01.04.2016 23:01, Eric Jacobsen wrote:
>> (snip)
>>
>>> I was trying to sort out how to map the constellation, since there
>>> isn't a power-of-two number of points.   Even mapping across multiple
>>> symbols isn't straightforward, since 3 doesn't go into 2^N evenly for
>>> practical N.
>>
>> Some simple choices to map binary to ternary words (with some ternary
>> words left unused) could be 2^11 into 3^7 (losing 0.3 dB), or 2^19 into
>> 3^12 (losing 0.06 dB), or 2^84 into 3^53 (losing 0.009 dB), or 2^659
>> into 3^359 (losing 0.0046 dB), or 2^1054 into 3^665 (losing 0.0002 dB).
>> Mapping could be done by simple division. But that would have bad
>> implications for error propagation, i.e. a single error in a 3-tuple
>> would (on average) corrupt half of a binary word.
>
>
> 4B3T, which maps 4 bits into 3 ternary symbols, was (still is?) used for
> basic rate ISDN (144kb/s useful data rate on phone lines) in Europe.
> This is baseband signalling, and some of the redundancy was used to
> create a null at DC, and some was used for framing.
>
> 2B1Q (2 bits mapping to 4 levels) was (is?) used for basic rate ISDN
> outside Europe.
> There was no null at DC.
>
> Basic rate ISDN is transformer coupled.  I vaguely recall designing a
> transformer for this a long time ago, and the design was much more
> difficult for 2B1Q because of the low frequency response needed.
>
> 2B1Q gave better reach because of the lower symbol rate though.
>
> Regards,
> Allan
>

Cool! I didn't know that.

Regards,
Evgeny

Evgeny Filatov  <filatov.ev@mipt.ru> wrote:

>The last claim is not correct. Turbo codes for TPSK (including BITO, 
>i.e. binary-input ternary-output) were reported in 2013 ("Non-Binary 
>Turbo Coded Spatial Modulation" by Hashimoto, Ishii, Ogose). That comes 
>with BER-SNR curves. And they have shown than the option to include 
>mapping within the encoder (i.e. binary-input ternary-output) is 
>superior to the option to separate mapping and coding.
>
>However, they have only considered a single code rate, i.e. 2/3. But the 
>real strength of turbo codes is in the region of lower code rates. So, 
>it looks like there are still open questions in that field.

I disagree that the "real strength of turbo codes is ... lower code
rates".  I have found them to be equally close to capacity for
rates up to 0.9, and relatively simple to construct for high rates
using puncturing.

Steve

On 02.04.2016 16:50, Steve Pope wrote:
> Evgeny Filatov  <filatov.ev@mipt.ru> wrote:
>
>> The last claim is not correct. Turbo codes for TPSK (including BITO,
>> i.e. binary-input ternary-output) were reported in 2013 ("Non-Binary
>> Turbo Coded Spatial Modulation" by Hashimoto, Ishii, Ogose). That comes
>> with BER-SNR curves. And they have shown than the option to include
>> mapping within the encoder (i.e. binary-input ternary-output) is
>> superior to the option to separate mapping and coding.
>>
>> However, they have only considered a single code rate, i.e. 2/3. But the
>> real strength of turbo codes is in the region of lower code rates. So,
>> it looks like there are still open questions in that field.
>
> I disagree that the "real strength of turbo codes is ... lower code
> rates".  I have found them to be equally close to capacity for
> rates up to 0.9, and relatively simple to construct for high rates
> using puncturing.
>
> Steve
>

Thanks for clearing that out. So, that were my amateur ideas. :)

Evgeny

On 02.04.2016 18:25, Evgeny Filatov wrote:
> On 02.04.2016 16:50, Steve Pope wrote:
>> Evgeny Filatov  <filatov.ev@mipt.ru> wrote:
>>
>>> The last claim is not correct. Turbo codes for TPSK (including BITO,
>>> i.e. binary-input ternary-output) were reported in 2013 ("Non-Binary
>>> Turbo Coded Spatial Modulation" by Hashimoto, Ishii, Ogose). That comes
>>> with BER-SNR curves. And they have shown than the option to include
>>> mapping within the encoder (i.e. binary-input ternary-output) is
>>> superior to the option to separate mapping and coding.
>>>
>>> However, they have only considered a single code rate, i.e. 2/3. But the
>>> real strength of turbo codes is in the region of lower code rates. So,
>>> it looks like there are still open questions in that field.
>>
>> I disagree that the "real strength of turbo codes is ... lower code
>> rates".  I have found them to be equally close to capacity for
>> rates up to 0.9, and relatively simple to construct for high rates
>> using puncturing.
>>
>> Steve
>>
>
> Thanks for clearing that out. So, that were my amateur ideas. :)
>
> Evgeny

Also, I'm not sure if they got the definition of "rate" right:

http://sci-hub.io/10.1109/VTCFall.2013.6692304

They seem to believe the rate is the ratio of input to output SYMBOL 
rates (so they get r=2/3 in one case and r=1 in two others). Shouldn't 
the rate be the ratio of input to output BIT rates (so it would contain 
that pesky log2(3) factor)?

Evgeny

On 02.04.2016 6:30, robert bristow-johnson wrote:

(snip)

>>> That's PSK with a constellation consisting of 3 possible states.
>
> it's like an equilateral triangle constellation of symbols?

Right.

(snip)

 > must be an absolute copulating female canine to encode normal 
(binary) data (the way God meant it to be) into such an abomination. and 
back again.  sorry Evgeny, my kinda "beautifully natural" is not a Rube 
Goldberg machine.

If there were more English like that in technical lit, fiction would be 
redundant. :)

(snip)

> i can imagine this 3-state PSK thingie (essentially 3-QAM with an equilateral triangle constellation) to do *differential* binary coding.  so you wouldn't give a rat's ass which actual point you're at, the receiver only cares if the movement of the quadrature IF vector is clockwise or counter-clockwise.  that sorta makes sense to me.  could be *real* clean and simple.  like OQPSK, each movement of the IF vector corresponds to exactly one bit of data.

It's essential to understand that with differential modulations it's an 
okey event if the same position in a constellation is transmitted twice 
in a row.

Differential modulation doesn't mean that you must move anywhere each 
time you transmit a symbol (although that's a somewhat popular 
misconception). It only means you are transmitting the _difference_ 
between two succeeding original symbols you had. The same difference 
twice in a row is legit (like 0-1=1, then 1-0=1 in D-BPSK). If you make 
it forbidden in your system, perhaps you are losing capacity.

(snip)

> thanks Eric.  thanks Evgeny.
>
> r b-j
>

You are welcome, Robert.

Evgeny

On Sat, 02 Apr 2016 12:49:08 +0300, Evgeny Filatov
<filatov.ev@mipt.ru> wrote:

>On 02.04.2016 12:21, Evgeny Filatov wrote:
>> On 01.04.2016 23:01, Eric Jacobsen wrote:
>> (snip)
>>
>>> I was trying to sort out how to map the constellation, since there
>>> isn't a power-of-two number of points.   Even mapping across multiple
>>> symbols isn't straightforward, since 3 doesn't go into 2^N evenly for
>>> practical N.
>>
>> Some simple choices to map binary to ternary words (with some ternary
>> words left unused) could be
>> 2^11 into 3^7 (losing 0.3 dB), or
>> 2^19 into 3^12 (losing 0.06 dB), or
>> 2^84 into 3^53 (losing 0.009 dB), or
>> 2^659 into 3^359 (losing 0.0046 dB), or
>> 2^1054 into 3^665 (losing 0.0002 dB).
>> Mapping could be done by simple division. But that would have bad
>> implications for error propagation, i.e. a single error in a 3-tuple
>> would (on average) corrupt half of a binary word.
>>
>> [OT] That was seemingly a hot topic back in 1960s. E.g., in a 1967
>> article by Franaszek there's a scheme to map 2^4 into 3^3 words:
>> http://sci-hub.io/10.1002/j.1538-7305.1968.tb00034.x
>>
>> Perhaps a more smart option would be to let the code do the mapping,
>> too. E.g., a convolutional code that outputs ternary digits while
>> receiving binary digits. Such a code was proposed in 2002 by Nakamura
>> and Torii in their article "Ternary phase shift keying and its
>> performance":
>> http://sci-hub.io/10.1109/WPMC.2002.1088386
>>
>> That article seems to be the most comprehensive study of TPSK at the
>> moment, and the authors have only considered Viterbi decoding of their
>> code.
>>
>> It would be interesting to see BER-SNR curves for turbo (or LPDC) codes
>> with TPSK modulation. Seemingly it hasn't been reported yet.
>>
>> Evgeny
>>
>
>The last claim is not correct. Turbo codes for TPSK (including BITO, 
>i.e. binary-input ternary-output) were reported in 2013 ("Non-Binary 
>Turbo Coded Spatial Modulation" by Hashimoto, Ishii, Ogose). That comes 
>with BER-SNR curves. And they have shown than the option to include 
>mapping within the encoder (i.e. binary-input ternary-output) is 
>superior to the option to separate mapping and coding.

That's kind of what I was wondering above;  use an N/3 code rate to
map to the ternary symbols. 

>However, they have only considered a single code rate, i.e. 2/3. But the 
>real strength of turbo codes is in the region of lower code rates. So, 
>it looks like there are still open questions in that field.

As Steve already mentioned, capacity-approaching codes, like TCs and
LDPCs and TPCs, are good for getting close to channel capacity at
whatever code rate might be needed.   Low code rates only optimize
power efficiency, and bandwidth efficiency may be important as well.
If you care about both power and bandwidth efficiency, there's a sweet
spot in the capacity curves at around R = 7/8 or so.   Turbo Product
Codes, which are relatively simple to implement, can approach capacity
at those rates.

As usual, it just depends on what you want to do at the time.

 

---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

On 02 Apr 2016 11:18:27 GMT, Allan Herriman
<allanherriman@hotmail.com> wrote:

>On Sat, 02 Apr 2016 12:21:43 +0300, Evgeny Filatov wrote:
>
>> On 01.04.2016 23:01, Eric Jacobsen wrote:
>> (snip)
>> 
>>> I was trying to sort out how to map the constellation, since there
>>> isn't a power-of-two number of points.   Even mapping across multiple
>>> symbols isn't straightforward, since 3 doesn't go into 2^N evenly for
>>> practical N.
>> 
>> Some simple choices to map binary to ternary words (with some ternary
>> words left unused) could be 2^11 into 3^7 (losing 0.3 dB), or 2^19 into
>> 3^12 (losing 0.06 dB), or 2^84 into 3^53 (losing 0.009 dB), or 2^659
>> into 3^359 (losing 0.0046 dB), or 2^1054 into 3^665 (losing 0.0002 dB).
>> Mapping could be done by simple division. But that would have bad
>> implications for error propagation, i.e. a single error in a 3-tuple
>> would (on average) corrupt half of a binary word.
>
>
>4B3T, which maps 4 bits into 3 ternary symbols, was (still is?) used for 
>basic rate ISDN (144kb/s useful data rate on phone lines) in Europe.
>This is baseband signalling, and some of the redundancy was used to 
>create a null at DC, and some was used for framing.
>
>2B1Q (2 bits mapping to 4 levels) was (is?) used for basic rate ISDN 
>outside Europe.
>There was no null at DC.
>
>Basic rate ISDN is transformer coupled.  I vaguely recall designing a 
>transformer for this a long time ago, and the design was much more 
>difficult for 2B1Q because of the low frequency response needed.
>
>2B1Q gave better reach because of the lower symbol rate though.
>
>Regards,
>Allan

Aw, somebody actually built it as part of standard?   It's much less
interesting now.  ;)



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus