ABSTRACT

A new non-binary decoding method, which is called Yaletharatalhussein decoding algorithm, is designed and implemented for decoding non-binary convolutional codes which is based on the trellis diagram representing the convolutional encoder. Yaletharatalhussein decoding algorithm outperforms the Viterbi algorithm and other algorithms in its simplicity, very small computational complexity, decoding reliability for high states TCM codes that suitable for Fourth-Generation (4G), decreasing errors with increasing word length, and easy to implement with real-time applications. The proposed Yaletharatalhussein decoding algorithm deals with non-binary error control coding of the convolutional and TCM codes. Convolutional codes differ from block codes in that a block code takes a fixed message length and encodes it, whereas a convolutional code can encode a continuous stream of data, and a hard-decision decoding can easily be realized using the Yaletharatalhussein algorithm. The idea of non-binary codes has been extended for symbols defined over rings of integers, which outperform binary codes with only a small increase in decoding complexity. The simulation results show that the performance of the nonbinary TCM-based Yaletharatalhussein algorithm outperforms the binary and non-binary decoding methods.

1. Introduction

When conventional coding techniques are introduced in a transmission system, the bandwidth of the coded signal after modulation is wider than that of the uncoded signal for the same information rate and the same modulation scheme. In fact, the encoding process requires a bandwidth expansion that is inversely proportional to the code rate, being traded for a coding gain. On the other hand, the available radio spectrum is limited and the communication capacity needs cannot be met without a significant increase in spectral efficiency [1]. Digital signals are more reliable in a noisy communications environment. They can usually be detected perfectly, as long as the noise levels are below a certain threshold. Digital data can easily be encoded in such a way as to introduce dependency among a large number of symbols, thus enabling a receiver to make a more accurate detection of the symbols. This is called error control coding. The design of signal processing algorithms for digital data seems much easier than designing analog signal processing algorithms. The abundance of such digital algorithms, including error control and correction techniques, combined with their ease of implementation in very large-scale integrated (VLSI) circuits, has led to many successful applications of error control coding in practice.

Advances in coding, such as turbo [2] and low density parity check codes [3], made it feasible to approach the Shannon capacity limit [4] in systems with a single antenna link. Significant further advances in spectral efficiency are available through increasing the number of antennas at both the transmitter and the receiver [5-7].

Further performance gains can be achieved by using non-binary codes in the coded modulation scheme, but with an increase in the decoding complexity [8]. Nonbinary codes are the most commonly used error-correcting codes and can be found in optical and magnetic storage, high-speed modems and wireless communications.

Among the various Coded Modulation (CM) schemes, TCM [9] was originally designed for transmission over Additive White Gaussian Noise (AWGN) channels. TTCM [10] is a more recent joint coding and modulation scheme which has a structure similar to that of the family of binary turbo codes, but employs TCM schemes as component codes. Both TCM and TTCM employ set-partitioning-based constellation mapping [11], while using symbol-based turbo interleavers and channel interleavers. Another CM scheme, referred to as BICM [12], invokes bit-based channel interleavers in conjunction with grey constellation mapping. Furthermore, iteratively decoded BICM [13] using set partitioning was also proposed.

2. Rings of Integers

If the two binary operations “+” and “·” are allowed then a ring can be defined. A ring must have the following conditions; associativity, distributivity, and commutativity under addition. The ring is called a commutative ring if it also has commutativity under multiplication. If the ring has a multiplicative identity 1 then it is called a ring with identity. An example of a ring is the ring of integers under modulo-q addition and multiplication, where q is the cardinality of the ring. For example, is defined as {0, 1, 2, 3}.

It is easy to see that the elements obey the three definitions of a ring. Also, all the elements commute under multiplication and the multiplicative identity element 1 is present, meaning that is a commutative ring with identity. Tables 1 and 2 show the addition and multiplication tables respectively of the ring of integers [14].

The set of all polynomials with coefficients defined in forms a ring under the addition and multiplication operations.

3. Non-Binary TCM

Convolutional codes and TCM codes are based on rings of integers modulo-M. Due to the similarities between M-PSK signal sets and the algebraic structure of rings of integers modulo-M, modulo-M ring-TCM codes are the natural linear codes for M-PSK modulation.

TCM Based on Rings of Integers

The general structure of a ring-TCM encoder suitable for M-PSK modulation, assuming that m information bits are transmitted per baud, with, is shown in Figure 1. This ring-TCM encoder works as follows [15]:

1) First, m + 1 information bits, b_i, are mapped into a modulo-M symbol, , according to a mapping function f (for instance, f can be a Gray mapping function).

2) Next, m modulo-M symbols are introduced into a linear multi-level convolutional encoder (MCE), which generates m + 1 modulo-M coded symbols,.

3) Finally, each one of these coded symbols is associated with a signal of the M-PSK signal set and is sent to the channel.

As a total of m + 1 modulo-M coded symbols are transmitted per single trellis branch, ring-TCM codes can be considered as -dimensional TCM codes.

4. A 4-State Ring-TCM Code Defined over 4

A good 4-state ring-TCM code over is shown in Figure 2 and this would be used in this research work [16].

Where each of the input and output of Figure 2 represent the elements of the ring of integers modulo-4, , and all addition arithmetic operations satisfy the properties of the ring of integers modulo-4 addition. The delay block represents the constraint length (number of memory elements, i.e., in this case there is only one memory element).

5. Yaletharatalhussein Decoding Algorithm

The Yaletharatalhussein non-binary decoding algorithm is proposed in this paper for decoding non-binary convolutional codes. The decoder for the non-binary convolutional code finds the most probable sequence of data bits given the received sequence y:

(1)

where y is the set of code symbols c observed through noise. The above equation can be solved using the Yale-

tharatalhussein algorithm, explained later.

The application of the Yaletharatalhussein algorithm to decoding non-binary convolutional codes is based on the logic similarities and differences, at each time instant, between the noisy received bits, i.e., y, and the sequence of output data bits, i.e., u, of the non-binary state table that represents the non-binary convolutional encoder sequential logic states.

This principle states that creating a state vector containing binary logic states, which represents the similarities and differences between y symbols associated with each u bits at the current time instant, and then searching for a minimum logic state in this vector to determine the state node number with its order bit for using in the next time instant of searching strategy method, in one hand, and for recovering the transmitted code word in the other hand. In this case, the decoding method is independent on the trellis diagram representing the non-binary convolutional encoder.

The basic steps in the Yaletharatalhussein non-binary decoding algorithm can be described as follows:

1) Determine the logic state vectors that represent the logic similarities and differences between the first block noisy received symbols, y, associated with each output data bits vector of all states, u, at each time instant (i.e., t = 0 to t = K), according to the following condition:

(2)

where:

: represents a non-binary operation defined above;

y: represents noisy received symbols with K, word length and;

u: represents a vector of non-binary output data bits for all states at the current time instant associated with y symbol, and the length of this vector is, where, is the number of non-binary states of the convolutional encoder. Thus the vector h would contain a set of ones and zeros (i.e., binary vector).

2) Begin at time t = K, at state 0.

3) Search about the zero logic state in h vector at this current time instant (i.e., t = K), and then store both number of state node and the order of the determined zero logic state to detect the transmitted bit at this time instant (i.e., x at t = K) from the input vector in the state table.

4) Decrement time t (i.e., t = K − 1) and return to Step 3, but search about the zero logic state in the h vector locations only, that have order the same as the state node number that stored in Step 3. Then the transmitted bit at this time instant (i.e., x at t = K − 1) can be detected from the input vector in the state table. In this case the searching about zero locations would be decreased.

5) Continue this process until all the symbols in the code word have been detected at the final time instant (t = 0).

An example of applying the Yaletharatalhussein decoding algorithm for the non-binary -ring-TCM encoder shown in Figure 2, the encoder takes an input sequence bits x of length K bits and for each bit produces two coded bits denoted as and.

For simplicity, assuming K = 5 bits, and noiseless data vector is received at the non-binary decoder input. If the input message to the non-binary -ring-TCM encoder is:

x = [1 2 3 3 3], then the coded bits and are described below:

= [1 2 3 3 3], and = [2 1 1 0 3].

Now, from the state table [16], the initial input vectors w’s and output data vectors u’s are shown below, where each script number indicates time instant k:

and

The steps of applying the Yaletharatalhussein decoding algorithm are described below:

1) To find h vectors, using the relation (4.15) then:

h₁ = [1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1]h₂ = [1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1]h₃ = [1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1]h₄ = [0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1]h₅ = [1 0 1 1]2) Search in h₅ = [1 0 1 1], about zero element, this leads to [1; 0; 1; 1], this assigned in state node number = 2, and bit order = 1. Thus the transmitted bit in w₅ = [0 1 2 3; 3 0 1 2; 2 3 0 1; 1 2 3 0], is x₅ = 3.

3) Search in h₄ = [0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1], about zero element in the 2^nd location of each state of h₄, this leads to [0 1 0 1; 1 1 1 1; 1 0 1 0; 1 1 1 1], and assigned in state node number = 3, and bit order = 10. Thus the transmitted bit in w₄ = [0 1 2 3 3 0 1 2 2 3 0 1 1 2 3 0], is x₄ = 3.

4) Search in h₃ = [1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1], about zero element in the 3^rd location of each state of h₃, this leads to [1 1 1 1; 1 0 1 0; 1 1 1 1; 0 1 0 1], and assigned in state node number = 4, and bit order = 15. Thus the transmitted bit in w₃ = [0 1 2 3 3 0 1 2 2 3 0 1 1 2 3 0], is x₃ = 3.

5) Search in h₂ = [1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1], about zero element in the 4^th location of each state of h₂, this leads to [1 1 1 1; 1 0 1 0; 1 1 1 1; 0 1 0 1], and assigned in state node number = 2, and bit order = 8. Thus the transmitted bit in w₂ = [0 1 2 3 3 0 1 2 2 3 0 1 1 2 3 0], is x₂ = 2.

6) Search in h₁ = [1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1], about zero element in the 2^nd location of each state of h₁, this leads to [1 0 1 0; 1 1 1 1; 0 1 0 1; 1 1 1 1], and assigned in state node number = 2, and bit order = 2. Thus the transmitted bit in w₁ = [0 1 2 3 3 0 1 2 2 3 0 1 1 2 3 0], is x₁ = 1.

7) The transmitted bits sequence form the non-binary -ring-TCM encoder is, x = [1 2 3 3 3], which is similar to the given input message.

To enhance the Yaletharatalhussein decoding method, a schematic design of the -ring-TCM-based Yaletharatalhussein algorithm is shown in Figure 3. The source information bits are first encoded and modulated by the -ring-TCM encoder and modulater.

The symbols are then transmitted via the channel, and the received noise-contaminated symbols are forwarded to the demodulator.

The recovered signal is then demodulated and the outputs are fed to the -ring-TCM-decoder which used the Yaletharatalhussein algorithm for recovering the most likely transmitted information bits.

The -ring-TCM demodulator and decoder-based Yaletharatalhussein decoding algorithm can be represented by a flowchart as shown in Figure 4. The flow chart inside the dashed lines represents the Yaletharatalhussein decoding algorithm.

6. Simulation Results

The performances of the -Ring-TCM-PAM schemebased Yaletharatalhussein algorithm communicating over

the AWGN channel are shown in Figure 5.

The performances of the -Ring-TCM-PAM schemebased Yaletharatalhussein decoding algorithm and the schemes of work [16] can be summarized in Table 3, where the coding gains are defined as the difference, expressed in decibels, at BERs of 10⁻⁵ and 10⁻³. The performance of the best scheme in Table 3 is (printed in bold), since the performance comparison shows that the -ring-TCM-PAM scheme-based Yaletharatalhussein algorithm outperforms the 4-state ring-TCMbased Viterbi algorithm by the gains (5.5 dB and 8.7 dB) at the BERs (10⁻³ and 10⁻⁵) respectively.

7. Conclusions and Future Works

A novel non-binary decoding method, which is called Yaletharatalhussein decoding algorithm, is proposed for decoding non-binary convolutional and TCM codes, which independent on the trellis diagram representing the nonbinary convolutional encoder, as in Viterbi algorithm.

The Yaletharatalhussein algorithm employed a harddecision decoding, which needed less computational complexity over the soft-decision MLD of Viterbi algorithm.

In Yaletharatalhussein algorithm, the code words are detected instantaneously through searching in the developed state vectors, while in Viterbi algorithm, the hamming distances between numbers and transition metrics are calculated and a comparison between competitive accumulated metrics is done for every state of the trellis diagram.

Computational complexity of the Yaletharatalhussein algorithm is much smaller than complexity of the Viterbi algorithm, since in Viterbi algorithm, a survivor path of the lowest accumulated metrics is calculated and repeated for every state of the trellis diagram.

In Yaletharatalhussein algorithm, the massages are decoded in blocks reached to 1,000,000 symbols as seen in simulation results, while in a typical Viterbi code,

messages are decoded in blocks of only about 200 bits or so, whereas in turbo coding the blocks are on the order of 16K bits long. Non-binary TCM codes outperform binary TCM codes with a small increase in decoding complexity. The use of non-binary TCM codes led to reduction in the effective input block length, since each m bits of binary information correspond to one non-binary symbol for q = 2^m, and thus non-binary system can be used with high number of symbols.

A future work can be done by applying the Yaletharatalhussein decoding algorithm to higher order rings of integers such as, , , , and, and then study the error performance and bandwidth efficiency of the system for different types of modulation schemes and orders: 8, 16, 32, and 64.

REFERENCES