Really good book on coding

On 13.12.2016 12:55, Evgeny Filatov wrote:
> On 13.12.2016 4:14, eric.jacobsen@ieee.org wrote:
>>
>> Modulation and Coding Techniques in Wireless Communication, Krouk and
>> Semenov.    I visited Prof. Krouk and his lab in St. Petersburg a few
>> times for a previous employer.   This book is a good translation of
>> the original Russian text.   It is one of the few books that covers
>> convolutional coding that also talks about list decoders (briefly) and
>> sequential decoders.
>
> I'm afraid there was no "original Russian text". It's common for Russian
> authors to write a book in English, and then, when the stars align,
> maybe make a Russian translation. Frankly, it's not much of an
> impediment, because everybody seems to know English. It's true that I
> read English fiction several times slower than the same sort of
> literature in my native tongue. But with technical texts my reading
> speed is limited by something else, i.e. my ability to understand the math.
>
> Gene
>

Or, perhaps, it would be more correct to say "it's not uncommon".

For example, Prof. Krouk has published several books in the both 
languages, but it doesn't look like some are mere translations of 
others. Perhaps there's some kind of an overlap across his works, but no 
translations.

http://ictacademy.ru/node/78

Gene

On 13.12.2016 13:53, Evgeny Filatov wrote:
> On 13.12.2016 12:55, Evgeny Filatov wrote:
>> On 13.12.2016 4:14, eric.jacobsen@ieee.org wrote:
>>>
>>> Modulation and Coding Techniques in Wireless Communication, Krouk and
>>> Semenov.    I visited Prof. Krouk and his lab in St. Petersburg a few
>>> times for a previous employer.   This book is a good translation of
>>> the original Russian text.   It is one of the few books that covers
>>> convolutional coding that also talks about list decoders (briefly) and
>>> sequential decoders.
>>
>> I'm afraid there was no "original Russian text". It's common for Russian
>> authors to write a book in English, and then, when the stars align,
>> maybe make a Russian translation. Frankly, it's not much of an
>> impediment, because everybody seems to know English. It's true that I
>> read English fiction several times slower than the same sort of
>> literature in my native tongue. But with technical texts my reading
>> speed is limited by something else, i.e. my ability to understand the
>> math.
>>
>> Gene
>>
>
> Or, perhaps, it would be more correct to say "it's not uncommon".
>
> For example, Prof. Krouk has published several books in the both
> languages, but it doesn't look like some are mere translations of
> others. Perhaps there's some kind of an overlap across his works, but no
> translations.
>
> http://ictacademy.ru/node/78
>
> Gene
>

Apologies, this is the link:
http://ictacademy.ru/en/node/88

Gene

On Tue, 13 Dec 2016 06:37:14 +0000, Steve Pope wrote:

> Tim Wescott  <seemywebsite@myfooter.really> wrote:
> 
>>OK.  Here's the deal.  I'd wondered if this was the case, but because of
>>hardware constraints I have an underlying layer that naturally breaks
>>things down into multiple symbols.  The symbols aren't all equidistant
>>from each other, but they're not ordered in a way that would map to a
>>binary count.
>>
>>I can make soft decisions, and because the symbols aren't equidistant, a
>>small error results in a pair, or three or four, symbols being roughly
>>equally probable.
>>
>>As a for-instance, if the decision is equally divided between symbols #3
>>and #4 out of 16 possible values, then if I keep things at this level,
>>what would go into the decoder would be a soft decision that basically
>>says "maybe number three, maybe number four, but definitely not the
>>rest".
>>
>>However, if I were to turn each of my 16 symbols into a four-bit
>>sequence, then in the above case what would go into the decoder would be
>>"definitely zero, erase, erase, erase" -- in other words, by going to
>>binary my two possible values out of sixteen have turned into eight out
>>of sixteen.
>>
>>So intuitively, it seems that a decoder operating on GF(16) would be
>>better in this case.
>>
>>So -- you think that even in this case I should just use a binary code?
> 
> Well, you're certainly welcome to try using a code over GF(16)
> and theoretically, such a code might ultimately be the best performer.
> But, it might have other problems such as extremely long codewords being
> necessary, humungous complexity, etc.
> 
> Or you could use a binary code with interleaving and compute the MAP
> probability for each bit feeding the decoder (as opposed to some
> suboptimal soft-decision and/or erasure algorithm which is my sense of
> what you are above describing).
> 
> Once you have implemented or perhaps simulated the MAP algorithm you can
> see how much performance is lost by cheaper, more ad-hoc soft-decision
> algorithms.
> 
> You might also consider going to a binary code which is stronger than a
> binary convolutional code in the first place (one of the near-channel
> capacity codes such as LDPC) -- I think this is lower-hanging fruit then
> searching for a nonbinary code.
> 
> Steve

I've got a severe constraint on the amount of delay that I can add, so 
I'm not working in the realm of codes that come closest to the channel 
capacity -- rather, I'm working in the realm of codes that come closest 
to the sphere-packing limit for the amount of delay that I'm allowing 
myself.

It doesn't seem to be an area where a lot of work has been done.

-- 
www.wescottdesign.com

On Tue, 13 Dec 2016 13:56:01 +0300, Evgeny Filatov
<filatov.ev@mipt.ru> wrote:

>On 13.12.2016 13:53, Evgeny Filatov wrote:
>> On 13.12.2016 12:55, Evgeny Filatov wrote:
>>> On 13.12.2016 4:14, eric.jacobsen@ieee.org wrote:
>>>>
>>>> Modulation and Coding Techniques in Wireless Communication, Krouk and
>>>> Semenov.    I visited Prof. Krouk and his lab in St. Petersburg a few
>>>> times for a previous employer.   This book is a good translation of
>>>> the original Russian text.   It is one of the few books that covers
>>>> convolutional coding that also talks about list decoders (briefly) and
>>>> sequential decoders.
>>>
>>> I'm afraid there was no "original Russian text". It's common for Russian
>>> authors to write a book in English, and then, when the stars align,
>>> maybe make a Russian translation. Frankly, it's not much of an
>>> impediment, because everybody seems to know English. It's true that I
>>> read English fiction several times slower than the same sort of
>>> literature in my native tongue. But with technical texts my reading
>>> speed is limited by something else, i.e. my ability to understand the
>>> math.
>>>
>>> Gene
>>>
>>
>> Or, perhaps, it would be more correct to say "it's not uncommon".
>>
>> For example, Prof. Krouk has published several books in the both
>> languages, but it doesn't look like some are mere translations of
>> others. Perhaps there's some kind of an overlap across his works, but no
>> translations.
>>
>> http://ictacademy.ru/node/78
>>
>> Gene
>>
>
>Apologies, this is the link:
>http://ictacademy.ru/en/node/88

That's him!   He's a good dude, too.   I liked him a lot.

And thanks for the corrections on the texts.   He had given me a
signed copy of a Russian-language text that has a lot of familiar
graphs and diagrams and such in it, so I had made the erroneous
assumption that the text I cited was a translation,  I think the
Russian text I have may be on information theory, at least the last
word in the title appears to be "information".  I'm not very competent
at Russian other than being able to read words that happen to be
fairly cognitive to English, order beer, etc.

On Tue, 13 Dec 2016 12:41:14 -0600, Tim Wescott
<tim@seemywebsite.really> wrote:

>On Tue, 13 Dec 2016 06:37:14 +0000, Steve Pope wrote:
>
>> Tim Wescott  <seemywebsite@myfooter.really> wrote:
>> 
>>>OK.  Here's the deal.  I'd wondered if this was the case, but because of
>>>hardware constraints I have an underlying layer that naturally breaks
>>>things down into multiple symbols.  The symbols aren't all equidistant
>>>from each other, but they're not ordered in a way that would map to a
>>>binary count.
>>>
>>>I can make soft decisions, and because the symbols aren't equidistant, a
>>>small error results in a pair, or three or four, symbols being roughly
>>>equally probable.
>>>
>>>As a for-instance, if the decision is equally divided between symbols #3
>>>and #4 out of 16 possible values, then if I keep things at this level,
>>>what would go into the decoder would be a soft decision that basically
>>>says "maybe number three, maybe number four, but definitely not the
>>>rest".
>>>
>>>However, if I were to turn each of my 16 symbols into a four-bit
>>>sequence, then in the above case what would go into the decoder would be
>>>"definitely zero, erase, erase, erase" -- in other words, by going to
>>>binary my two possible values out of sixteen have turned into eight out
>>>of sixteen.
>>>
>>>So intuitively, it seems that a decoder operating on GF(16) would be
>>>better in this case.
>>>
>>>So -- you think that even in this case I should just use a binary code?
>> 
>> Well, you're certainly welcome to try using a code over GF(16)
>> and theoretically, such a code might ultimately be the best performer.
>> But, it might have other problems such as extremely long codewords being
>> necessary, humungous complexity, etc.
>> 
>> Or you could use a binary code with interleaving and compute the MAP
>> probability for each bit feeding the decoder (as opposed to some
>> suboptimal soft-decision and/or erasure algorithm which is my sense of
>> what you are above describing).
>> 
>> Once you have implemented or perhaps simulated the MAP algorithm you can
>> see how much performance is lost by cheaper, more ad-hoc soft-decision
>> algorithms.
>> 
>> You might also consider going to a binary code which is stronger than a
>> binary convolutional code in the first place (one of the near-channel
>> capacity codes such as LDPC) -- I think this is lower-hanging fruit then
>> searching for a nonbinary code.
>> 
>> Steve
>
>I've got a severe constraint on the amount of delay that I can add, so 
>I'm not working in the realm of codes that come closest to the channel 
>capacity -- rather, I'm working in the realm of codes that come closest 
>to the sphere-packing limit for the amount of delay that I'm allowing 
>myself.

I'm having difficulty visualizing what you're doing just based on your
description.   Having unequal-weighted inputs or soft-decision scaling
is perfectly okay with a binary code, and is typically done in
high-order modulations, anyway.   Bits with large spacing or small
soft regions may get away with not being coded at all, like in many
TCM or BICM schemes, if that applies to your system.

>It doesn't seem to be an area where a lot of work has been done.

I wouldn't assume that.   It may just have not been very useful and
wound up under a pile of dust somewhere.   There was kind of an
explosion in coding research for a decade or so after Turbo Codes came
on the scene, and I recall seeing a number of papers on coding for
oddball symbol spaces, but I wouldn't be able to point you to them any
more other than maybe just scour Trans on Information Theory or Trans
on Comm or Wireless Comm.   That doesn't seem to narrow it down much,
though.  ;)

Sphere-packing analysis and code design is pretty well known, but
whether any of the techniques apply to your particular application
might be tricky to find depending on how esoteric it really is.

On Tue, 13 Dec 2016 19:13:11 +0000, eric.jacobsen wrote:

> On Tue, 13 Dec 2016 12:41:14 -0600, Tim Wescott
> <tim@seemywebsite.really> wrote:
> 
>>On Tue, 13 Dec 2016 06:37:14 +0000, Steve Pope wrote:
>>
>>> Tim Wescott  <seemywebsite@myfooter.really> wrote:
>>> 
>>>>OK.  Here's the deal.  I'd wondered if this was the case, but because
>>>>of hardware constraints I have an underlying layer that naturally
>>>>breaks things down into multiple symbols.  The symbols aren't all
>>>>equidistant from each other, but they're not ordered in a way that
>>>>would map to a binary count.
>>>>
>>>>I can make soft decisions, and because the symbols aren't equidistant,
>>>>a small error results in a pair, or three or four, symbols being
>>>>roughly equally probable.
>>>>
>>>>As a for-instance, if the decision is equally divided between symbols
>>>>#3 and #4 out of 16 possible values, then if I keep things at this
>>>>level, what would go into the decoder would be a soft decision that
>>>>basically says "maybe number three, maybe number four, but definitely
>>>>not the rest".
>>>>
>>>>However, if I were to turn each of my 16 symbols into a four-bit
>>>>sequence, then in the above case what would go into the decoder would
>>>>be "definitely zero, erase, erase, erase" -- in other words, by going
>>>>to binary my two possible values out of sixteen have turned into eight
>>>>out of sixteen.
>>>>
>>>>So intuitively, it seems that a decoder operating on GF(16) would be
>>>>better in this case.
>>>>
>>>>So -- you think that even in this case I should just use a binary
>>>>code?
>>> 
>>> Well, you're certainly welcome to try using a code over GF(16)
>>> and theoretically, such a code might ultimately be the best performer.
>>> But, it might have other problems such as extremely long codewords
>>> being necessary, humungous complexity, etc.
>>> 
>>> Or you could use a binary code with interleaving and compute the MAP
>>> probability for each bit feeding the decoder (as opposed to some
>>> suboptimal soft-decision and/or erasure algorithm which is my sense of
>>> what you are above describing).
>>> 
>>> Once you have implemented or perhaps simulated the MAP algorithm you
>>> can see how much performance is lost by cheaper, more ad-hoc
>>> soft-decision algorithms.
>>> 
>>> You might also consider going to a binary code which is stronger than
>>> a binary convolutional code in the first place (one of the
>>> near-channel capacity codes such as LDPC) -- I think this is
>>> lower-hanging fruit then searching for a nonbinary code.
>>> 
>>> Steve
>>
>>I've got a severe constraint on the amount of delay that I can add, so
>>I'm not working in the realm of codes that come closest to the channel
>>capacity -- rather, I'm working in the realm of codes that come closest
>>to the sphere-packing limit for the amount of delay that I'm allowing
>>myself.
> 
> I'm having difficulty visualizing what you're doing just based on your
> description.  

Me: "I can increase your data rate by a factor of ten."

Customer: "OH COOL!!!"

Me: "But the delay from the measurement to the data becoming available is 
going to be as long as now."

Customer: "No, no, no.  Get the delay down as much as possible."

How's that?

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!

Tim Wescott  <tim@seemywebsite.really> wrote:

>I've got a severe constraint on the amount of delay that I can add, so 
>I'm not working in the realm of codes that come closest to the channel 
>capacity -- rather, I'm working in the realm of codes that come closest 
>to the sphere-packing limit for the amount of delay that I'm allowing 
>myself.

>It doesn't seem to be an area where a lot of work has been done.

For the general constraint of code performance vs. clock length
based on the sphere-packing limit, there is a paper by Fabrizio
Pollara that I have linked to here before, one result of which is
that for codeword lengths in the range of several dozen bits, conventional
BCC's are the best available.

I think this latency constraint makes it even less likely that you'll 
want to use a code over GF(16).  Codes over GF(2) outperform codes over
GF(N), N > 2, for the same codeword length -- so there'll have to
be something very serindipitous about how the transmitted symbols
map into code symbols.  It would have to outperform feeding the
MAP values into the binary decoder and there isn't a lot of room
to improve on that.

Steve

On Tue, 13 Dec 2016 13:29:06 -0600, Tim Wescott
<seemywebsite@myfooter.really> wrote:

>On Tue, 13 Dec 2016 19:13:11 +0000, eric.jacobsen wrote:
>
>> On Tue, 13 Dec 2016 12:41:14 -0600, Tim Wescott
>> <tim@seemywebsite.really> wrote:
>> 
>>>On Tue, 13 Dec 2016 06:37:14 +0000, Steve Pope wrote:
>>>
>>>> Tim Wescott  <seemywebsite@myfooter.really> wrote:
>>>> 
>>>>>OK.  Here's the deal.  I'd wondered if this was the case, but because
>>>>>of hardware constraints I have an underlying layer that naturally
>>>>>breaks things down into multiple symbols.  The symbols aren't all
>>>>>equidistant from each other, but they're not ordered in a way that
>>>>>would map to a binary count.
>>>>>
>>>>>I can make soft decisions, and because the symbols aren't equidistant,
>>>>>a small error results in a pair, or three or four, symbols being
>>>>>roughly equally probable.
>>>>>
>>>>>As a for-instance, if the decision is equally divided between symbols
>>>>>#3 and #4 out of 16 possible values, then if I keep things at this
>>>>>level, what would go into the decoder would be a soft decision that
>>>>>basically says "maybe number three, maybe number four, but definitely
>>>>>not the rest".
>>>>>
>>>>>However, if I were to turn each of my 16 symbols into a four-bit
>>>>>sequence, then in the above case what would go into the decoder would
>>>>>be "definitely zero, erase, erase, erase" -- in other words, by going
>>>>>to binary my two possible values out of sixteen have turned into eight
>>>>>out of sixteen.
>>>>>
>>>>>So intuitively, it seems that a decoder operating on GF(16) would be
>>>>>better in this case.
>>>>>
>>>>>So -- you think that even in this case I should just use a binary
>>>>>code?
>>>> 
>>>> Well, you're certainly welcome to try using a code over GF(16)
>>>> and theoretically, such a code might ultimately be the best performer.
>>>> But, it might have other problems such as extremely long codewords
>>>> being necessary, humungous complexity, etc.
>>>> 
>>>> Or you could use a binary code with interleaving and compute the MAP
>>>> probability for each bit feeding the decoder (as opposed to some
>>>> suboptimal soft-decision and/or erasure algorithm which is my sense of
>>>> what you are above describing).
>>>> 
>>>> Once you have implemented or perhaps simulated the MAP algorithm you
>>>> can see how much performance is lost by cheaper, more ad-hoc
>>>> soft-decision algorithms.
>>>> 
>>>> You might also consider going to a binary code which is stronger than
>>>> a binary convolutional code in the first place (one of the
>>>> near-channel capacity codes such as LDPC) -- I think this is
>>>> lower-hanging fruit then searching for a nonbinary code.
>>>> 
>>>> Steve
>>>
>>>I've got a severe constraint on the amount of delay that I can add, so
>>>I'm not working in the realm of codes that come closest to the channel
>>>capacity -- rather, I'm working in the realm of codes that come closest
>>>to the sphere-packing limit for the amount of delay that I'm allowing
>>>myself.
>> 
>> I'm having difficulty visualizing what you're doing just based on your
>> description.  
>
>Me: "I can increase your data rate by a factor of ten."
>
>Customer: "OH COOL!!!"
>
>Me: "But the delay from the measurement to the data becoming available is 
>going to be as long as now."
>
>Customer: "No, no, no.  Get the delay down as much as possible."
>
>How's that?

If you have a good ratio of processing bandwidth to bit rate could you
do a basic block code, like a Reed-Solomon?   That'd let you fit the
bits around where the code performance could be adjusted somewhat.
The gain might be comparable to a convolutional code and latency would
be potentially adjustable by processing resource availability,
starting at the end of the code block, though.  Sometimes that's not
an issue if there's a CRC or FCS or something, anyway.

On 13.12.2016 22:03, eric.jacobsen@ieee.org wrote:
> On Tue, 13 Dec 2016 13:56:01 +0300, Evgeny Filatov
> <filatov.ev@mipt.ru> wrote:

>
> That's him!   He's a good dude, too.   I liked him a lot.
>
> And thanks for the corrections on the texts.   He had given me a
> signed copy of a Russian-language text that has a lot of familiar
> graphs and diagrams and such in it, so I had made the erroneous
> assumption that the text I cited was a translation,  I think the
> Russian text I have may be on information theory, at least the last
> word in the title appears to be "information".  I'm not very competent
> at Russian other than being able to read words that happen to be
> fairly cognitive to English, order beer, etc.
>
>

Actually I don't know anything about the man or his works, so I couldn't 
correct you. You may be correct and it's a translation, just I couldn't 
find the original book. Or perhaps he has given you a manuscript. ;-)

Gene

On Tue, 13 Dec 2016 19:48:04 +0000, Steve Pope wrote:

> Tim Wescott  <tim@seemywebsite.really> wrote:
> 
>>I've got a severe constraint on the amount of delay that I can add, so
>>I'm not working in the realm of codes that come closest to the channel
>>capacity -- rather, I'm working in the realm of codes that come closest
>>to the sphere-packing limit for the amount of delay that I'm allowing
>>myself.
> 
>>It doesn't seem to be an area where a lot of work has been done.
> 
> For the general constraint of code performance vs. clock length based on
> the sphere-packing limit, there is a paper by Fabrizio Pollara that I
> have linked to here before, one result of which is that for codeword
> lengths in the range of several dozen bits, conventional BCC's are the
> best available.
> 
> I think this latency constraint makes it even less likely that you'll
> want to use a code over GF(16).  Codes over GF(2) outperform codes over
> GF(N), N > 2, for the same codeword length -- so there'll have to be
> something very serindipitous about how the transmitted symbols map into
> code symbols.  It would have to outperform feeding the MAP values into
> the binary decoder and there isn't a lot of room to improve on that.

Here is my confusion:

I am under the impression that the available decoder algorithms take MAP 
values on a per-bit basis, but the structure of my symbols is such that I 
cannot map my set of symbols to a collection of four bits such that a 
"short distance" symbol error reliably results in fewer bit errors.

I already gave this example, but for the mapping that I'm currently 
using, symbol #3 and symbol #4 are a short distance apart, so it would be 
entirely natural for a decoder at the symbol level to come up with an 
output that says that these two symbols are equally likely to have been 
transmitted, and any other symbol values are highly unlikely to have been 
transmitted.

If I were to take that and turn it into binary with likelihoods, it would 
say that bits 0, 1 and 2 are equally likely to be 0 or 1, and that bit 3 
is definitely a 0.

So either I'm confused about why going from a 2-in-16 decode to an 8-
in-16 decode is a good thing, or I'm confused about how this binary MAP 
decoding stuff really works, and there is, indeed, a way to do 
conditional probabilities between bits.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!