Repository logo

Masters Degrees (Electronic Engineering)

Permanent URI for this collectionhttps://hdl.handle.net/10413/6868

Browse

Browsing Masters Degrees (Electronic Engineering) by Subject "Algorithms."

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    The hybrid list decoding and Chase-like algorithm of Reed-Solomon codes.
    (2005) Jin, Wei.; Xu, Hongjun.; Takawira, Fambirai.
    Reed-Solomon (RS) codes are powerful error-correcting codes that can be found in a wide variety of digital communications and digital data-storage systems. Classical hard decoder of RS code can correct t = (dmin -1) /2 errors where dmin = (n - k+ 1) is the minimum distance of the codeword, n is the length of codeword and k is the dimension of codeword. Maximum likelihood decoding (MLD) performs better than the classical decoding and therefore how to approach the performance of the MLD with less complexity is a subject which has been researched extensively. Applying the bit reliability obtained from channel to the conventional decoding algorithm is always an efficient technique to approach the performance of MLD, although the exponential increase of complexity is always concomitant. It is definite that more enhancement of performance can be achieved if we apply the bit reliability to enhanced algebraic decoding algorithm that is more powerful than conventional decoding algorithm. In 1997 Madhu Sudan, building on previous work of Welch-Berlekamp, and others, discovered a polynomial-time algorithm for decoding low-rate Reed- Solomon codes beyond the classical error-correcting bound t = (dmin -1) /2. Two years later Guruswami and Sudan published a significantly improved version of Sudan's algorithm (GS), but these papers did not focus on devising practical implementation. The other authors, Kotter, Roth and Ruckenstein, were able to find realizations for the key steps in the GS algorithm, thus making the GS algorithm a practical instrument in transmission systems. The Gross list algorithm, which is a simplified one with less decoding complexity realized by a reencoding scheme, is also taken into account in this dissertation. The fundamental idea of the GS algorithm is to take advantage of an interpolation step to get an interpolation polynomial produced by support symbols, received symbols and their corresponding multiplicities. After that the GS algorithm implements a factorization step to find the roots of the interpolation polynomial. After comparing the reliability of these codewords which are from the output of factorization, the GS algorithm outputs the most likely one. The support set, received set and multiplicity set are created by Koetter Vardy (KV) front end algorithm. In the GS list decoding algorithm, the number of errors that can be corrected increases to tcs = n - 1 - lJ (k - 1) n J. It is easy to show that the GS list decoding algorithm is capable of correcting more errors than a conventional decoding algorithm. In this dissertation, we present two hybrid list decoding and Chase-like algorithms. We apply the Chase algorithms to the KV soft-decision front end. Consequently, we are able to provide a more reliable input to the KV list algorithm. In the application of Chase-like algorithm, we take two conditions into consideration, so that the floor cannot occur and more coding gains are possible. With an increase of the bits that are chosen by the Chase algorithm, the complexity of the hybrid algorithm increases exponentially. To solve this problem an adaptive algorithm is applied to the hybrid algorithm based on the fact that as signal-to-noise ratio (SNR) increases the received bits are more reliable, and not every received sequence needs to create the fixed number of test error patterns by the Chase algorithm. We set a threshold according to the given SNR and utilize it to finally decide which unreliable bits are picked up by Chase algorithm. However, the performance of the adaptive hybrid algorithm at high SNRs decreases as the complexity decreases. It means that the adaptive algorithm is not a sufficient mechanism for eliminating the redundant test error patterns. The performance of the adaptive hybrid algorithm at high SNRs motivates us to find out another way to reduce the complexity without loss of performance. We would consider the two following problems before dealing with the problem on hand. One problem is: can we find a terminative condition to decide which generated candidate codeword is the most likely codeword for received sequence before all candidates of received set are tested? Another one is: can we eliminate the test error patterns that cannot create more likely codewords than the generated codewords? In our final algorithm, an optimality lemma coming from the Kaneko algorithm is applied to solve the first problem and the second problem is solved by a ruling out scheme for the reduced list decoding algorithm. The Gross list algorithm is also applied in our final hybrid algorithm. After the two problems have been solved, the final hybrid algorithm has performance comparable with the hybrid algorithm combined the KV list decoding algorithm and the Chase algorithm but much less complexity at high SNRs.
  • Thumbnail Image
    Item
    Transmit antenna selection algorithms for quadrature spatial modulation.
    (2016) Naidu, Suvigya.; Pillay, Narushan.
    The use of multiple-input multiple-output (MIMO) systems has become increasingly popular due to the demand for high data rate transmissions. One such attractive MIMO system is spatial modulation (SM). SM is an ideal candidate for high data rate transmission as it is able to achieve a high spectral efficiency, whilst maintaining a relatively low receiver complexity. SM completely avoids inter-channel interference and the need for inter-antenna synchronisation. Furthermore, SM requires the existence of only one radio frequency chain. However, the need to increase the spectral efficiency achieved by SM is a topic which continues to garner interest. Quadrature spatial modulation (QSM) was introduced as an innovative SM-based MIMO system. QSM maintains the aforementioned advantages of SM, whilst further increasing the spectral efficiency of SM. However, similar to SM, the need to improve the reliability (error performance) of QSM still exists. One such strategy is the application of a closed-loop technique, such as transmit antenna selection (TAS). In this dissertation, Euclidean distance-based antenna selection for QSM (EDAS-QSM) is proposed. A substantial improvement in the average error performance is demonstrated. However, this is at the expense of a relatively high computational complexity. To address this, we formulate an algorithm in the form of reduced-complexity Euclidean distance-based antenna selection for QSM (RCEDAS-QSM) that is used for the computation of EDAS-QSM. RCEDAS-QSM yields a significant reduction in the computational complexity, whilst preserving the error performance. To further address computational complexity, four sub-optimal, low-complexity, TAS schemes for QSM are investigated, viz. capacity optimised antenna selection for QSM (COASQSM), TAS for QSM based on amplitude and antenna correlation (TAS-A-C-QSM), lowcomplexity TAS for QSM based on amplitude and antenna correlation using the splitting technique (LCTAS-A-C-QSM) and TAS based on amplitude, antenna correlation and Euclidean distance for QSM (A-C-ED-QSM). Amongst the sub-optimal algorithms, A-C-ED-QSM provides superior error performance. While the computational complexity of A-C-ED-QSM is higher than the other sub-optimal, lowcomplexity schemes, there is a significant reduction in the computational complexity compared to the optimal RCEDAS-QSM. However, this is at the expense of error performance. Hence, clearly a trade-off exists between error performance and computational complexity, and is investigated in detail in this dissertation.