On Thu, 3 Dec 2015 10:46:08 -0800 (PST), RichD
<r_delaney2001@yahoo.com> wrote:
>On November 27, Eric Jacobsen wrote:
>>>>> C = BW . log2(1+S/N)
>>>>> So, where is the encoding method
>>>>> taking into account in the above equation?
>> >>
>>>> Encoding (and modulation) is only mentioned in passing.
>>>> The actual fundamental measure is the number of discrete regions
>>>> that can be packed into the space that you can construct
>>>> with a given bandwidth and a given signal to noise ratio over
>>>> some large amount of time. Shannon used the word "spheres".
>>
>>> Yes. However, there remains an enigma here.
>>> Shannon discussed both the discrete and continuous channel.
>>> For the former, he suggested the obvious solution:
>>> error correction via redundancy.
>>
>>> Regarding the latter, Shannon framed it
>>> geometrically, as you alluded, to produce a mathematical
>>> work of art. The messages reside in a N-dimensional space.
>>> Then, it becomes a packing problem: pack the hyper-
>>> spheres optimally into that space, in a minimax sense,
>>> to achieve the capacity (or as close as feasible). Each
>>> modulated waveform transmitted,representing a particular
>>> message, then fits into a unique sphere.
>>
>>> Seen this way, Shannon is talking about analog waveforms,
>>> and analog channel. Even though the information is
>>> measured in digital bits, the encoding is analog.
>>
>> In this context terminology is fairly important. I'm not sure
>> "encoding" is the right word here, as the distinction between
>> discrete and continuous wrt the signal carries many subtleties in
>> this context.
>
>I mean, a block of bits presented to the channel,
>to be transmitted, is mapped to a unique analog waveform.
>
>In this portion of his paper, Shannon says nothing
>about digital, error correction redundancy.
Yup, and since it is now known that the FEC/ECC plays a huge part in
achieving capacity, distinguishing which "encoding" is meant is
useful.
These days, usually, the waveform is the "modulation", how the bits
are assigned within a constellation is "mapping", the FEC/ECC is the
"coding", etc., etc.. Terminology isn't hard and fast in this
industry, which is often a problem.
>>> But in practice, engineers simply source encode
>>> with redundancy, then send those bit sequences,
>>> with a variety of modulation schemes. No one has
>>> tried to implement Shannon's idea directly: i.e.
>>> encode blocks of source bits into these optimally
>>> separated hyper-spheres.
>>
>> I think you mean channel coding rather than source coding,
>>
>> The sphere thing is partly just a viewpoint. Managing distance
>> spectrums in algebraic codes is sort of a sphere-packing exercise,
>> and the existing of capacity-approaching codes suggests that the
>> sphere-packing is being done efficiently, even if the development of
>> the codes weren't done with that in mind.
>
>That may be so, but it's certainly a roundabout way to
>get there, almost miraculous.
Well, it took decades to figure it out, years to refine it, and
research continues, so I wouldn't call it miraculous.
>It would be theoretically significant, a breakthrough,
>to show that these algebraic methods do indeed address
>the sphere packing framework, that they are in fact
>equivalent (asymptotically). But perhaps someone has
>already done this, and I slept through it -
Sorry, I didn't mean that there were capacity-approaching algebraic
codes, although there may be (but none I can name off the top of my
head). I meant to say, separately, that designing an algebraic code
with good distance-spectrum properties is like a sphere-packing
exercise, and, also, that the existence of capacity-approaching codes
(separate from the algebraic code idea), suggests that they are
efficiently sphere-packed.
For the case of the algebraic codes, it is useful to try to have most
codewords at similar Hamming distances from each other (or greater),
so that a few codewords at or near a minimum-distance that is smaller
than the more common distances don't dominate the code performance.
From this standpoint one is trying to make all the spheres (with a
radius of the Hamming distance to the nearest spheres, where the
spheres are codewords), roughly the same size, hopefully raising the
overall code performance in the process.
Capacity-approaching codes tend to be much more complex in analyzing
distances, even though they're systematic codes. The design criteria
and methodologies for things like Turbo Codes or LDPCs, at least not
that I've ever noticed, don't take into account sphere packing in any
significant sense beyond analyzing error distributions. There have
been some good code designs that were generated either automatically
or heuristically just by looking at performance and tweaking things
until it worked. Claude Berrou had incredible intuition in designing
the first Turbo Codes, as it took a fair amount of time (and other
researchers) to sort out why it worked, and that he'd picked
constituent codes with the right properties before knowing what the
right properties were.
Remember, many random codes are good codes, just some are better than
others. ;)
Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com