Information Theory/General Description - Revision history

Guenter at 15:18, 19 February 2023

2023-02-19T15:18:08Z

Hwang at 12:09, 16 February 2023

2023-02-16T12:09:13Z

Hwang at 12:05, 16 February 2023

2023-02-16T12:05:06Z

Hwang at 12:04, 16 February 2023

2023-02-16T12:04:13Z

Hwang at 12:02, 16 February 2023

2023-02-16T12:02:53Z

Hwang at 11:51, 16 February 2023

2023-02-16T11:51:12Z

Hwang at 11:40, 16 February 2023

2023-02-16T11:40:33Z

Hwang at 11:25, 16 February 2023

2023-02-16T11:25:53Z

Hwang at 11:20, 16 February 2023

2023-02-16T11:20:17Z

Hwang at 11:17, 16 February 2023

2023-02-16T11:17:09Z

Show changes

@@ Line 14: / Line 14: @@
-The following is a detailed discussion '''KORREKTUR: of''':
+The following is a detailed discussion of:
 :*The different destinations of&nbsp; &raquo;source coding&laquo;,&nbsp; &raquo;channel coding&laquo;&nbsp; and&nbsp; &raquo;line coding&laquo;,
@@ Line 32: / Line 32: @@
 *The source signal&nbsp; $q(t)$&nbsp; can be analog as well as digital, just like the sink signal&nbsp; $v(t)$.&nbsp; All other signals in this block diagram, even those not explicitly named here, are digital.
 *In particular, also the signals&nbsp; $x(t)$&nbsp; and&nbsp; $y(t)$&nbsp; at the input and output of the&nbsp; "digital channel"&nbsp; are digital and can therefore also be described completely by the symbol sequences&nbsp; $〈x_ν〉$&nbsp; and&nbsp; $〈y_ν〉$.
-*The&nbsp; "digital channel"&nbsp; includes not only the transmission medium and interference (noise) but also components of the transmitter&nbsp; (modulator, transmitter pulse shaper, etc.)&nbsp; and the receiver&nbsp; (demodulator, receive '''KORREKTUR: receiver''' filter, detector, decision maker '''KORREKTUR: decision''').
 *The chapter&nbsp; [[Digital_Signal_Transmission/Parameters of Digital Channel Models|"Parameters of Digital Channel Models"]]&nbsp; in the book&nbsp; "Digital Signal Transmission"&nbsp; describes the modeling of the&nbsp; "digital channel".
 <br clear=all>
 As can be seen from this block diagram, there are three different types of coding, depending on the target direction.&nbsp; Each of which is realized by the&nbsp; "encoder"&nbsp; on the transmission side and the corresponding&nbsp; "decoder"&nbsp; at the receiver:
-Task of the&nbsp; &raquo;'''source coding'''&laquo;&nbsp; is the reduction of redundancy for data compression, as it is used for example in image coding.&nbsp; By using correlations between the individual points of an image or between the brightness values of a pixel at different times&nbsp; (for moving picture sequences)&nbsp; procedures can be developed which lead to a noticeable reduction of the amount of data (measured in bit or byte) with nearly the same picture quality.&nbsp; A simple example is the&nbsp; &raquo;differential pulse code modulation&laquo;&nbsp; (DPCM).
+&rArr; &nbsp; Task of the&nbsp; &raquo;'''source coding'''&laquo;&nbsp; is the reduction of redundancy for data compression, as it is used for example in image coding.&nbsp; By using correlations between the individual points of an image or between the brightness values of a pixel at different times&nbsp; (for moving picture sequences)&nbsp; procedures can be developed which lead to a noticeable reduction of the amount of data (measured in bit or byte) with nearly the same picture quality.&nbsp; A simple example is the&nbsp; &raquo;differential pulse code modulation&laquo;&nbsp; (DPCM).
-With&nbsp; &raquo;'''channel coding'''&laquo;&nbsp; on the other hand, a noticeable improvement of the transmission behavior is achieved by using a redundancy specifically added at the transmitter to detect and correct transmission errors at the receiver side.&nbsp; Such codes, whose most important representatives are&nbsp; &raquo;block codes&laquo;,&nbsp; &raquo;convolutional codes&laquo;&nbsp; and&nbsp; &raquo;turbo codes&laquo;,&nbsp; are of great importance, especially for heavily disturbed channels.&nbsp; The greater the relative redundancy of the encoded signal, the better the correction properties of the code, but at a reduced payload data rate.
+&rArr; &nbsp; With&nbsp; &raquo;'''channel coding'''&laquo;&nbsp; on the other hand, a noticeable improvement of the transmission behavior is achieved by using a redundancy specifically added at the transmitter to detect and correct transmission errors at the receiver side.&nbsp; Such codes, whose most important representatives are&nbsp; &raquo;block codes&laquo;,&nbsp; &raquo;convolutional codes&laquo;&nbsp; and&nbsp; &raquo;turbo codes&laquo;,&nbsp; are of great importance, especially for heavily disturbed channels.&nbsp; The greater the relative redundancy of the encoded signal, the better the correction properties of the code, but at a reduced payload data rate.
-&raquo;'''Line coding'''&laquo;&nbsp; is used to adapt the transmitted signal&nbsp; $x(t)$&nbsp; to the spectral characteristics of the channel and the receiving equipment by recoding the source symbols. &nbsp; For example, in the case of an&nbsp; (analog)&nbsp; transmission channel over which no direct signal can be transmitted, for which thus&nbsp; $H_{\rm K}(f = 0) = 0$, it must be ensured by line coding that the encoded sequence does not contain long sequences of the same polarity.
+&rArr; &nbsp;  &raquo;'''Line coding'''&laquo;&nbsp; is used to adapt the transmitted signal&nbsp; $x(t)$&nbsp; to the spectral characteristics of the channel and the receiving equipment by recoding the source symbols. &nbsp; For example, in the case of an&nbsp; (analog)&nbsp; transmission channel over which no direct signal can be transmitted, for which thus&nbsp; $H_{\rm K}(f = 0) = 0$, it must be ensured by line coding that the encoded sequence does not contain long sequences of the same polarity.
 The focus of this chapter is on lossless source coding, which generates a data-compressed encoded sequence&nbsp; $〈c_ν〉$&nbsp; starting from the source symbol sequence&nbsp; $〈q_ν〉$&nbsp;  and based on the results of information theory.
@@ Line 50: / Line 53: @@
-''Note'': &nbsp; We uniformly use&nbsp; "$\nu$"&nbsp; here as a control variable of a symbol sequence.&nbsp; Normally, for&nbsp; $〈q_ν〉$,&nbsp; $〈c_ν〉$&nbsp; and&nbsp; $〈x_ν〉$&nbsp; different indices should be used if the rates do not match.
+<u>Note:</u> &nbsp; We uniformly use&nbsp; "$\nu$"&nbsp; here as a control variable of a symbol sequence.&nbsp; Normally, for&nbsp; $〈q_ν〉$,&nbsp; $〈c_ν〉$&nbsp; and&nbsp; $〈x_ν〉$&nbsp; different indices should be used if the rates do not match.
@@ Line 94: / Line 97: @@
 *Especially fonts look "washed out".
 <br clear=all>
-''Note'': &nbsp; Due to technical limitations of&nbsp; $\rm LNTww$&nbsp; all graphics had to be saved as&nbsp; "PNG".
+<u>Note:</u> &nbsp; Due to technical limitations of&nbsp; $\rm LNTwww$&nbsp; all graphics had to be saved as&nbsp; "PNG".
 *In the above graphic, "JPEG" means the PNG conversion of a file previously compressed with&nbsp; "JPEG".
 *However, the associated loss is negligible. }}
@@ Line 105: / Line 108: @@
 == Lossy source coding for audio signals==
 <br>
-A first example of source coding for speech and music is the&nbsp; [https://en.wikipedia.org/wiki/Pulse-code_modulation $\text{pulse-code modulation}$]&nbsp; $\rm (PCM)$, invented in 1938, which extracts the encoded sequence&nbsp; $〈c_ν〉 $&nbsp;from an analog source signal&nbsp; $q(t)$, corresponding to the three processing blocks
+A first example of source coding for speech and music is the&nbsp; [https://en.wikipedia.org/wiki/Pulse-code_modulation "pulse-code modulation"]&nbsp; $\rm (PCM)$, invented in 1938, which extracts the encoded sequence&nbsp; $〈c_ν〉 $&nbsp;from an analog source signal&nbsp; $q(t)$, corresponding to the three processing blocks
 [[File:EN_Mod_T_4_1_S1_v2.png|right|frame|Prinzip der Pulscodemodulation (PCM)]]
 *Sampling,

@@ Line 275: / Line 275: @@
 *The average code word length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the entropy&nbsp; $H$&nbsp; of the source symbol sequence: &nbsp; $L_{\rm M} \ge H \hspace{0.05cm}. $
-*This regularity is called&nbsp; &raquo;''' Source Coding Theorem'''&laquo;, which goes back to&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon $\text{Claude Elwood Shannon}$].&nbsp; &nbsp;
+*This regularity is called&nbsp; &raquo;'''Source Coding Theorem'''&laquo;, which goes back to&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon $\text{Claude Elwood Shannon}$].&nbsp; &nbsp;
 *If the source coder considers only the different symbol probabilities, but not the correlation between symbols, then&nbsp; $L_{\rm M} ≥ H_1$ &nbsp; ⇒ &nbsp; [[Information_Theory/Sources with Memory#Entropy with respect to two-tuples|$\text{first entropy approximation}$]].}}

@@ Line 215: / Line 215: @@
 $\text{Definition:}$&nbsp; The property&nbsp; &raquo;'''prefix-free'''&laquo;&nbsp; indicates that no code word may be the prefix (beginning) of a longer code word.&nbsp; Such a code word is immediately decodable.}}
-*The blue code in&nbsp; [[Information_Theory/General_Description#Description_of_lossless_source_encoding_.E2.80.93_Prerequisites|$\text{Example 4}$]]&nbsp; is not prefix-free.&nbsp; For example, the encoded sequence "01" could be interpreted by the decoder as&nbsp; $\rm AD$&nbsp; but also as&nbsp; $\rm B$.
+*The blue code in&nbsp; [[Information_Theory/General_Description#Description_of_lossless_source_encoding_.E2.80.93_Requirements|$\text{Example 4}$]]&nbsp; is not prefix-free.&nbsp; For example, the encoded sequence "01" could be interpreted by the decoder as&nbsp; $\rm AD$&nbsp; but also as&nbsp; $\rm B$.
 *The red code, on the other hand, is prefix-free, although prefix freedom would not be absolutely necessary here because of&nbsp; $L_μ = \rm const.$
@@ Line 227: / Line 227: @@
 {{GraueBox|TEXT=
 $\text{Example 5:}$&nbsp;
-If you check the second (blue) code of&nbsp; [[Information_Theory/General_Description#Description of lossless source encoding.E2.80.93_Requirements|$\text{Example 4}$]]&nbsp; with&nbsp; $M = 9$&nbsp; and&nbsp; $D = 3$, you get:
+If you check the second (blue) code of&nbsp; [[Information_Theory/General_Description#Description_of_lossless_source_encoding_.E2.80.93_Requirements|$\text{Example 4}$]]&nbsp; with&nbsp; $M = 9$&nbsp; and&nbsp; $D = 3$, you get:
 :$$3 \cdot 3^{-1} + 6 \cdot 3^{-2} = 1.667 > 1 \hspace{0.05cm}.$$

← Older revision		Revision as of 12:04, 16 February 2023
Line 231:		Line 231:
	:$$3 \cdot 3^{-1} + 6 \cdot 3^{-2} = 1.667 > 1 \hspace{0.05cm}.$$		:$$3 \cdot 3^{-1} + 6 \cdot 3^{-2} = 1.667 > 1 \hspace{0.05cm}.$$

−	From this you can see that this code cannot be prefix-free }}	+	From this you can see that this code cannot be prefix-free. }}

@@ Line 181: / Line 181: @@
 *The source encoder replaces the source symbol&nbsp; $q_μ$&nbsp; with the code word&nbsp; $\mathcal{C}(q_μ)$, <br>consisting of&nbsp; $L_μ$&nbsp; code symbols of a new alphabet with the symbol set size&nbsp; $D$&nbsp; $\{0, \ 1$, ... ,&nbsp; $D - 1\}$.&nbsp; This gives the&nbsp; &raquo;'''average code word length'''&laquo;:
-:$$L_{\rm M} = \sum_{\mu=1}^{M} \hspace{0.1cm} p_{\mu} \cdot L_{\mu} \hspace{0.05cm}, \hspace{0.2cm}{\rm mit} \hspace{0.2cm}p_{\mu} = {\rm Pr}(q_{\mu}) \hspace{0.05cm}. $$
+:$$L_{\rm M} = \sum_{\mu=1}^{M} \hspace{0.1cm} p_{\mu} \cdot L_{\mu} \hspace{0.05cm}, \hspace{0.2cm}{\rm with} \hspace{0.2cm}p_{\mu} = {\rm Pr}(q_{\mu}) \hspace{0.05cm}. $$
 {{GraueBox|TEXT=

@@ Line 125: / Line 125: @@
 {{GraueBox|TEXT=
 $\text{Example 2:}$&nbsp;
-The following data is taken from the&nbsp; [[Examples_of_Communication_Systems/Entire GSM Transmission System#Components_of_Language.E2.80.93_and_Data.C3.BCtransmission|$\text{GSM specification}$]]:
+The following data is taken from the&nbsp; [[Examples_of_Communication_Systems/Entire_GSM_Transmission_System#Speech_and_data_transmission_components|$\text{GSM specification}$]]:
 *If a speech signal is spectrally limited to the bandwidth&nbsp; $B = 4 \, \rm kHz$ &nbsp; ⇒ &nbsp; sampling rate $f_{\rm A} = 8 \, \rm kHz$&nbsp; with a quantization of $13 \, \rm bit$ &nbsp; ⇒ &nbsp; number of quantization levels&nbsp; $M = 2^{13} = 8192$&nbsp; a binary data stream of data rate&nbsp; $R = 104 \, \rm kbit/s$ results.
 *The quantization noise ratio is then&nbsp; $20 \cdot \lg M ≈ 78 \, \rm dB$.
@@ Line 142: / Line 142: @@
 In mobile communications, very high data rates often could not (yet) be handled.&nbsp; In the 1990s, speech coding procedures were developed that led to data compression by the factor&nbsp; $8$&nbsp; and more.&nbsp; From today's point of view, it is worth mentioning:
-*The&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Halfrate_Vocoder_and_Enhanced_Fullrate_Codec|$\text{Enhanced Full Rate Codec}$]]&nbsp; $\rm (EFR)$, which extracts&nbsp; exactly&nbsp; $244 \, \rm bit$&nbsp; for each speech frame of&nbsp; $20\, \rm ms$&nbsp;$($Data rate: &nbsp; $12. 2 \, \rm kbit/s)$; <br> this data compression of more than the factor&nbsp; $8$&nbsp; is achieved by stringing together several procedures:
+*The&nbsp; [[Examples_of_Communication_Systems/Speech_Coding#Half_Rate_Vocoder_and_Enhanced_Full_Rate_Codec|$\text{Enhanced Full Rate Codec}$]]&nbsp; $\rm (EFR)$, which extracts&nbsp; exactly&nbsp; $244 \, \rm bit$&nbsp; for each speech frame of&nbsp; $20\, \rm ms$&nbsp;$($Data rate: &nbsp; $12. 2 \, \rm kbit/s)$; <br> this data compression of more than the factor&nbsp; $8$&nbsp; is achieved by stringing together several procedures:
 :# &nbsp;Linear Predictive Coding&nbsp; $\rm (LPC$, short term prediction$)$,
 :# &nbsp;Long Term Prediction&nbsp; $\rm (LTP)$,
 :# &nbsp;Regular Pulse Excitation&nbsp; $\rm (RPE)$.
-*The&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Adaptive_Multi.E2.80. 93Rate_Codec|$\text{Adaptive Multi Rate Codec}$]]&nbsp;  $\rm (AMR)$&nbsp; based on&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Algebraic_Code_Excited_Linear_Prediction|$\rm ACELP$]]&nbsp; ("Algebraic Code Excited Linear Prediction")&nbsp; and several modes between&nbsp; $12. 2 \, \rm kbit/s$&nbsp; $\rm (EFR)$&nbsp; and&nbsp; $4.75 \, \rm kbit/s$&nbsp; so that improved channel coding can be used in case of poorer channel quality.
+*The&nbsp; [[Examples_of_Communication_Systems/Speech_Coding#Adaptive_Multi_Rate_Codec|$\text{Adaptive Multi Rate Codec}$]]&nbsp;  $\rm (AMR)$&nbsp; based on&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Algebraic_Code_Excited_Linear_Prediction|$\rm ACELP$]]&nbsp; ("Algebraic Code Excited Linear Prediction")&nbsp; and several modes between&nbsp; $12. 2 \, \rm kbit/s$&nbsp; $\rm (EFR)$&nbsp; and&nbsp; $4.75 \, \rm kbit/s$&nbsp; so that improved channel coding can be used in case of poorer channel quality.
-*The&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Various_Language Coding Methods|$\text{Wideband-AMR}$]]&nbsp; $\rm (WB-AMR)$&nbsp; with nine modes between&nbsp; $6.6 \, \rm kbit/s$&nbsp; and&nbsp; $23.85 \, \rm kbit/s$. &nbsp; This is used with&nbsp; [[Examples_of_Communication_Systems/General_Description_of_UMTS|$\text{UMTS}$]]&nbsp; and is suitable for broadband signals between&nbsp; $200 \, \rm Hz$&nbsp; and&nbsp; $7 \, \rm kHz$. &nbsp; Sampling is done with&nbsp; $16 \, \rm kHz$, quantization with&nbsp; $4 \, \rm bit$.
+*The&nbsp; [[Examples_of_Communication_Systems/Speech_Coding#Various_speech_coding_methods|$\text{Wideband-AMR}$]]&nbsp; $\rm (WB-AMR)$&nbsp; with nine modes between&nbsp; $6.6 \, \rm kbit/s$&nbsp; and&nbsp; $23.85 \, \rm kbit/s$. &nbsp; This is used with&nbsp; [[Examples_of_Communication_Systems/General_Description_of_UMTS|$\text{UMTS}$]]&nbsp; and is suitable for broadband signals between&nbsp; $200 \, \rm Hz$&nbsp; and&nbsp; $7 \, \rm kHz$. &nbsp; Sampling is done with&nbsp; $16 \, \rm kHz$, quantization with&nbsp; $4 \, \rm bit$.

@@ Line 66: / Line 66: @@
 These compression methods partly use
 *vector quantization for redundancy reduction of correlated pixels,
-*at the same time the lossless compression algorithms according to&nbsp; [[Information_Theory/Entropy Coding According to Huffman#The_Huffman.E2.80.93Algorithm|$\text{Huffman}$]]&nbsp; and&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch|$\text{Lempel/Ziv}$]],
+*at the same time the lossless compression algorithms according to&nbsp; [[Information_Theory/Entropy_Coding_According_to_Huffman#The_Huffman_algorithm|$\text{Huffman}$]]&nbsp; and&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch|$\text{Lempel/Ziv}$]],
 *possibly also transformation coding based on DFT&nbsp; ("Discrete Fourier Transform")&nbsp; and&nbsp; DCT&nbsp; ("Discrete Cosine Transform"),
 *then quantization and transfer in the transformed range.
@@ Line 318: / Line 318: @@
 *The entropy of this alphabet with&nbsp; $M = 27$&nbsp; characters will be&nbsp; $H≈ 4 \, \rm bit/character$.&nbsp; We have only estimated this value.&nbsp;  [https://en.wikipedia.org/wiki/Francis_Bacon $\text{Francis Bacon}$]&nbsp; had already given a binary code in 1623, where each letter is represented by five bits: &nbsp; $L_{\rm M} = 5$.
 *About 250 years later&nbsp; [https://en.wikipedia.org/wiki/Baudot_code $\text{Jean-Maurice-Émile Baudot}$]&nbsp; adopted this code, which was later standardized for the entire telegraphy.&nbsp; One consideration important to him was that a code with a uniform five binary characters per letter is more difficult for an enemy to decipher, since he cannot draw conclusions about the transmitted character from the frequency of its occurrence.
-*The last line in the above table gives an exemplary&nbsp; [[Information_Theory/Entropy_Coding_According_to_Huffman#The_Huffman.E2.80.93Algorithm|$\text{Huffman code}$]]&nbsp; for the above frequency distribution.&nbsp; Probable characters like&nbsp; "E"&nbsp; or&nbsp; "N"&nbsp; and also the&nbsp; "Blank"&nbsp; are represented with three bits only, the rare&nbsp; "Q"&nbsp; on the other hand with eleven bits.
+*The last line in the above table gives an exemplary&nbsp; [[Information_Theory/Entropy_Coding_According_to_Huffman#The_Huffman_algorithm|$\text{Huffman code}$]]&nbsp; for the above frequency distribution.&nbsp; Probable characters like&nbsp; "E"&nbsp; or&nbsp; "N"&nbsp; and also the&nbsp; "Blank"&nbsp; are represented with three bits only, the rare&nbsp; "Q"&nbsp; on the other hand with eleven bits.
 *The average code word length &nbsp;$L_{\rm M} = H + ε$&nbsp; is slightly larger than&nbsp; $H$, whereby we will not go into more detail here about the small positive quantity&nbsp; $ε$.&nbsp; &nbsp; Only this much: &nbsp; There is no prefix-free code with smaller average word length than the Huffman code.
 *Also&nbsp; [https://en.wikipedia.org/wiki/Morse_code $\text{Samuel Morse}$]&nbsp; took into account the different frequencies in his code for telegraphy, already in the 1830s.&nbsp; The Morse code of each character consists of two to four binary characters, which are designated here according to the application with dot&nbsp; ("short")&nbsp; and bar&nbsp; ("long").

← Older revision		Revision as of 11:20, 16 February 2023
Line 14:		Line 14:


−	The following is a detailed discussion:	+	The following is a detailed discussion '''KORREKTUR: of''':

	:*The different destinations of  »source coding«,  »channel coding«  and  »line coding«,		:*The different destinations of  »source coding«,  »channel coding«  and  »line coding«,