Building Channels from Existing Channels: Changing an existing transmission matrix, maintaining reliability, and channel graph conceptuatlization

Question

I am reading Sudan's Essential Coding Theory and I am having trouble with chapter 6, about stochastic channels, with regards to how manipulation on the transition matrix $M$ is possible.

Consider a Binary Symmetric Channel (BSC). The probability $p$ is defined as the crossover probability of a letter going into the channel. I want to understand how I can affect the transition matrix.

For example, assume that I have a channel encoder, $E$ ,and channel decoder, $D$, in the system such that I get reliable transmission with $p<\frac{1}{2}$. I want to build a new channel with possibly a new channel encoder, $E'$ and a new channel decoder, $D'$ such that I can create a reliable channel with $p'>\frac{1}{2}$. By the way, this is exercise 6.1 in the book.

From what I understand, I need to show 3 things:

1. The new $p'$ should be placed as the crossover probability.
2. Transmission should still be reliable.
3. The algorithm should still be polynomial w.r.t to the input (this is more relevant to exercise 6.1, as I currently do not understand how can new channels be created from old channels).

So far, I thought of the following:

Since $p<\frac{1}{2}$, I know that $1-p>\frac{1}{2}$, so my initial motivation was to perform a bit-flip to try and create a new channel where $p'=1-p$. That said, I came across the following difficulties:

1. I do not understand where and in what component can I put the bit-flip block. Can I only place it in the channel encoder or the channel decoder?
2. Where does the channel transmission $M$ take its input and output from? Is it from exactly what goes in and out of the channel or does it stretch to before the channel encoder and after the channel decoder?
3. Does reliability mean that I can restore the original message sent before channel encoding, after the channel decoder, with high probability? how can I prove that this property is maintained when composing channels? I suppose I do not need to calculate the probability all over again. Is there any argument that allows me to build on the already existing reliability?
4. Conceptually, how does channel composition look like? Does it look like a flow graph with layers, where the layers correspond to the state of the message after each transition (channel encoder -> channel -> channel decoder), where the edges hold the probabilities for the transitions?

Answer 1

If I want to create new transmission schemes from an existing transmission scheme, I need to be able to give units of the scheme, or blocks in the scheme, their own properties. This allows me to take them, plant them in a new scheme, and still make sense of what is going on.

1. This applies to decoders, with say, probability of error, or rather - how much errors in the encoded message, taken from previous parts of the transmission, can the decoder overcome? If I know something works for a transmission scheme with a specific encoder-channel-receiver, and I want to create a new scheme using the receiver, there should be some property of the receiver that is maintained, based on the initial scheme working.
2. This also applies to transmission matrices w.r.t channels.

This self-maintained properties, independent of a specific scheme, and inherent to the specific box in the scheme, help create a conceptual framework in which compositions are evaluated for reliable transmission.

Thus, answers:

1. Bit-flip block can be placed everywhere. It uses a modifying function on a signal. Any modifications can be placed in a transmission scheme. If I am asking with respect to the possibility of a transmission to be successful, then placing the block before the channel or after the channel, with BSC channels will have similar influence in that in order for a message to stay the same after the passing the bit-flip and then channel (or channel, and then bit-flip), the message must use a crossover route in the BSC.
2. The channel transmission matrix is fixed and determined by the channel. It is a property of the channel and it alone.
3. When probing that reliability is maintained, the key observation is that decoders have the property of "how much they error in the encoded message they can overcome". When using the same decoder in a different scheme, all that is needed is to calculate if the probability for error in the encoded message is not higher than the probability of error the decoder can fix. This is maybe clearer when moving from speaking about probabilities to actual numbers. Then error probability of both encoded message and decoded message can be defined by "fractional error in block size n". This allows to transition the discussion into actual number of errors, by multiplying the probabilities by n and then comparing the sizes. If the decoder in the new scheme is facing less or equal number of errors that it can cope with, the transmission is successful. The number of errors the decoder can overcome is a value determined by the old transmission scheme, known to be reliable. The number of errors possible in the encoded message, that the decoder will face in the new scheme, is a value to be determined by the new transmission scheme.
4. It can be regarded as a flow box, but if you look at recommended books about information theory, they have better representations. In essence, it is a line with blocks. The signal passes through the line, and the boxes interact with the signal, before moving it "forward". Then you get notions that describe signal-box-boxes interaction. One such notion is memory. It relates the flow of information in the scheme: Is all information one way and has to do with the signal? Are blocks independent from each other? If blocks are not independent, then they communicate and then they pass message (or information) not just about the signal. This also allows for modularization in the scheme, and separate the discussion between an entire scheme and individual pieces (or blocks). Such abstraction is crucial with complex systems.

Here is one illustration of a generalized scheme: It is missing individual properties such as the probabilities mentioned earlier (error in decoding, error in encoding), but these can be added

Here is one illustration of a component in a scheme: Here I posted a BSC channel.

Other boxes should also be similar with respect to routing: There's an input, and then circuitry to represent an operation on the input, and then you get an output. There are many types of boxes that induce change into a signal (for example, permutation block or substitution blocks). With respect to inducing change into a signal, both encoders and decoders perform change, but the change is different when considering the entire transmission scheme. So it is important to remember context when considering boxes or blocks: Are they considered individually? Are they considered as a member of an entire transmission scheme?

Here's another illustration, which attempts to connect the two contexts (individual and collective role on a signal):

But you don't have representation for all the components, as you get in the general generalized scheme: Source or channel decoders and encoders are missing. You cannot always show everything on a single map. That's why you have abstraction. But that is a different discussion.

---

Recommended material for further investigation:

Books:

Book 1: Gallager

https://www.amazon.com/Information-Theory-Reliable-Robert-Gallager/dp/0471290483

Book 2: Cover

https://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

Book 3: Claude Shannon

https://www.amazon.com/Mathematical-Theory-Communication-Claude-Shannon/dp/0252725484

It is always good to have the possibility to consult the work of a founding father in field, especially with conceptualization and motivation.

Online lectures (from YouTube):

Playlist 1: Thomas Cover (the author of books 2)

https://www.youtube.com/playlist?list=PLzfesPA4ERSWlcKhDUiApOCt2o9WdlRYb

Playlist 2: Form Stanford

https://www.youtube.com/playlist?list=PLv_7iO_xlL0Kz2nU05COpINjU8C0UPICA