Сверточные коды исправляющие ошибки

In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the ‘convolution’ of the encoder over the data, which gives rise to the term ‘convolutional coding’. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time-variant trellis and therefore are typically hard-decision decoded. Convolutional codes are often characterized by the base code rate and the depth (or memory) of the encoder . The base code rate is typically given as , where n is the raw input data rate and k is the data rate of output channel encoded stream. n is less than k because channel coding inserts redundancy in the input bits. The memory is often called the «constraint length» K, where the output is a function of the current input as well as the previous inputs. The depth may also be given as the number of memory elements v in the polynomial or the maximum possible number of states of the encoder (typically : ).

Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real-world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic block codes, which generally have fixed block lengths that are determined by algebraic properties.

The code rate of a convolutional code is commonly modified via symbol puncturing. For example, a convolutional code with a ‘mother’ code rate may be punctured to a higher rate of, for example, simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility of convolutional codes, makes them very popular for digital communications.

History[edit]

Convolutional codes were introduced in 1955 by Peter Elias. It was thought that convolutional codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967, Andrew Viterbi determined that convolutional codes could be maximum-likelihood decoded with reasonable complexity using time invariant trellis based decoders — the Viterbi algorithm. Other trellis-based decoder algorithms were later developed, including the BCJR decoding algorithm.

Recursive systematic convolutional codes were invented by Claude Berrou around 1991. These codes proved especially useful for iterative processing including the processing of concatenated codes such as turbo codes.^[1]

Using the «convolutional» terminology, a classic convolutional code might be considered a Finite impulse response (FIR) filter, while a recursive convolutional code might be considered an Infinite impulse response (IIR) filter.

Where convolutional codes are used[edit]

Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as digital video, radio, mobile communications (e.g., in GSM, GPRS, EDGE and 3G networks (until 3GPP Release 7)^[3][4]) and satellite communications.^[5] These codes are often implemented in concatenation with a hard-decision code, particularly Reed–Solomon. Prior to turbo codes such constructions were the most efficient, coming closest to the Shannon limit.

Convolutional encoding[edit]

To convolutionally encode data, start with k memory registers, each holding one input bit. Unless otherwise specified, all memory registers start with a value of 0. The encoder has n modulo-2 adders (a modulo 2 adder can be implemented with a single Boolean XOR gate, where the logic is: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0), and n generator polynomials — one for each adder (see figure below). An input bit m₁ is fed into the leftmost register. Using the generator polynomials and the existing values in the remaining registers, the encoder outputs n symbols. These symbols may be transmitted or punctured depending on the desired code rate. Now bit shift all register values to the right (m₁ moves to m₀, m₀ moves to m₋₁) and wait for the next input bit. If there are no remaining input bits, the encoder continues shifting until all registers have returned to the zero state (flush bit termination).

The figure below is a rate 1⁄3 (m⁄n) encoder with constraint length (k) of 3. Generator polynomials are G₁ = (1,1,1), G₂ = (0,1,1), and G₃ = (1,0,1). Therefore, output bits are calculated (modulo 2) as follows:

n₁ = m₁ + m₀ + m₋₁

n₂ = m₀ + m₋₁

n₃ = m₁ + m₋₁.

Convolutional codes can be systematic and non-systematic:

• systematic repeats the structure of the message before encoding
• non-systematic changes the initial structure

Non-systematic convolutional codes are more popular due to better noise immunity. It relates to the free distance of the convolutional code.^[6]

• 

  A short illustration of non-systematic convolutional code.

• 

  A short illustration of systematic convolutional code.

Recursive and non-recursive codes[edit]

The encoder on the picture above is a non-recursive encoder. Here’s an example of a recursive one and as such it admits a feedback structure:

The example encoder is systematic because the input data is also used in the output symbols (Output 2). Codes with output symbols that do not include the input data are called non-systematic.

Recursive codes are typically systematic and, conversely, non-recursive codes are typically non-systematic. It isn’t a strict requirement, but a common practice.

The example encoder in Img. 2. is an 8-state encoder because the 3 registers will create 8 possible encoder states (2³). A corresponding decoder trellis will typically use 8 states as well.

Recursive systematic convolutional (RSC) codes have become more popular due to their use in Turbo Codes. Recursive systematic codes are also referred to as pseudo-systematic codes.

Other RSC codes and example applications include:

Useful for LDPC code implementation and as inner constituent code for serial concatenated convolutional codes (SCCC’s).

Useful for SCCC’s and multidimensional turbo codes.

Useful as constituent code in low error rate turbo codes for applications such as satellite links. Also suitable as SCCC outer code.

Impulse response, transfer function, and constraint length[edit]

A convolutional encoder is called so because it performs a convolution of the input stream with the encoder’s impulse responses:

where x is an input sequence, y^j is a sequence from output j, h^j is an impulse response for output j and denotes convolution.

A convolutional encoder is a discrete linear time-invariant system. Every output of an encoder can be described by its own transfer function, which is closely related to the generator polynomial. An impulse response is connected with a transfer function through Z-transform.

Transfer functions for the first (non-recursive) encoder are:

Transfer functions for the second (recursive) encoder are:

Define m by

where, for any rational function ,

.

Then m is the maximum of the polynomial degrees of the
, and the constraint length is defined as . For instance, in the first example the constraint length is 3, and in the second the constraint length is 4.

Trellis diagram[edit]

A convolutional encoder is a finite state machine. An encoder with n binary cells will have 2ⁿ states.

Imagine that the encoder (shown on Img.1, above) has ‘1’ in the left memory cell (m₀), and ‘0’ in the right one (m₋₁). (m₁ is not really a memory cell because it represents a current value). We will designate such a state as «10». According to an input bit the encoder at the next turn can convert either to the «01» state or the «11» state. One can see that not all transitions are possible for (e.g., a decoder can’t convert from «10» state to «00» or even stay in «10» state).

All possible transitions can be shown as below:

An actual encoded sequence can be represented as a path on this graph. One valid path is shown in red as an example.

This diagram gives us an idea about decoding: if a received sequence doesn’t fit this graph, then it was received with errors, and we must choose the nearest correct (fitting the graph) sequence. The real decoding algorithms exploit this idea.

Free distance and error distribution[edit]

The free distance^[7] (d) is the minimal Hamming distance between different encoded sequences. The correcting capability (t) of a convolutional code is the number of errors that can be corrected by the code. It can be calculated as

Since a convolutional code doesn’t use blocks, processing instead a continuous bitstream, the value of t applies to a quantity of errors located relatively near to each other. That is, multiple groups of t errors can usually be fixed when they are relatively far apart.

Free distance can be interpreted as the minimal length of an erroneous «burst» at the output of a convolutional decoder. The fact that errors appear as «bursts» should be accounted for when designing a concatenated code with an inner convolutional code. The popular solution for this problem is to interleave data before convolutional encoding, so that the outer block (usually Reed–Solomon) code can correct most of the errors.

Decoding convolutional codes[edit]

Several algorithms exist for decoding convolutional codes. For relatively small values of k, the Viterbi algorithm is universally used as it provides maximum likelihood performance and is highly parallelizable. Viterbi decoders are thus easy to implement in VLSI hardware and in software on CPUs with SIMD instruction sets.

Longer constraint length codes are more practically decoded with any of several sequential decoding algorithms, of which the Fano algorithm is the best known. Unlike Viterbi decoding, sequential decoding is not maximum likelihood but its complexity increases only slightly with constraint length, allowing the use of strong, long-constraint-length codes. Such codes were used in the Pioneer program of the early 1970s to Jupiter and Saturn, but gave way to shorter, Viterbi-decoded codes, usually concatenated with large Reed–Solomon error correction codes that steepen the overall bit-error-rate curve and produce extremely low residual undetected error rates.

Both Viterbi and sequential decoding algorithms return hard decisions: the bits that form the most likely codeword. An approximate confidence measure can be added to each bit by use of the Soft output Viterbi algorithm. Maximum a posteriori (MAP) soft decisions for each bit can be obtained by use of the BCJR algorithm.

Popular convolutional codes[edit]

In fact, predefined convolutional codes structures obtained during scientific researches are used in the industry. This relates to the possibility to select catastrophic convolutional codes (causes larger number of errors).

An especially popular Viterbi-decoded convolutional code, used at least since the Voyager program has a constraint length K of 7 and a rate r of 1/2.^[12]

Mars Pathfinder, Mars Exploration Rover and the Cassini probe to Saturn use a K of 15 and a rate of 1/6; this code performs about 2 dB better than the simpler code at a cost of 256× in decoding complexity (compared to Voyager mission codes).

The convolutional code with a constraint length of 2 and a rate of 1/2 is used in GSM as an error correction technique.^[13]

Punctured convolutional codes[edit]

Convolutional code with any code rate can be designed based on polynomial selection;^[15] however, in practice, a puncturing procedure is often used to achieve the required code rate. Puncturing is a technique used to make a m/n rate code from a «basic» low-rate (e.g., 1/n) code. It is achieved by deleting of some bits in the encoder output. Bits are deleted according to a puncturing matrix. The following puncturing matrices are the most frequently used:

For example, if we want to make a code with rate 2/3 using the appropriate matrix from the above table, we should take a basic encoder output and transmit every first bit from the first branch and every bit from the second one. The specific order of transmission is defined by the respective communication standard.

Punctured convolutional codes are widely used in the satellite communications, for example, in INTELSAT systems and Digital Video Broadcasting.

Punctured convolutional codes are also called «perforated».

Turbo codes: replacing convolutional codes[edit]

Simple Viterbi-decoded convolutional codes are now giving way to turbo codes, a new class of iterated short convolutional codes that closely approach the theoretical limits imposed by Shannon’s theorem with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. Concatenation with an outer algebraic code (e.g., Reed–Solomon) addresses the issue of error floors inherent to turbo code designs.

See also[edit]

• Quantum convolutional code

References[edit]

•  This article incorporates public domain material from Federal Standard 1037C. General Services Administration. Archived from the original on 2022-01-22.

External links[edit]

• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses convolutional codes in Chapter 48.
• The Error Correcting Codes (ECC) Page
• Matlab explanations
• Fundamentals of Convolutional Decoders for Better Digital Communications
• Convolutional codes (MIT)
• Information Theory and Coding (TU Ilmenau), discusses convolutional codes on page 48.

Further reading[edit]

In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the ‘convolution’ of the encoder over the data, which gives rise to the term ‘convolutional coding’. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time-variant trellis and therefore are typically hard-decision decoded. Convolutional codes are often characterized by the base code rate and the depth (or memory) of the encoder . The base code rate is typically given as , where n is the raw input data rate and k is the data rate of output channel encoded stream. n is less than k because channel coding inserts redundancy in the input bits. The memory is often called the «constraint length» K, where the output is a function of the current input as well as the previous inputs. The depth may also be given as the number of memory elements v in the polynomial or the maximum possible number of states of the encoder (typically : ).

Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real-world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic block codes, which generally have fixed block lengths that are determined by algebraic properties.

The code rate of a convolutional code is commonly modified via symbol puncturing. For example, a convolutional code with a ‘mother’ code rate may be punctured to a higher rate of, for example, simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility of convolutional codes, makes them very popular for digital communications.

History[edit]

Convolutional codes were introduced in 1955 by Peter Elias. It was thought that convolutional codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967, Andrew Viterbi determined that convolutional codes could be maximum-likelihood decoded with reasonable complexity using time invariant trellis based decoders — the Viterbi algorithm. Other trellis-based decoder algorithms were later developed, including the BCJR decoding algorithm.

Recursive systematic convolutional codes were invented by Claude Berrou around 1991. These codes proved especially useful for iterative processing including the processing of concatenated codes such as turbo codes.^[1]

Using the «convolutional» terminology, a classic convolutional code might be considered a Finite impulse response (FIR) filter, while a recursive convolutional code might be considered an Infinite impulse response (IIR) filter.

Where convolutional codes are used[edit]

Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as digital video, radio, mobile communications (e.g., in GSM, GPRS, EDGE and 3G networks (until 3GPP Release 7)^[3][4]) and satellite communications.^[5] These codes are often implemented in concatenation with a hard-decision code, particularly Reed–Solomon. Prior to turbo codes such constructions were the most efficient, coming closest to the Shannon limit.

Convolutional encoding[edit]

To convolutionally encode data, start with k memory registers, each holding one input bit. Unless otherwise specified, all memory registers start with a value of 0. The encoder has n modulo-2 adders (a modulo 2 adder can be implemented with a single Boolean XOR gate, where the logic is: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0), and n generator polynomials — one for each adder (see figure below). An input bit m₁ is fed into the leftmost register. Using the generator polynomials and the existing values in the remaining registers, the encoder outputs n symbols. These symbols may be transmitted or punctured depending on the desired code rate. Now bit shift all register values to the right (m₁ moves to m₀, m₀ moves to m₋₁) and wait for the next input bit. If there are no remaining input bits, the encoder continues shifting until all registers have returned to the zero state (flush bit termination).

The figure below is a rate 1⁄3 (m⁄n) encoder with constraint length (k) of 3. Generator polynomials are G₁ = (1,1,1), G₂ = (0,1,1), and G₃ = (1,0,1). Therefore, output bits are calculated (modulo 2) as follows:

n₁ = m₁ + m₀ + m₋₁

n₂ = m₀ + m₋₁

n₃ = m₁ + m₋₁.

Convolutional codes can be systematic and non-systematic:

• systematic repeats the structure of the message before encoding
• non-systematic changes the initial structure

Non-systematic convolutional codes are more popular due to better noise immunity. It relates to the free distance of the convolutional code.^[6]

• 

  A short illustration of non-systematic convolutional code.

• 

  A short illustration of systematic convolutional code.

Recursive and non-recursive codes[edit]

The encoder on the picture above is a non-recursive encoder. Here’s an example of a recursive one and as such it admits a feedback structure:

The example encoder is systematic because the input data is also used in the output symbols (Output 2). Codes with output symbols that do not include the input data are called non-systematic.

Recursive codes are typically systematic and, conversely, non-recursive codes are typically non-systematic. It isn’t a strict requirement, but a common practice.

The example encoder in Img. 2. is an 8-state encoder because the 3 registers will create 8 possible encoder states (2³). A corresponding decoder trellis will typically use 8 states as well.

Recursive systematic convolutional (RSC) codes have become more popular due to their use in Turbo Codes. Recursive systematic codes are also referred to as pseudo-systematic codes.

Other RSC codes and example applications include:

Useful for LDPC code implementation and as inner constituent code for serial concatenated convolutional codes (SCCC’s).

Useful for SCCC’s and multidimensional turbo codes.

Useful as constituent code in low error rate turbo codes for applications such as satellite links. Also suitable as SCCC outer code.

Impulse response, transfer function, and constraint length[edit]

A convolutional encoder is called so because it performs a convolution of the input stream with the encoder’s impulse responses:

where x is an input sequence, y^j is a sequence from output j, h^j is an impulse response for output j and denotes convolution.

A convolutional encoder is a discrete linear time-invariant system. Every output of an encoder can be described by its own transfer function, which is closely related to the generator polynomial. An impulse response is connected with a transfer function through Z-transform.

Transfer functions for the first (non-recursive) encoder are:

Transfer functions for the second (recursive) encoder are:

Define m by

where, for any rational function ,

.

Then m is the maximum of the polynomial degrees of the
, and the constraint length is defined as . For instance, in the first example the constraint length is 3, and in the second the constraint length is 4.

Trellis diagram[edit]

A convolutional encoder is a finite state machine. An encoder with n binary cells will have 2ⁿ states.

Imagine that the encoder (shown on Img.1, above) has ‘1’ in the left memory cell (m₀), and ‘0’ in the right one (m₋₁). (m₁ is not really a memory cell because it represents a current value). We will designate such a state as «10». According to an input bit the encoder at the next turn can convert either to the «01» state or the «11» state. One can see that not all transitions are possible for (e.g., a decoder can’t convert from «10» state to «00» or even stay in «10» state).

All possible transitions can be shown as below:

An actual encoded sequence can be represented as a path on this graph. One valid path is shown in red as an example.

This diagram gives us an idea about decoding: if a received sequence doesn’t fit this graph, then it was received with errors, and we must choose the nearest correct (fitting the graph) sequence. The real decoding algorithms exploit this idea.

Free distance and error distribution[edit]

The free distance^[7] (d) is the minimal Hamming distance between different encoded sequences. The correcting capability (t) of a convolutional code is the number of errors that can be corrected by the code. It can be calculated as

Since a convolutional code doesn’t use blocks, processing instead a continuous bitstream, the value of t applies to a quantity of errors located relatively near to each other. That is, multiple groups of t errors can usually be fixed when they are relatively far apart.

Free distance can be interpreted as the minimal length of an erroneous «burst» at the output of a convolutional decoder. The fact that errors appear as «bursts» should be accounted for when designing a concatenated code with an inner convolutional code. The popular solution for this problem is to interleave data before convolutional encoding, so that the outer block (usually Reed–Solomon) code can correct most of the errors.

Decoding convolutional codes[edit]

Several algorithms exist for decoding convolutional codes. For relatively small values of k, the Viterbi algorithm is universally used as it provides maximum likelihood performance and is highly parallelizable. Viterbi decoders are thus easy to implement in VLSI hardware and in software on CPUs with SIMD instruction sets.

Longer constraint length codes are more practically decoded with any of several sequential decoding algorithms, of which the Fano algorithm is the best known. Unlike Viterbi decoding, sequential decoding is not maximum likelihood but its complexity increases only slightly with constraint length, allowing the use of strong, long-constraint-length codes. Such codes were used in the Pioneer program of the early 1970s to Jupiter and Saturn, but gave way to shorter, Viterbi-decoded codes, usually concatenated with large Reed–Solomon error correction codes that steepen the overall bit-error-rate curve and produce extremely low residual undetected error rates.

Both Viterbi and sequential decoding algorithms return hard decisions: the bits that form the most likely codeword. An approximate confidence measure can be added to each bit by use of the Soft output Viterbi algorithm. Maximum a posteriori (MAP) soft decisions for each bit can be obtained by use of the BCJR algorithm.

Popular convolutional codes[edit]

In fact, predefined convolutional codes structures obtained during scientific researches are used in the industry. This relates to the possibility to select catastrophic convolutional codes (causes larger number of errors).

An especially popular Viterbi-decoded convolutional code, used at least since the Voyager program has a constraint length K of 7 and a rate r of 1/2.^[12]

Mars Pathfinder, Mars Exploration Rover and the Cassini probe to Saturn use a K of 15 and a rate of 1/6; this code performs about 2 dB better than the simpler code at a cost of 256× in decoding complexity (compared to Voyager mission codes).

The convolutional code with a constraint length of 2 and a rate of 1/2 is used in GSM as an error correction technique.^[13]

Punctured convolutional codes[edit]

Convolutional code with any code rate can be designed based on polynomial selection;^[15] however, in practice, a puncturing procedure is often used to achieve the required code rate. Puncturing is a technique used to make a m/n rate code from a «basic» low-rate (e.g., 1/n) code. It is achieved by deleting of some bits in the encoder output. Bits are deleted according to a puncturing matrix. The following puncturing matrices are the most frequently used:

For example, if we want to make a code with rate 2/3 using the appropriate matrix from the above table, we should take a basic encoder output and transmit every first bit from the first branch and every bit from the second one. The specific order of transmission is defined by the respective communication standard.

Punctured convolutional codes are widely used in the satellite communications, for example, in INTELSAT systems and Digital Video Broadcasting.

Punctured convolutional codes are also called «perforated».

Turbo codes: replacing convolutional codes[edit]

Simple Viterbi-decoded convolutional codes are now giving way to turbo codes, a new class of iterated short convolutional codes that closely approach the theoretical limits imposed by Shannon’s theorem with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. Concatenation with an outer algebraic code (e.g., Reed–Solomon) addresses the issue of error floors inherent to turbo code designs.

See also[edit]

• Quantum convolutional code

References[edit]

•  This article incorporates public domain material from Federal Standard 1037C. General Services Administration. Archived from the original on 2022-01-22.

External links[edit]

• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses convolutional codes in Chapter 48.
• The Error Correcting Codes (ECC) Page
• Matlab explanations
• Fundamentals of Convolutional Decoders for Better Digital Communications
• Convolutional codes (MIT)
• Information Theory and Coding (TU Ilmenau), discusses convolutional codes on page 48.

Further reading[edit]

При
изучении блочных кодов говорилось, что
способность кода к кор­рекции ошибок,
t,
представляет
собой количество ошибочных кодовых
символов, ко­торые можно исправить в
каждом блоке кода путем декодирования
по методу мак­симального правдоподобия.
В то же время при декодировании сверточных
кодов способность кода к коррекции
ошибок нельзя сформулировать так
лаконично. Можно сказать, что при
декодировании по принципу максималь­ного
правдоподобия код способен исправить
t
ошибок
в пределах нескольких длин кодового
ограничения, причем «несколько» —
это где-то от 3 до 5. Точное значение длины
зависит от характера распределения
ошибок.

8.4.2. Систематические и несистематические сверточные коды

Систематический
сверточный
код — это код, в котором входной k-кортеж
фигурирует как часть выходного n-кортежа
кодового слова, соответствующего этому
k-кортежу.
На рис. 8.17 показан двоичный систематический
кодер со степенью кодирования 1/2 и К
= 3. Для
линейных блочных кодов любой
несистематический код можно преобра­зовать
в систематический с такими же
пространственными характеристиками
блоков. При использовании сверточных
кодов это не так. Причина в том, что
сверточные ко­ды сильно зависят от
просвета;
при
построении сверточного кода в
систематической форме при данной длине
кодового ограничения и степени кодирования
максимально возможное значение просвета
снижается.

В
табл.8.1 показан максимальный просвет
при степени кодирования 1/2 для
сис­тематического и несистематического
кодов с К от
2 до 8. При большой длине кодо­вого
ограничения результаты отличаются еще
сильнее .

8.4.3. Распространение катастрофических ошибок в сверточных кодах

Катастрофическая
ошибка возникает,
когда конечное число ошибок в кодовых
симво­лах вызывает бесконечное число
битовых ошибок в декодированных данных.
Мэсси (Massey)
и Сейн (Sain)
указали необходимые и достаточные
условия для сверточного кода, при которых
возможно распространение катастрофических
ошибок. Условием распространения
катастрофических ошибок для кода со
степенью кодирования 1/2 является на­личие
у порождающих многочленов общего
полиномиального множителя (степени не
менее едини­цы). Например, на рис. 8.18,
а показан
кодер с К = 3, степенью
кодирования 1/2, со старшим многочленом
g₁(X)
и младшим g₂(X):

g₁(X)
= 1 + X,

g₂(X)
= 1 + X².

Многочлены g₁(X)
и g₂(X)
имеют общий множитель 1 + X,
поскольку

1 + X²
= (1 + X)(1
+ X).

Следовательно,
в кодере, показанном на рис. 8.18, а,
может происходить
распростра­нение

катастрофической
ошибки.

Если
говорить о диаграмме состояний кода
произвольной степени кодирования, то
катастрофическая ошибка может появиться
тогда и только тогда, когда любая петля
пути на диаграмме имеет нулевой весовой
коэффициент (нулевое расстояние до
нуле­вого пути). Чтобы проиллюстрировать
это, рассмотрим пример, приведенный на
рис. 8.18 На диаграмме (рис. 8.18, б)
узел состояния а =00
разбит на два узла, а
и е,
как и ранее. Допустим,
что нулевой путь является правильным,
тогда неправильный путь a
b
d
d
… d
с e
имеет точно 6 единиц,
независимо от того, сколько раз мы
обой­дем вокруг петли в узле d.
К выбору этого
непра­вильного пути могут привести
три канальные ошибки. На таком пути
может появиться сколь угодно большое
число ошибок (две плюс количество раз
обхода петли). Для кодов со степенью
кодирования 1/n
можно видеть, что если каждый сумматор
в кодере имеет четное количество
соединений, петли, которые соответствуют
информа­ционным состояниям со всеми
единицами, будут иметь нулевой вес, и,
следовательно, код
будет катастрофическим.

Единственное
преимущество описанного ранее
систематического кода заключается в
том, что он никогда не будет катастрофическим,
поскольку каждая петля должна содер­жать
по крайней мере одну ветвь, порождаемую
ненулевым входным битом; следова­тельно,
каждая петля должна содержать ненулевой
кодовый символ. Впрочем, можно показать
,что только небольшая часть несистематических
кодов (исключая тот, в ко­тором все
сумматоры имеют четное количество
соединений) является катастрофической.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

Для обнаружения ошибок используют коды обнаружения ошибок, для исправления — корректирующие коды (коды, исправляющие ошибки, коды с коррекцией ошибок, помехоустойчивые коды).

Способы борьбы с ошибками

В процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, физическом, канальном, транспортном уровнях модели OSI).

В системах связи возможны несколько стратегий борьбы с ошибками:

• обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;
• обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
• исправление ошибок (forward error correction) применяется на физическом уровне.

Коды обнаружения и исправления ошибок

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.

Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию (контрольное число), а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.

С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

По способу работы с данными коды, исправляющие ошибки делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные, работающие с данными как с непрерывным потоком.

Блоковые коды

Пусть кодируемая информация делится на фрагменты длиной бит, которые преобразуются в кодовые слова длиной бит. Тогда соответствующий блоковый код обычно обозначают . При этом число называется скоростью кода.

Если исходные бит код оставляет неизменными, и добавляет проверочных, такой код называется систематическим, иначе несистематическим.

Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из информационных бит сопоставляется бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:

• способность исправлять как можно большее число ошибок,
• как можно меньшая избыточность,
• простота кодирования и декодирования.

Нетрудно видеть, что приведённые требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.

Практически все используемые коды являются линейными. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования.

Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовём его ) в -мерном линейном пространстве, изоморфное пространству -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.

Пусть  — ортогональное подпространство по отношению к , а  — матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

Минимальное расстояние и корректирующая способность

Основная статья: Расстояние Хемминга

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях, , что равно числу «единиц» в векторе .

Минимальное расстояние Хемминга является важной характеристикой линейного блокового кода. Она показывает насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

, округляем «вниз», так чтобы .

Корректирующая способность определяет, сколько ошибок передачи кода (типа ) можно гарантированно исправить. То есть вокруг каждого кода имеем -окрестность , которая состоит из всех возможных вариантов передачи кода с числом ошибок () не более . Никакие две окрестности двух любых кодов не пересекаются друг с другом, так как расстояние между кодами (то есть центрами этих окрестностей) всегда больше двух их радиусов .

Таким образом получив искажённый код из декодер принимает решение, что был исходный код , исправляя тем самым не более ошибок.

Поясним на примере. Предположим, что есть два кодовых слова и , расстояние Хемминга между ними равно 3. Если было передано слово , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к любому другому, и в частности к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ) то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение что передавалось слово .

Коды Хемминга

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

, где  — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

Общий метод декодирования линейных кодов

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова соответствует наиболее вероятное переданное слово . Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора вычисляется синдром . Поскольку , где  — кодовое слово, а  — вектор ошибки, то . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды

Несмотря на то, что декодирование линейных кодов уже значительно проще декодирования большинства нелинейных, для большинства кодов этот процесс всё ещё достаточно сложен. Циклические коды, кроме более простого декодирования, обладают и другими важными свойствами.

Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть могут принимать значения 0 или 1.

Порождающий (генераторный) полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному . Порождающий полином является делителем .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12
CRC-16	16
CRC-CCITT	16
CRC-32	32

Коды БЧХ

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами (октетами).

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды

Файл:ECC NASA standard coder.png

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

Свёрточные коды, как правило, порождаются дискретной линейной инвариантной во времени системой. Поэтому, в отличие от большинства блоковых кодов, свёрточное кодирование — очень простая операция, чего нельзя сказать о декодировании.

Кодирование свёрточным кодом производится с помощью регистра сдвига, отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.

Декодирование свёрточных кодов, как правило, производится по алгоритму Витерби, который пытается восстановить переданную последовательность согласно критерию максимального правдоподобия.

Преимущества и недостатки свёрточных кодов

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование

Преимущества разных способов кодирования можно объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако, декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Оценка эффективности кодов

Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).

Граница Хемминга и совершенные коды

Основная статья: Граница Хэмминга

Пусть имеется двоичный блоковый код с корректирующей способностью . Тогда справедливо неравенство (называемое границей Хемминга):

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.

Энергетический выигрыш

При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

• в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
• в системах хранения информации, в том числе магнитных и оптических.

Коды, обнаруживающие ошибки, применяются в сетевых протоколах различных уровней.

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Для этого метода необходим полнодуплексный канал. Передача данных от передатчика к приемнику производится одновременно. В случае ошибки передача возобновляется, начиная с ошибочного блока (то есть, передается ошибочный блок и все последующие).

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также

• Цифровая связь
• Линейный код
• Циклический код
• Код Боуза — Чоудхури — Хоквингема
• Код Рида — Соломона
• LDPC
• Свёрточный код
• Турбо-код

Литература

• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки

• Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Проверено 25 декабря 2006.

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Обнаружение и исправление ошибок. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

7.4.1. Пространственные характеристики сверточных кодов

7.4.1.1. Возможности сверточного кода в коррекцииошибок

7.4.2. Систематические и несистематические сверточные коды

7.4.3. Накопление катастрофических ошибок в сверточных кодах

7.4.4. Границы рабочих характеристик сверточных кодов

7.4.5. Эффективность кодирования

7.4.6. Наиболее известные сверточные коды

7.4.7. Компромиссы сверточного кодирования

7.4.7.1. Производительность при когерентнойпередаче сигналов с модуляцией PSK

7.4.7.2.Производительность при некогерентной ортогональной передаче сигналов

7.4.8. Мягкое декодирование по алгоритму Витерби

7.4.1. Пространственные характеристики сверточных кодов

Рассмотрим пространственные характеристики сверточных кодов в контексте простого кодера и его решетчатой диаграммы (рис 7.7.). Мы хотим узнать расстояние между всеми возможными парами последовательности кодовых слов. Как и в случае блочных кодов (см. раздел 6.5.2), нас интересует, минимальное расстояние между всеми такими парами последовательности таких кодовых слов в коде, поскольку минимальное расстояние связано с возможностями кода в коррекции ошибок. Поскольку сверточный код является групповым или линейным [6], можно без потери общности просто найти минимальное расстояние между последовательностью кодовых слов и нулевой последовательностью. Другими словами, для линейного кода данное контрольное сообщение окажется точно таким же «хорошим», как и любое другое. Так почему бы не взять то сообщение, которое легко проследить, а именно нулевую последовательность? Допустим, что на вход передана нулевая последовательность; следовательно, нас интересует такой путь, который начинается и заканчивается в состоянии 00 и не возвращается к состоянию 00 нигде внутри пути. Всякий раз, когда расстояние любых других путей, которые сливаются с состоянием а = 00 в момент окажется меньше расстояния нулевого пути. Иными словами, при нулевой передаче ошибка возникает всегда, когда не выживает нулевой путь. Следовательно, ошибка, о которой идет речь, связана с выживающим путем, который расходиться, а затем снова сливается с нулевым путем. Может возникнуть вопрос, зачем нужно чтобы пути сливались? Не будет ли для обнаружения ошибки достаточно лишь того, что бы пути расходились? В принципе, достаточно, но если ошибка характеризуется только расхождением, то декодер, начиная с этой точки, будет выдавать вместо оставшегося сообщения сплошной «мусор». Мы хотим выразить возможности декодера через число обычно появляющихся ошибок, то есть хотим узнать «самый легкий» для декодера способ сделать ошибку. Минимально расстояние для такой ошибки можно найти, полностью изучив все пути из состояния 00 в состояние 00. Итак, давайте заново начертим решетчатую диаграмму, как показано на рисунке 7.16, и обозначим каждую ветвь не символом ответвляющегося слова, а её расстояние Хемминга от нулевого кодового слова. Расстояние Хемминга между двумя последовательностями разной длины можно получить путем их сравнивания, т.е. прибавив к началу более короткой последовательности нужное количество нулей. Рассмотрим все пути, которые расходятся из нулевого пути и затем в какой то момент снова сливаются в произвольном узле. ИЗ диаграммы на рисунке 7.16 можно получить расстояние этих путей до нулевого пути. И так, на расстоянии 5 от нулевого пути имеется один путь; этот путь отходит от нулевого в момент в . Точно так же имеется два пути с расстоянием 6, один отходит в момент и сливается с ним в момент , а другой отходит в момент и сливается с ним в момент и т.д. Также можно видеть (по пунктирным и сплошным линиям на диаграмме), что входными битами для расстояния 5 будет 100; от нулевой последовательности эта последовательность отличается только одним битом. Точно так же входные биты для путей с расстоянием 6 будут 1100 и 10100; каждая из этих последовательностей отличается от нулевого пути в двух местах. Минимальная длина пути из числа расходящихся, а затем сливающихся путей называетсяминимальным просветом (minimum free distance), или просто просветом (free distance). Его можно видеть на рис. 7.16, где он показан жирной линией. Для оценки возможностей кода коррекции ошибок, мы повторно приведем уравнение (6.44) с заменой минимального расстояния на просвет .

(7.11)

Здесь [x] означает наибольшее целое, не большее х. Положив =5, можно видеть, что код, описываемый кодером на рис. 7.3, может исправить две любые ошибки канала.

Рис. 7.16. Решетчатая диаграмма с обозначенными расстояниями от нулевого пути

Решетчатая диаграмма представляет собой «правила игры». Она является как бы символическим описанием всех возможных переходов и соответствующих начальных и конечных состояний, ассоциируемых с конкретным конечным автоматом. Эта диаграмма позволяет взглянуть глубже на выгоды (эффективность кодирования), которые дает применение кодирования с коррекцией ошибок. Взглянем на рис. 7.16 и на возможные ошибочные расхождения и слияния путей. Из рисунка видно, что декодер не может сделать ошибку произвольным образом. Ошибочный путь должен следовать одному из возможных переходов. Решетка позволяет нам определить все такие доступные пути. Получив по этому пути кодированные данные, мы можем наложить ограничения на переданный сигнал. Если декодер знает об этих ограничениях, то это позволяет ему более просто (используя меньшее ) удовлетворять требованиям надежной безошибочной работы.

Хотя на рис. 7.16 представлен способ прямого вычисления просвета, для него можно получить более строгое аналитическое выражение, воспользовавшись для этого диаграммой состояний, изображенной на рис. 7.5. Для начала обозначим ветви диаграммы состояний как , как это показано на рис. 7.17, где показатель D означает расстояние Хэмминга между ответвленным словом этой ветви и нулевой ветвью. Петлю в узле а можно убрать, поскольку она не дает никакого вклада в пространственные характеристики последовательности кодовых слов относительно нулевой последовательности. Более того, узел а можно разбить на два узла (обозначим их а и е), один из них представляет вход, а другой — выход диаграммы состояний. Все пути, начинающиеся из состояния а=00 и заканчивающиеся в е=00, можно проследить на модифицированной диаграмме состояний, показанной на рис. 7.17. Передаточную функцию пути a b c e (который начинается и заканчивается в состоянии 00) можно рассчитать через неопределенный “заполнитель” D как . Степень D — общее число единиц на пути, а значит, расстояние Хэмминга до нулевого пути. Точно так же пути a b d c e и а b c b с е имеют передаточную функцию D⁶ и, соответственно, расстояние Хэмминга, равное 6, до нулевого пути. Теперь уравнения состояния можем записать следующим образом

(7.12)

Здесь являются фиктивными переменными неполных путей между промежуточными узлами. Передаточную функцию,T(D), которую иногда называют производящей функцией кода, можно записать как . Решение уравнений состояния (7.12) имеет следующий вид [15, 16].

(7.13)

Передаточная функция этого кода показывает, что имеется один путь с расстоянием 5 до нулевого вектора, два пути — с расстоянием 6, четыре — с расстоянием 7. Вообще, существуют пути с расстоянием l+5 до нулевого вектора, причем l = 0,1,2,… . Просвет df кода является весовым коэффициентом Хэмминга члена наименьшего порядка разложения T(D). В данном случае df=5. Для оценки пространственных характеристик при большой длине кодового ограничения передаточную функцию T(D) использовать нельзя, поскольку сложность T(D) растет с увеличением длины кодового ограничения как степенная функция.

Рис. 7.17. Диаграмма состояний с обозначенными расстояниями до нулевого пути

С помощью передаточной функции можно получить более подробную информацию, чем при использовании лишь расстояния между различными путями. В каждую ветвь диаграммы состояний введем множитель L так, чтобы показатель L мог служить счетчиком ветвей в любом пути из состояния а = 00 в состояние е = 00. Более того, мы можем ввести множитель N во все ветви переходов, порожденных входной двоичной единицей. Таким образом, после прохождения ветви суммарный множитель N возрастает на единицу, только если этот переход ветви вызван входной битовой единицей. Для сверточного кода, описанного на рис. 7.3, на перестроенной диаграмме состояний (рис. 7.18) показаны дополнительные множители L и N. Уравнения (7.12) теперь можно переписать следующим образом.

(7.14)

Передаточная функция такой доработанной диаграммы состояний будет следующей.

(7.15)

Таким образом, мы можем проверить некоторые свойства путей, показанные на рис. 7.16. Существует один путь с расстоянием 5 и длиной 3, который отличается от нулевого пути одним входным битом. Имеется два пути с расстоянием 6, один из них имеет длину 4, другой — длину 5, и оба отличаются от нулевого пути двумя входными битами. Также есть пути с расстоянием 7, из которых один имеет длину 5, два — длину 6 и один — длину 7; все четыре пути соответствуют входной последовательности, которая отличается от нулевого пути тремя входными битами. Следовательно, если нулевой путь является правильным и шум приводит к тому, что мы выбираем один из неправильных путей, то в итоге получится три битовые ошибки.

Рис. 7.18. Диаграмма состояний с обозначением расстояния, длины и числа входных единиц

7.4.1.1. Возможности сверточного кода в коррекции ошибок

В главе 6 при изучении блочных кодов говорилось, что способность кода к коррекции ошибок, t, представляет собой количество ошибочных кодовых символов, которые можно исправить в каждом блоке кода путем декодирования по методу максимального правдоподобия. В то же время при декодировании сверточных кодов способность кода к коррекции ошибок нельзя сформулировать так лаконично. Из уравнения (7.11) можно сказать, что при декодировании по принципу максимального правдоподобия код способен исправить t ошибок в пределах нескольких длин кодового ограничения, причем «несколько» — это где-то от 3 до 5. Точное значение длины зависит от распределения ошибок. Для конкретного кода и ошибочной комбинации длину можно ограничить с использованием методов передаточной функции. Такое ограничение будет описано позднее.

7.4.2. Систематические и несистематические сверточные коды

Систематический сверточный код — это код, в котором входной k—кортеж фигурирует как часть выходного n-кортежа ответвляющегося слова, соответствующего этому k—кортежу. На рис. 7.19 показан двоичный систематический кодер со степенью кодирования 1/2 и К=3. Для линейных блочных кодов любой несистематический код можно преобразовать в систематический с такими же пространственными характеристиками блоков. При использовании сверточных кодов это не так. Это означает, что сверточные коды сильно зависят от просвета; при построении сверточного кода в систематической форме при данной длине кодового ограничения и степени кодирования максимально возможное значение просвета снижается.

Рис. 7.19. Систематический сверточный кодер (степень кодирования 1/2, К=3)

В табл. 7.1 показан максимальный просвет при степени кодирования 1/2 для систематического и несистематического кодов с К от 2 до 8. При большой длине кодового ограничения результаты отличаются еще сильнее [17].

Таблица 7.1. Сравнение систематического и несистематического просветов, степень кодирования 1/2

Источник:. A. J. Viteibi and J. К. Omura. Principles of Digital Communication and Coding, McGraw-Hill Book Company, New-York, 1979, p. 251.

7.4.3. Накопление катастрофических ошибок в сверточных кодах

Катастрофическая ошибка возникает, когда конечное число ошибок в кодовых символах вызывает бесконечное число битовых ошибок в декодированных данных. Мэсси (Massey) и Сейн (Sain) указали необходимые и достаточные условия для сверточного кода, при которых возможно накопление катастрофических ошибок. Условием накопления катастрофических ошибок для кода со степенью кодирования 1/2, реализованного на полиномиальных генераторах, описанных в разделе 7.2.1, будет наличие у генераторов общего полиномиального делителя (степени не менее единицы). Например, на рис. 7.20, а показан кодер с К = 3, степенью кодирования 1/2, со старшим полиномом и младшим .

(7.16)

Генераторы и имеют общий полиномиальный делитель 1+X, поскольку

.

Следовательно, в кодере, показанном на рис. 7.20, а, может происходить накопление катастрофической ошибки.

Рис. 7.20. Кодер, в котором возможно накопление катастрофической ошибки: а) кодер; б) диаграмма состояний

Если говорить о диаграмме состояний кода произвольной степени кодирования, то катастрофическая ошибка может появиться тогда и только тогда, когда любая петля пути на диаграмме имеет нулевой весовой коэффициент (нулевое расстояние до нулевого пути). Чтобы проиллюстрировать это, рассмотрим пример, приведенный на рис. 7.20. На диаграмме (рис. 7.20, б) узел состояния а = 00 разбит на два узла, а и е, как и ранее. Допустим, что нулевой путь является правильным, тогда неправильный путь a b d d… d c e имеет точно 6 единиц, независимо от того, сколько раз мы обойдем вокруг петли в узле d. Поэтому, например, для канала BSC к выбору этого неправильного пути могут привести три канальные ошибки. На таком пути может появиться сколь угодно большое число ошибок (две, плюс количество раз обхода петли). Для кодов со степенью кодирования 1/n можно видеть, что если каждый сумматор в кодере имеет четное количество соединений, петли, которые соответствуют информационным состояниям со всеми единицами, будут иметь нулевой вес, и, следовательно, код будет катастрофическим.

Единственное преимущество описанного ранее систематического кода заключается в том, что он никогда не будет катастрофическим, поскольку каждая петля должна содержать по крайней мере одну ветвь, порождаемую ненулевым входным битом; следовательно, каждая петля должна содержать ненулевой кодовый символ. Впрочем, можно показать [19], что только небольшая часть несистематических кодов (исключая тот, в котором все сумматоры имеют четное количество соединений) является катастрофической.

7.4.4. Границы рабочих характеристик сверточных кодов

Можно показать [8], что вероятность битовой ошибки в бинарном сверточном коде, использующем при декодировании жесткую схему принятия решений, может быть ограничена сверху следующим образом.

(7.17)

где p — вероятность ошибки в канальном символе. Для примера, приведенного на рис. 7.3, T(D,N) получено из T(D, L, N) путем задания L=1 в уравнении (7.15).

(7.18)

и

(7.19)

Объединяя уравнения (7.17) и (7.19), можем записать следующее.

(7.20)

Можно показать, что при когерентной модуляции BPSK в канале с аддитивным белым гауссовым шумом (additive white Gaussian noise — AWGN) вероятность битовой ошибки ограничивается следующей величиной.

(7.21)

где

— отношение энергии информационного бита к спектральной плотности мощности шума,

— отношение энергии канального символа к спектральной плотности мощности шума,

—степень кодирования,

а Q(x) определяется уравнениями (3.43) и (3.44) и приведено в табл. Б.1. Следовательно, для кода со степенью кодирования 1/2 и просветом df=5, при использовании когерентной схемы BPSK и жесткой схемы принятия решений при декодировании, можем записать следующее.

(7.22)

7.4.5. Эффективность кодирования

Эффективность кодирования, представленная уравнением (6.19), определяется как уменьшение (обычно выраженное в децибелах) отношения , требуемого для достижения определенной вероятности появления ошибок в кодированной системе, по сравнению с не кодированной системой с той же модуляцией и характеристиками канала. В табл. 7.2 перечислены верхние границы эффективности кодирования. Они сравниваются с не кодированным сигналом с когерентной модуляцией BPSK для нескольких значений минимальных просветов сверточного кода. Длина кодового ограничения в гауссовом канале с жесткой схемой принятия решений при декодировании изменяется от 3 до 9. В таблице отражен тот факт, что даже при использовании простого сверточного кода можно достичь значительной эффективности кодирования. Реальная эффективность кодирования будет изменяться в зависимости от требуемой вероятности появления битовых ошибок [20].

Таблица 7.2. Верхние границы эффективности кодирования для некоторых сверточных кодов

Источник: V. К. Bhargava, D. Haccoun, R. Matyas and P. Nuspl. Digital Communications by Satellite. John Wiley & Sons, Inc., New York, 1981.

В табл. 7.3 приводятся оценки эффективности кодов, сравниваемые с не кодированным сигналом с когерентной модуляцией BPSK, реализованной аппаратным путем или путем моделирования на компьютере, в гауссовом канале с мягкой схемой принятия решений при декодировании [21]. Не кодированное значение дано в крайнем левом столбце. Из табл. 7.3 можно видеть, что эффективность кодирования возрастает при уменьшении вероятности появления битовой ошибки. Однако эффективность кодирования не может возрастать бесконечно. Как показано в таблице, она имеет верхнюю границу. Эту границу (в децибелах) можно выразить следующим образом.

эффективность кодирования (7.23)

Здесь r— степень кодирования, a df— просвет. При изучении табл. 7.3 обнаруживается также, что (при ) для кодов со степенью кодирования 1/2 и 2/3 более слабые коды имеют тенденцию находиться ближе к верхней границе, чем более мощные коды.

Таблица 7.3. Основные значения эффективности кодирования (в дБ) при использовании мягкой схемы принятия решений в ходе декодирования по алгоритму Витерби

Источник: I. M. Jacobs. Practical Applications of Coding. IEEE Trans. Inf. Theory, vol. IT20, May 1974, pp. 305-310. .

Как правило, декодирование по алгоритму Витерби используется в двоичном входном канале с жестким или мягким 3-битовым квантованным выходом. Длина кодового ограничения варьируется от 3 до 9, причем степень кодирования кода редко оказывается меньше 1/3, и память путей составляет несколько длин кодового ограничения [12]. Памятью путей называется глубина входных битов, которая сохраняется в декодере. После рассмотрения в разделе 7.3.4 декодирования по алгоритму Витерби может возникнуть вопрос об ограничении объема памяти путей. Из этого примера может показаться, что декодирование ответвленного слова в любом узле может происходить сразу, как только останется один выживший путь в этом узле. Это действительно так; хотя для создания реального декодера таким способом потребуется большое количество постоянных проверок после декодирования ответвленного слова. На практике вместо всего этого обеспечивается фиксированная задержка, после которой ответвляющееся слово декодируется. Было показано [12, 22], что информации о происхождении состояния с наименьшей метрикой состояния (с использованием фиксированного объема путей, порядка 4 или 5 длин кодового ограничения) достаточно для получения характеристик декодера, которые для гауссова канала и канала BSC на величину порядка 0,1 дБ меньше характеристик оптимального канала. На рис. 7.21 показаны характерные результаты моделирования достоверности передачи при декодировании по алгоритму Витерби с жесткой схемой квантования [12]. Заметьте, что каждое увеличение длины кодового ограничения приводит к улучшению требуемого значения на величину, равную приблизительно 0,5 дБ, при .

7.4.6. Наиболее известные сверточные коды

Векторы связи или полиномиальные генераторы сверточного кода обычно выбираются исходя из свойств просветов кода. Главным критерием при выборе кода является требование, чтоб код не допускал катастрофического накопления ошибок и имел максимальный просвет при данной степени кодирования и длине кодового ограничения.

(дБ)

Рис. 7.21. Зависимость вероятности появления битовой ошибки от при степени кодирования кодов 1/2; используется когерентная модуляция BPSK в канале ВSС, декодирование согласно алгоритму Витерби и 32-битовая (Перепечатано с разрешения авторов из J. A. Heller and I. M. Jacobs. «Viterbi Decoding for Satellite and Space Communication». IEEE Trans. Commun. Technol., vol. COM19, n. 5, October, 1971, Fig. 7, p. 84 © 1971, IEEE.)

Затем при данном просвете df минимизируется число путей или число ошибочных битов данных, которые представляют путь. Процедуру выбора можно усовершенствовать, рассматривая количество путей или ошибочных битов при df+1, df +2и т.д., пока не останется только один код или класс кодов. Список наиболее известных кодов со степенью кодирования 1/2 при K , равном от 3 до 9, и со степенью кодирования 1/3 при K, равном от 3 до 8, соответствующих этому критерию, был составлен Оденуальдером (Odenwalder) [3, 23] и приводится в табл. 7.4. Векторы связи в этой таблице представляют наличие или отсутствие (1 или 0) соединения между соответствующими регистрами сверточного кодера, причем крайний левый элемент соответствует крайнему левому разряду регистра кодера. Интересно, что эти соединения можно обратить (заменить в указанной выше схеме крайний; левые на крайние правые). При декодировании по алгоритму Витерби обратные соединения приведут к кодам с точно такими же пространственными характеристиками, а значит, и с такими же рабочими характеристиками, как показаны в табл. 7.4.

Таблица 7.4. Оптимальные коды с малой длиной кодового ограничения (степень кодирования 1/2 и 1/3)

Источник: J. P. Odenwalder. Error Control Coding Handbook. Linkabit Corp., San Diego, Calif., July, 15, 1976.

7.4.7. Компромиссы сверточного кодирования

7.4.7.1. Производительность при когерентной передаче сигналов с модуляцией PSK

Возможности схемы кодирования в коррекции ошибок возрастают при увеличении числа канальных символов n, приходящихся на число информационных бит k, или при снижении степени кодирования k/n. В то же время при этом увеличивается ширина полосы пропускания канала и сложность декодера: Выгода низких степеней кодирования при использовании сверточного кода совместно с когерентной модуляцией PSK проявляется в снижении требуемого значения (для широкого диапазона степеней кодирования), что позволяет при заданном значении мощности осуществить передачу на более высоких скоростях или снизить мощность при заданной скорости передачи информации. Компьютерное моделирование показало [16, 22], что при фиксированной длине кодового ограничения снижение степени кодирования с 1/2 до 1/3 в итоге приводит к уменьшению требуемого значения примерно на 0,4 дБ (сложность декодера при этом возрастает примерно на 17%). Для меньших значений степени кодирования улучшение рабочих характеристик по отношению к росту сложности декодирования быстро убывает [22]. В конечном счете, существует точка, по достижении которой дальнейшее снижение степени кодирования приводит к падению эффективности кодирования (см. раздел 9.7.7.2).

7.4.7.2. Производительность при некогерентной ортогональной передаче сигналов

В отличие от модуляции PSK, при некогерентной ортогональной передаче сигналов существует оптимальное значение степени кодирования, приблизительно равное 1/2. Надежность передачи при степени кодирования 1/3, 2/3 и 3/4 хуже, чем при степени кодирования 1/2. При фиксированной длине кодового ограничения и степени кодирования 1/3, 2/3 или 3/4 качество кодирования, как правило, падает на 0,25, 0,5 и 0,3 дБ, соответственно, по сравнению с достоверностью передачи при Степени кодирования 1/2 [16].

7.4.8. Мягкое декодирование по алгоритму Витерби

Для двоичной кодовой системы со степенью кодирования 1/2, демодулятор подает на декодер два кодовых символа за раз. Для жесткого (двухуровневого) декодирования каждую пару принятых кодовых символов можно изобразить на плоскости в виде одного из углов квадрата, как показано на рис. 7.22, а. Углы помечены двоичными числами (0, 0), (0, 1), (1, 0) и (1, 1), представляющими четыре возможных значения, которые могут принимать два кодовых символа в жесткой схеме принятия решений. Аналогично для 8-уровневого мягкого декодирования каждую пару кодовых символов можно отобразить на плоскости в виде равностороннего прямоугольника размером 8×8, состоящего из 64 точек, как показано на рис. 7.22, б. В этом случае демодулятор больше не выдает жестких решений; он выдает квантованные сигналы с шумом (мягкая схема принятия решений).

Основное различие между мягким и жестким декодированием по алгоритму Витерби состоит в том, что в мягкой схеме не используется метрика расстояния Хэмминга, поскольку она имеет ограниченное разрешение. Метрика расстояний, которая имеет нужное разрешение, называется евклидовым кодовым расстоянием, поэтому далее, чтобы облегчить ее применение, соответствующим образом преобразуем двоичные числа из единиц и нулей в восьмеричные числа от 0 до 7. Это можно увидеть на рис. 7.22, в, где соответствующим образом обозначены углы квадрата; теперь для описания любой из 64 точек мы будем пользоваться парами целых чисел от 0 до 7. На рис. 7.22, в также изображена точка 5,4, представляющая пример пары значений кодовых символов с шумом. Представим себе, что квадрат на рис. 7.22, в изображен в координатах (x, y). Каким будет евклидово кодовое расстояние между точкой с шумом 5,4 и точкой без шума 0,0? Оно равно . А если мы захотим узнать евклидово кодовое расстояние между точкой с шумом 5,4 и точкой без шума 7,7? Аналогично .

Рис. 7.22. Декодирование Витерби: а) плоскость жесткой схемы принятия решений; б) 8-уровневая плоскость мягкой схемы принятия решений; в) пример мягких кодовых символов; г) секция решетки кодирования; д) секция решетки декодирования

Мягкое декодирование по алгоритму Витерби, по большей части, осуществляется так же, как и жесткое декодирование (как описывалось в разделах 7.3.4 и 7.3.5). Единственное отличие состоит в том, что здесь не используется расстояние Хэмминга. Поэтому рассмотрим мягкое декодирование, осуществляемое с евклидовым кодовым расстоянием. На рис. 7.22, г показана первая секция решетки кодирования, которая вначале имела вид, приведенный на рис. 7.7. При этом кодовые слова преобразованы из двоичных в восьмеричные. Допустим, что пара кодовых символов, поступившая на декодер во время первого перехода, согласно мягкой схеме декодирования имеет значения 5,4. На рис. 7.22, д показана первая секция решетки декодирования. Метрика (), представляющая евклидово кодовое расстояние между прибывшим ответвленным словом 5,4 и ответвленным словом 0,0, обозначена сплошной линией. Аналогично метрика () представляет собой евклидово кодовое расстояние между поступившим кодовым символом 5,4 и кодовым символом 7,7; это расстояние показано пунктирной линией. Оставшаяся часть задачи декодирования, которая сводится к отсечению решетки и поиску полной ветви, осуществляется аналогично схеме жесткого декодирования. Заметим, что в реальных микросхемах, предназначенных для сверточного декодирования, евклидово кодовое расстояние в действительности не применяется, вместо него используется монотонная метрика, которая обладает сходными свойствами, но значительно проще в реализации. Примером такой метрики является’ квадрат евклидова кодового расстояния, в котором исключается рассмотренная выше операция взятия квадратного корня. Более того, если двоичные кодовые символы представлены биполярными величинами, тогда можно использовать метрику скалярного произведения, определяемую уравнением (7.9). При такой метрике вместо минимального расстояния мы должны будем рассматривать максимальные корреляции.

типа кода исправления ошибок с использованием свертки

В телекоммуникациях, a сверточный код представляет собой тип кода с исправлением ошибок, который генерирует символы четности посредством скользящего применения функции логического полинома к потоку данных. Скользящее приложение представляет собой «свертку» кодировщика над данными, что дает начало термину «сверточное кодирование». Скользящий характер сверточных кодов облегчает декодирование решетчатой ​​диаграммы с использованием неизменной во времени решетчатой ​​диаграммы. Не зависящее от времени решетчатое декодирование позволяет декодировать сверточные коды с мягким решением с максимальной вероятностью и с разумной сложностью.

Возможность выполнять экономичное декодирование с мягким решением с максимальной вероятностью является одним из основных преимуществ сверточных кодов. Это контрастирует с классическими блочными кодами, которые обычно представлены решеткой, изменяющейся во времени, и поэтому обычно декодируются с жестким решением. Сверточные коды часто характеризуются скоростью основного кода и глубиной (или памятью) кодировщика [n, k, K] { displaystyle [n, k, K]}. Базовая кодовая скорость обычно задается как n / k { displaystyle n / k}, где n { displaystyle n}— скорость исходных входных данных. и k { displaystyle k}— скорость передачи данных закодированного потока выходного канала. n { displaystyle n}меньше k { displaystyle k}, потому что канальное кодирование добавляет избыточность во входные биты. Память часто называется «ограничивающая длина» K { displaystyle K}, где вывод является функцией текущего ввода, а также предыдущего K — 1 { displaystyle K-1}входы. Глубина также может быть задана как количество элементов памяти v { displaystyle v}в полиноме или максимально возможное количество состояний кодировщика (обычно: 2 v { displaystyle 2 ^ {v}}).

Сверточные коды часто называют непрерывными. Однако можно также сказать, что сверточные коды имеют произвольную длину блока, а не являются непрерывными, поскольку в большинстве случаев сверточное кодирование в реальном мире выполняется на блоках данных. Сверточно-кодированные блочные коды обычно используют завершение. Произвольную длину блока сверточных кодов можно также противопоставить классическим блочным кодам , которые обычно имеют фиксированную длину блока, которая определяется алгебраическими свойствами.

Кодовая скорость сверточного кода обычно модифицируется с помощью прокалывания символов . Например, сверточный код со скоростью «материнского» кода n / k = 1/2 { displaystyle n / k = 1/2}может быть проколот до более высокой скорости, для например, 7/8 { displaystyle 7/8}просто не передавая часть кодовых символов. Производительность сверточного кода с проколами обычно хорошо масштабируется в зависимости от передаваемой четности. Возможность выполнять экономичное декодирование с мягким решением для сверточных кодов, а также гибкость длины блока и кодовой скорости сверточных кодов делают их очень популярными для цифровой связи.

Содержание

• 1 История
• 2 Где используются сверточные коды
• 3 Сверточное кодирование
• 4 Рекурсивные и нерекурсивные коды
• 5 Импульсная характеристика, передаточная функция и длина ограничения
• 6 Решетчатая диаграмма
• 7 Свободное расстояние и распределение ошибок
• 8 Декодирование сверточных кодов
• 9 Популярные сверточные коды
• 10 Проколотые сверточные коды
• 11 Турбокоды: замена сверточных кодов
• 12 См. Также
• 13 Ссылки
• 14 Внешние ссылки
• 15 Дополнительная литература
  • 15.1 Публикации

История

Сверточные коды были введены в 1955 году Питером Элиасом. Считалось, что сверточные коды можно декодировать с произвольным качеством за счет вычислений и задержки. В 1967 г. Эндрю Витерби определил, что сверточные коды могут быть декодированы с максимальной вероятностью с разумной сложностью с использованием инвариантных во времени декодеров на основе решетчатых диаграмм — алгоритма Витерби. Позже были разработаны другие алгоритмы декодирования на основе решеток, включая алгоритм декодирования BCJR.

Рекурсивные систематические сверточные коды были изобретены Клодом Берро примерно в 1991 году. Эти коды оказались особенно полезными для итеративной обработки, включая обработку составных кодов, таких как турбокоды.

. В терминологии «сверточной» терминологии классический сверточный код может рассматриваться как фильтр с конечной импульсной характеристикой (FIR), в то время как рекурсивный сверточный код может рассматриваться как фильтр с бесконечной импульсной характеристикой (IIR).

Где используются сверточные коды

Этапы канального кодирования в GSM. Блочный кодировщик и проверка четности — часть обнаружения ошибок. Сверточный кодер и декодер Витерби — часть исправления ошибок. Чередование и деинтерлейвинг — разделение кодовых слов увеличивается во временной области и во избежание скачкообразных искажений.

Сверточные коды широко используются для обеспечения надежной передачи данных во многих приложениях, таких как цифровое видео, радио, мобильная связь (например, в сетях GSM, GPRS, EDGE и 3G (до версии 7 3GPP)) и спутниковая связь. Эти коды часто реализуются в конкатенации с кодом жесткого решения, в частности, Рида – Соломона. До турбо-кодов такие конструкции были наиболее эффективными, приближаясь к пределу Шеннона.

Сверточное кодирование

Для сверточного кодирования данных начните с k регистров памяти., каждый из которых содержит один входной бит. Если не указано иное, все регистры памяти начинаются со значения 0. Кодер имеет n сумматоров по модулю 2 (сумматор по модулю 2 может быть реализован с помощью одного логического типа XOR вентиль, где логика: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0), и n генераторных полиномов — по одному для каждого сумматора (см. рисунок ниже). Входной бит m 1 подается в крайний левый регистр. Используя генерирующие полиномы и существующие значения в остальных регистрах, кодер выводит n символов. Эти символы могут быть переданы или проколоты в зависимости от желаемой кодовой скорости. Теперь бит сдвигает все значения регистров вправо (m 1 перемещается в m 0, m 0 перемещается в m — 1) и дождитесь следующего входного бита. Если нет оставшихся входных битов, энкодер продолжает сдвиг, пока все регистры не вернутся в нулевое состояние (завершение битов сброса).

Изображение 1. Нерекурсивный несистематический сверточный кодировщик со скоростью 1/3 с длиной ограничения 3

На рисунке ниже показан кодер со скоростью ⁄ 3 (⁄ n) с длиной ограничения (k) из 3. Полиномы генератора: G 1 = (1,1,1), G 2 = (0,1,1) и G 3 = (1,0,1). Следовательно, выходные биты вычисляются (по модулю 2) следующим образом:

n1= m 1 + m 0 + m −1

n2= m 0 + m −1

n3= m 1 + m −1.

Сверточные коды могут быть систематическими и несистематическими:

• систематический повторяет структуру сообщения перед кодированием

• несистематический изменяет исходную структуру

Несистематические сверточные коды более популярны из-за лучшей помехоустойчивости. Это относится к свободному расстоянию сверточного кода.

• 

  Краткая иллюстрация несистематического сверточного кода.

• 

  Краткая иллюстрация систематического сверточного кода.

Рекурсивные и нерекурсивные коды

Кодировщик на изображении выше является нерекурсивным кодировщиком. Вот пример рекурсивного, и поэтому он допускает структуру обратной связи:

Img.2. Системный рекурсивный сверточный кодер с 8 состояниями скорости 1/2. Используется в качестве составляющего кода в турбо-коде 3GPP 25.212.

Пример кодировщика — систематический, поскольку входные данные также используются в выходных символах (Выход 2). Коды с выходными символами, которые не включают входные данные, называются несистематическими.

Рекурсивные коды обычно систематичны, и, наоборот, нерекурсивные коды обычно несистематичны. Это не строгое требование, а обычная практика.

Пример кодировщика на рис. 2. кодер с 8 состояниями, потому что 3 регистра будут создавать 8 возможных состояний кодера (2). Соответствующая решетка декодера обычно также использует 8 состояний.

Рекурсивные систематические сверточные коды (RSC) стали более популярными благодаря их использованию в турбокодах. Рекурсивные систематические коды также называются псевдосистематическими кодами.

Другие коды RSC и примеры приложений включают:

Рис. 3. Рекурсивный систематический сверточный (RSC) код с двумя состояниями. Также называется «аккумулятором».

Используется для реализации кода LDPC и в качестве внутреннего составляющего кода для последовательных конкатенированных сверточных кодов (SCCC).

Изображение. 4. Рекурсивный систематический сверточный код (RSC) с четырьмя состояниями.

Полезно для SCCC и многомерных турбокодов.

Изображение. 5. Рекурсивный систематический сверточный код (RSC) с шестнадцатью состояниями.

Используется в качестве составляющего кода в турбокодах с низким коэффициентом ошибок для таких приложений, как спутниковые линии связи. Также подходит как внешний код SCCC.

Импульсная характеристика, передаточная функция и длина ограничения

Сверточный кодер называется так, потому что он выполняет свертку входного потока с импульсными характеристиками кодера:

yij знак равно ∑ К знак равно 0 ∞ hkjxi — к = (x * hj) [я], { displaystyle y_ {i} ^ {j} = sum _ {k = 0} ^ { infty} h_ {k} ^ {j} x_ {ik} = (x * h ^ {j}) [i],}

где x — входная последовательность, y — последовательность выхода j, h — импульсная характеристика для выхода j и ∗ { displaystyle {*}}обозначает свертку.

Сверточный кодировщик — это дискретная линейная система, не зависящая от времени. Каждый выход кодировщика может быть описан его собственной передаточной функцией , которая тесно связана с полиномом генератора. Импульсный отклик связан с передаточной функцией через Z-преобразование.

Передаточными функциями для первого (нерекурсивного) кодировщика являются:

Передаточными функциями для второго (рекурсивного) кодировщика являются:

Определить m по

m = max i polydeg ⁡ (H i (1 / z)) { displaystyle m = max _ {i} operatorname {polydeg} (H_ {i} (1 / z)) ,}

где для любой рациональной функции f (z) = P (z) / Q (z) { displaystyle f (z) = P (z) / Q (z) , },

многоугольник ⁡ (е) = макс (град ⁡ (P), град ⁡ (Q)) { displaystyle operatorname {polydeg} (f) = max ( deg (P), deg (Q)) ,}.

Тогда m — это максимум из степеней полинома для H i (1 / z) { displaystyle H_ {i} (1 / z) ,}, а длина ограничения определяется как K = m + 1 { displaystyle K = m + 1 ,}. Например, в первом примере длина ограничения равна 3, а во втором — 4.

Решетчатая диаграмма

Сверточный кодировщик — это конечный автомат. Кодер с n двоичными ячейками будет иметь 2 состояния.

Представьте, что кодировщик (показанный на Рисунке 1 выше) имеет «1» в левой ячейке памяти (m 0) и «0» в правой (m −1). (m 1 на самом деле не является ячейкой памяти, поскольку представляет текущее значение). Обозначим такое состояние цифрой «10». В соответствии с входным битом кодер на следующем повороте может преобразовать либо в состояние «01», либо в состояние «11». Можно видеть, что не все переходы возможны для (например, декодер не может преобразовать из состояния «10» в «00» или даже остаться в состоянии «10»).

Все возможные переходы могут быть показаны ниже:

Изображение 6. Решетчатая диаграмма кодировщика на рис.1. Путь через решетку показан красной линией. Сплошные линии обозначают переходы, когда вводится «0», и пунктирные линии, где вводится «1».

Фактическая закодированная последовательность может быть представлена ​​как путь на этом графике. Один допустимый путь показан красным в качестве примера.

Эта диаграмма дает нам представление о декодировании: если полученная последовательность не соответствует этому графику, значит, она была получена с ошибками, и мы должны выбрать ближайшую правильную (подходящую к графику) последовательность. Настоящие алгоритмы декодирования используют эту идею.

Свободное расстояние и распределение ошибок

Теоретические кривые частоты ошибок по битам для кодированного QPSK (рекурсивного и нерекурсивного, мягкое решение), канала аддитивного белого гауссова шума. Кривые отличаются небольшими размерами из-за приблизительно одинаковых свободных расстояний и весов.

Свободное расстояние (d) — это минимальное расстояние Хэмминга между различными кодированными последовательностями. Корректирующая способность (t) сверточного кода — это количество ошибок, которые могут быть исправлены кодом. Его можно рассчитать как

t = ⌊ d — 1 2 ⌋. { displaystyle t = left lfloor { frac {d-1} {2}} right rfloor.}

Поскольку сверточный код не использует блоки, вместо обработки непрерывного потока битов значение t применяется к количеству ошибок, расположенных относительно близко друг к другу. То есть несколько групп t ошибок обычно можно исправить, если они относительно далеко друг от друга.

Свободное расстояние можно интерпретировать как минимальную длину ошибочного «пакета» на выходе сверточного декодера. Тот факт, что ошибки появляются как «пакеты», следует учитывать при разработке конкатенированного кода с внутренним сверточным кодом. Популярным решением этой проблемы является чередование данных перед сверточным кодированием, чтобы код внешнего блока (обычно Рида – Соломона ) мог исправить большую часть ошибок.

Декодирование сверточных кодов

Теоретические кривые частоты ошибок по битам для некодированного и кодированного QPSK, канала аддитивного белого гауссовского шума. Жесткое решение означает, что декодер ожидает двоичных символов (нулей и единиц); Мягкое решение означает, что декодер ожидает логарифмических отношений правдоподобия.

. Для декодирования сверточных кодов существует несколько алгоритмов. Для относительно небольших значений k алгоритм Витерби используется повсеместно, поскольку он обеспечивает производительность с максимальной вероятностью и обладает высокой степенью распараллеливания. Таким образом, декодеры Витерби легко реализовать в аппаратном обеспечении VLSI и в программном обеспечении на процессорах с наборами инструкций SIMD.

Коды с большей длиной ограничения более практично декодируются с помощью любого из нескольких алгоритмов последовательного декодирования, из которых наиболее известен алгоритм Фано. В отличие от декодирования Витерби, последовательное декодирование не является максимальным правдоподобием, но его сложность лишь немного увеличивается с увеличением длины ограничения, что позволяет использовать строгие коды с большой длиной ограничения. Такие коды использовались в программе Pioneer начала 1970-х годов для Юпитера и Сатурна, но уступили место более коротким кодам, декодированным по Витерби, обычно объединенным с большими кодами исправления ошибок Рида – Соломона которые делают общую кривую коэффициента ошибок по битам более крутой и обеспечивают чрезвычайно низкий уровень остаточных необнаруженных ошибок.

Как алгоритм Витерби, так и алгоритм последовательного декодирования возвращают трудные решения: биты, образующие наиболее вероятное кодовое слово. Приблизительную меру достоверности можно добавить к каждому биту с помощью алгоритма Витерби мягкого вывода. Максимальные апостериорные (MAP) мягкие решения для каждого бита могут быть получены с использованием алгоритма BCJR.

Популярные сверточные коды

Регистр сдвига для (7, [171, 133 ]) сверточный кодовый полином. Ветви:

h 1 = 171 o = [1111001] b { displaystyle h ^ {1} = 171_ {o} = [1111001] _ {b}}

,

h 2 = 133 o = [1011011] b { displaystyle h ^ {2} = 133_ {o} = [1011011] _ {b}}

. Все математические операции должны выполняться по модулю 2. Теоретические кривые частоты ошибок по битам кодированного QPSK (мягкое решение), канал аддитивного белого гауссова шума. Более длинные ограничения дают более мощные коды, но сложность алгоритма Витерби увеличивается экспоненциально с ограничениями длины, ограничивая эти более мощные коды для миссий в дальний космос, где дополнительная производительность легко стоит того. повышенная сложность декодера.

Фактически, в промышленности используются предопределенные структуры сверточных кодов, полученные в ходе научных исследований. Это связано с возможностью выбора катастрофических сверточных кодов (вызывает большее количество ошибок).

Особенно популярный сверточный код, декодируемый по Витерби, используемый по крайней мере с тех пор, как программа Voyager имеет длину ограничения K { displaystyle K}, равную 7 и коэффициент r равен 1/2.

Mars Pathfinder, Mars Exploration Rover и зонд Cassini на Сатурн используют K { displaystyle K}из 15 и коэффициент 1/6; этот код работает примерно на 2 дБ лучше, чем более простой код K = 7 { displaystyle K = 7}за счет 256-кратной сложности декодирования (по сравнению с кодами миссии Voyager).

Сверточный код с длиной ограничения 2 и скоростью 1/2 используется в GSM как метод исправления ошибок.

Проколотые сверточные коды

Сверточные коды с кодовыми скоростями 1/2 и 3/4 (и длина ограничения 7, мягкое решение, 4-QAM / QPSK / OQPSK).

Сверточный код с любой кодовой скоростью может быть разработан на основе полиномиального выбора; однако на практике для достижения требуемой кодовой скорости часто используется процедура исключения. Прокалывание — это метод, используемый для создания кода скорости m / n из «базового» кода с низкой скоростью (например, 1 / n). Это достигается удалением некоторых битов на выходе кодировщика. Биты удаляются в соответствии с матрицей выкалывания. Наиболее часто используются следующие матрицы прокалывания:

Например, если мы хотим создать код со скоростью 2 / 3, используя соответствующую матрицу из приведенной выше таблицы, мы должны взять выходной сигнал базового кодера и передать каждый первый бит из первой ветви и каждый бит из второй. Конкретный порядок передачи определяется соответствующим стандартом связи.

Проколотые сверточные коды широко используются в спутниковой связи, например, в системах INTELSAT и цифровом видеовещании.

Проколотые сверточные коды также используются называется «перфорированный».

Турбокоды: замена сверточных кодов

Турбокод с кодами компонентов 13, 15. Турбокоды получили свое название, потому что декодер использует обратную связь, как двигатель турбо. Перестановка означает то же, что и перемежение. C1 и C2 — рекурсивные сверточные коды. Рекурсивные и нерекурсивные сверточные коды не так сильно различаются по производительности BER, однако рекурсивный тип реализован в сверточных кодах Turbo из-за лучших свойств перемежения.

Простые сверточные коды, декодированные по Витерби, теперь уступают место турбо-коды, новый класс повторяющихся коротких сверточных кодов, которые близко подходят к теоретическим ограничениям, налагаемым теоремой Шеннона с гораздо меньшей сложностью декодирования, чем алгоритм Витерби для длинных сверточных кодов, которые потребуются для такая же производительность. Конкатенация с внешним алгебраическим кодом (например, Рида – Соломона ) решает проблему уровней ошибок, присущих проектам турбокода.

См. Также

• Квантовый сверточный код

Ссылки

• Эта статья включает материалы общественного достояния из документа General Services Administration : «Федеральный стандарт 1037C».

Внешние ссылки

• Он-лайн учебник: теория информации, логический вывод и алгоритмы обучения, автор Дэвид Дж. К. Маккей, обсуждает сверточные коды в главе 48..
• Страница кодов коррекции ошибок (ECC)
• Пояснения к Matlab
• Основы сверточных декодеров для улучшения цифровой связи
• Сверточные коды (MIT)
• Теория информации и кодирование (TU Ilmenau), обсуждает сверточные коды на странице 48.

Дополнительная литература