Complexity of coding and decoding algorithms

The using of code control ability depends on decoding algorithm. By full decoding use all possibilities to correct errors following from properties of a code. According to Shannon fundamental theorem the error-control codes used for correction of channel errors should get out long enough. However with growth of a code word length n increases complexity of realization procedures both of encoding and decoding that causes difficulty of practical realization of codecs. In the coding theory of along with estimations of code error-control ability of can estimate complexity of realization of encoding/decoding procedureswhich can be realized by software or hardware. Thus as argument of complexity function the length of a codeword n should act.

coding complexity of a block codes C _cod with use of generator matrix (n, k) code with a size nk = n ²(1 – R _code) usually estimate in the value which is proportional to number of elements of the generator matrix

C _cod = nk = n ²(1 – R _code). (6.3)

The decoding algorithms appear more difficult. Among them it is considered to be the most difficult full-search algorithm according to which the decoder by the full searchingcompares the received code word with the set of all possible words and the decision on that transmitted from the allowed word which appears on the minimum distance from the received word (decoding by a minimum distance) passes. It is considered to be complexity of full-search decoding algorithm proportional to quantity of all possible code words to volume of full search:

C _decod = mⁿ = 2 ⁿ. (6.4)

It is said that complexity of full-search decoding increases «as an exponent» with growth of code length. Clearly, that full-search decoding algorithms are practically difficult for realising for long codes.