Device-to-Device (D2D) assisted coded caching is a promising approach to improve the communication efficiency over networks. However, the basic D2D coded caching scheme requires a subpacketization size that increases exponentially with the number of users. This is infeasible since the file size needs to be extremely large in the server. It is desirable to design a scheme that achieves a small subpacketization size while keeping the rate low. Recently, D2D placement delivery array (DPDA) was proposed to address the high subpacketization issue of D2D coded caching. This paper investigates the design of DPDA from the perspectives of linear algebraic and additive combinatorics. It is shown that a linear subspace possessing certain property can be employed in the design of DPDA. Based on this, a new D2D coded caching scheme with a subquadratic subpacketization size is derived through shortening the binary Reed-Muller codes. In order to obtain a D2D coded caching scheme with a linear subpacketization size, a new combinatorial structure called proper disjoint 3-term arithmetic progression (3-AP) free set is further introduced, and a deterministic algorithm for constructing it is provided with a polynomial complexity. Both the theoretical and numerical results reveal that the proposed schemes have a superior performance in terms of subpacketization size or transmission rate.

For polar codes, perturbing received information can enhance the successive cancellation (SC) decoding performance. This is an effective approach for realizing low-latency yet high performance for long polar codes, since all the perturbation-enhanced SC (PSC) decoding can be performed in parallel. This paper provides theoretical insights into soft information perturbation, revealing that the PSC decoding can be equivalently interpreted as perturbing thea posteriorilog-likelihood ratios (LLRs) of information bits. Such a revelation leads to the design of an improved PSC (IPSC) decoding that yields a lower perturbation complexity. By better utilizing the decodinga posterioriLLRs, a set of possibly erroneous estimations can be formed and further perturbed, resulting in the proposed hybrid PSC (HPSC) decoding. During each new SC decoding attempt, it takes turns to flip the first erroneous bit by introducing a biased perturbation, while the subsequent erroneous estimations are corrected through random perturbations. Our simulation results validate that, for various codeword lengths and rates, the proposed IPSC decoding can achieve a similar performance as the conventional PSC decoding, but yield a significantly reduced perturbation complexity. With the same number of decoding attempts, the proposed HPSC decoding outperforms several state-of-the-art SC-based decoding, such as the thresholded SC-flip (TSCF) decoding and the dynamic SC-flip (DSCF) decoding.

Algebraic codes are important in communication and storage systems where soft information is limited and decoding efficiency is critical. Among them, algebraic-geometric (AG) codes are promising candidates to replace the widely used Reed-Solomon (RS) codes. However, their more sophisticated algebraic structure results in high decoding complexity, hindering their practical application. This paper proposes a novel interpolation-based algebraic soft decoding (ASD) for one of the most important AG codes - Hermitian codes. Given a designed maximum decoding output list size (OLS), the interpolation module is constructed, and the decoding is formulated as finding a desired Gröbner basis of this module that contains the interpolation polynomial. The re-encoding transform (ReT) specifically designed for ASD is proposed, enabling the modified basis reduction (BR) interpolation to achieve lower complexity. The ReT is formulated by defining Lagrange interpolation polynomials over the Hermitian function fields and appropriately choosing the re-encoding points. By exploiting the linear code property, the ReT transforms a subset of interpolation points to have zeroz-coordinates, which allows a common factor to be extracted from the module basis polynomials, thereby simplifying the interpolation. This paper further proposes an improved ReT employing more re-encoding points. It enables the common factor to have a greater degree, yielding a more significant complexity reduction. This also leads to an early termination for the decoding. Theoretical analysis and numerical results demonstrate that the two proposed ReT schemes efficiently facilitate the ASD for Hermitian codes.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. Generalized integrated interleaved (GII) codes have an enhanced error-correction capability over an array of interleaves which are also known as component codes. With BCH component codes, the GII codes are called GII-BCH codes. The existing Chase decoding of GII-BCH codes can achieve a significant coding gain over hard-decision decoding of the codes, but at the cost of complexity. On the other aspect, the existing theoretical characterization of the codes' Chase decoding performance remains complex, and even partially numerical. This paper introduces a new theoretical characterization for Chase decoding performance of the codes, offering a simpler and computationally friendly closed form expression. Based on it, this paper further proposes a new Chase decoding method for GII-BCH codes, namely the enhanced Chase decoding (ECD). The ECD can identify the decoding rounds which are more likely to declare a decoding failure and prioritize allocating the flipped positions to them. Our simulation results show that with a similar maximum number of test-vectors, the ECD can achieve an improved performance over the existing Chase decoding.

This paper proposes a new interpolation-based algebraic soft decoding (ASD) for Hermitian codes. The interpolation is realized through basis reduction (BR) that is facilitated by the re-encoding transform (ReT). The ReT is formulated by defining Lagrange interpolation polynomials over the Hermitian function fields and choosing proper re-encoding points. It transforms the interpolation points, which can lead to a reduced BR interpolation complexity. With a designed decoding output list size (OLS), the interpolation module basis can be formulated. The ReT results in polynomials of the module basis having a common factor. It can be extracted from the polynomials, resulting in a simpler basis reduction. An enhanced ReT is further proposed. It enables the basis polynomials having a common factor with a greater degree, yielding a more significant complexity reduction. Numerical results show that both of the two proposed ReT can facilitate the ASD for the advanced decoding of Hermitian codes.

For polar codes, the bit-flipping strategy can significantly improve performance of its successive cancellation (SC) decoding. However, the gain derived from SC-flip (SCF) decoding diminishes as the codeword length increases. Addressing this issue, this paper proposes a novel hybrid perturbation-based SC (HPSC) decoding. If the initial SC decoding fails, the algorithm will generate multiple SC decoding attempts, each of which introduces stochastic perturbations to the received symbols. By soft information perturbations, the SC decoding can divert from the initial erroneous estimation and converge to the intended one. Our simulation results show that the proposed HPSC decoding consistently yields stable coding gains over various codeword lengths and rates. With the same number of decoding attempts, the HPSC decoding outperforms the thresholded SCF (TSCF) decoding. Moreover, it can achieve a similar performance as the cyclic redundancy check (CRC) aided SC list (CA-SCL) decoding, without any path sorting and expansion requirements.

U-UV codes are good-performing short-to-medium length channel codes constructed by several algebraic component codes. They are coupled through the (U|U+V) recursive structure. With eBCH codes as the component codes, U-UV codes can be interpreted as the generalized concatenated codes (GCCs) with inner polar codes and outer eBCH codes. With ordered statistic decoding (OSD) for the outer codes, the successive cancellation list (SCL) decoding of U-UV codes can outperform that of the cyclic redundancy check (CRC)-polar codes. But the complexity of the OSD grows exponentially with its decoding order, rendering the worst-case decoding complexity of U-UV codes being too high. This paper proposes the SCL2decoding of eBCH based U-UV codes, in which both the inner codes and outer codes are decoded by the SCL decoding. In particular, the eBCH outer codes are interpreted as the concatenation of a polar code and a linear transform. Consequently, it can be decoded by SCL decoding with a sub-quadratic complexity. Our simulation results show that for eBCH based U-UV codes, SCL2decoding can reduce the binary operations required in the existing (outer) OSD-(inner) SCL decoding by an order of magnitude, while maintain the decoding performance.

For polar codes, perturbing received information can enhance the error-correction performance of successive cancellation (SC) decoding. This is an effective approach for realizing low-latency yet high decoding performance for long polar codes, since each perturbation-enhanced SC (PSC) decoding can be performed in parallel. This paper provides theoretical insights into the soft information perturbation. It first reveals that the PSC decoding can be equivalently viewed as perturbing the SC decoding a posteriori log-likelihood ratio (LLR) of the information bits. Such a revelation enables us to reduce the perturbation complexity by only targeting the information bits, resulting in an improved PSC (IPSC) decoding. By better utilizing the a posteriori LLRs, a set of possibly erroneous estimations can be formed to be perturbed, further reducing the perturbation complexity. Our simulation results show that, for various codeword lengths, the proposed IPSC decoding can achieve a similar performance as the PSC decoding, while yielding significant perturbation complexity reduction.

Generalized integrated interleaved (GII) codes enable an enhanced error-correction over an array of interleaves (component codes) within a single block. Error-correction performance of GII codes can be further improved by utilizing the soft received information. The existing Chase decoding of GII-BCH codes can achieve a significant coding gain over the hard-decision decoding, but at the cost of complexity. Meanwhile, the existing theoretical characterization of its Chase decoding performance remains complex and partially empirical. This paper introduces a new theoretical characterization for Chase decoding performance of GII-BCH codes. With this characterization, it further proposes two new soft-decision decoding methods for GII-BCH codes, including the enhanced Chase decoding (ECD) and the enhanced concatenated Chase decoding (ECCD). They both identify the decoding rounds that are more likely to declare a decoding failure and prioritize allocating the flipped positions to those rounds. In particular, the latter utilizes codewords of a linear block code to cover the least reliable or the second least reliable positions, further improving the error-correction performance over the ECD. With a similar number of test-vectors, both the ECD and ECCD can outperform the existing Chase decoding for GII-BCH codes.

This paper proposes the low-complexity Chase (LCC) decoding for Hermitian codes, which is facilitated by both the improved interpolation and root-finding. By identifying$\eta $unreliable received symbols,$2^{\eta }$test-vectors are formulated, each of which is decoded by the interpolation based Guruswami-Sudan (GS) algorithm. To reduce both the interpolation complexity and latency, the re-encoding transform (ReT) is introduced through defining the Lagrange interpolation polynomials over the Hermitian function fields. The interpolation polynomial is further computed through module basis reduction (BR) that yields the Gröbner basis that contains the desired polynomial. The BR interpolation exhibits a greater parallelism than the conventional Kötter’s interpolation. Moreover, the$2^{\eta }$root-finding processes are facilitated by estimating the codewords directly from the interpolation outcomes. It eliminates the re-encoding computation for identifying the most likely candidate from the decoding output list. It is also shown that the average LCC decoding complexity can be further reduced by both assessing the re-encoding outcome and decoding the test-vectors progressively. They can achieve an early decoding termination once a codeword that satisfies the maximum likelihood (ML) criterion is found. Our simulation results demonstrate that the decoding complexity and latency can be significantly reduced over the existing decoding algorithms.

This paper proposes two low-complexity Chase (LCC) decoding algorithms for elliptic codes, which are realized by K¨otter’s interpolation and the basis reduction (BR) interpolation, respectively. They are both developed from the perspective of computing the Gr¨obner bases of the interpolation modules. By identifying η unreliable symbols, 2η decoding testvectors are formulated and the corresponding interpolation modules can be defined. The re-encoding transform (ReT) is further introduced to facilitate the interpolation. The LCC-K ¨otter decoding performs interpolation for the common elements, producing an intermediate outcome shared by all test-vectors. The desired Gr¨obner basis w.r.t. each test-vector can be obtained in a binary tree growing fashion. The new interpolation process can start from intermediate nodes of the previously interpolated paths, resulting in a low complexity. But the decoding latency cannot be contained. In contrast, the LCC-BR decoding performs the common computation in basis construction, which partly substantiates the bases for all interpolation modules. The subsequent basis construction and reduction can be performed in parallel. Besides a low complexity, it offers a latency advantage over the LCC-K¨otter decoding. The decoding complexity and latency are analyzed and verified numerically. The LCC decoding performance are also presented, demonstrating their advantage over both the Guruswami-Sudan decoding and the algebraic soft decoding. Moreover, the performance advantage of elliptic codes over the Reed-Solomon (RS) codes is demonstrated.

Ordered statistics decoding (OSD) can achieve near maximum likelihood (ML) decoding performance for BCH codes. However, Gaussian elimination (GE) that delivers the systematic generator matrix of the code has an uncompromised latency. Addressing this challenge, this paper proposes a low-latency OSD (LLOSD) for BCH codes. Since BCH codes are binary subcodes of Reed-Solomon (RS) codes, codeword candidates can be produced using the RS systematic generator matrix, whose entries can be generated in parallel. By eliminating the non-binary codeword candidates and identifying the ML codeword, the LLOSD yields a lower latency as well as complexity than the OSD. It is shown that the LLOSD can be interpreted as generating the codeoword candidates through systematic encoding of a punctured BCH codeword, explaining its low-complexity feature. Moreover, the segmented variant is proposed to further facilitate the LLOSD. In order to decode long BCH codes, a hybrid soft decoding (HSD) is finally proposed. It integrates the LLOSD and the algebraic Chase decoding that can effectively provide extra TEPs for the LLOSD, enhancing the decoding performance. Both the complexity and performance of the proposed decoding are analyzed, demonstrating their advantage over the relevant state-of-the-art decoding.

Algebraic Chase decoding (ACD) is an effective soft-decision decoding approach for elliptic codes. By identifying η least reliable symbols, 2η test-vectors are formulated, each of which will be decoded through the interpolation and rootfinding processes. To improve the ACD of elliptic codes, this paper proposes the generalized re-encoding transform (GReT) and improved root-finding (IRF) for reducing the decoding complexity. A systematic encoding method for elliptic codes with an arbitrary information set is proposed to re-encode the received symbols with the most reliable information set (MRIS). By assessing the likelihood of the re-encoded codeword, the ACD can be early terminated, saving the decoding computation for all test-vectors. The GReT, which allows arbitrary selection of re-encoding positions, is further proposed for the ACD in reducing the interpolation complexity. It transforms the interpolation polynomials and points using the Gröbner basis associated to the MRIS. Furthermore, the IRF is proposed to reduce the root-finding complexity that also grows exponentially with η. It can directly determine the codeword candidates from the interpolation outcomes and eliminate the restoration of interpolation polynomials in the context of GReT. Our numerical results show that the proposed GReT and IRF significantly reduce the interpolation and root-finding complexity of ACD, respectively. Moreover, with the early termination facilitated by the re-encoding with the MRIS, the average ACD complexity decreases as the channel conditions improve.

This paper proposes an efficient root-finding algorithm for the interpolation-based unique decoding of one-point elliptic and hyperelliptic codes. Instead of finding a message polynomial, it directly computes a codeword from the interpolation polynomial. It first determines the error positions through the error locator polynomial that is contained in the interpolation polynomial. Subsequently, the corresponding codeword symbols are determined based on the root-finding equation that is reformulated as a linear system of univariate polynomials. The proposed algorithm demonstrates superiority to the Roth-Ruckenstein (RR) algorithm, especially in the scenarios that the decoder is required to output a codeword and the re-encoding transform (ReT) technique is employed.

This paper proposes a reduced complexity ordered statistics decoding (OSD) algorithm for linear block codes, the namely order skipping (OS)-OSD algorithm. An approximated correlation distance lower bound (CDLB) is derived by utilizing likelihood of the received symbols over the least reliable positions (LRPs). It enables the assessment of whether the higher-order decoding can yield a more likely codeword estimation. If not, they can be skipped. Error-correction performance of the OSOSD is analyzed. In particular, the decoding error probability of OS-OSD with order one is theoretically characterized. Our simulation results verify that the OS-OSD can achieve a significant complexity reduction over the state-of-the-art OSD without compromising the decoding performance.

Due to the high parallelism of belief propagation (BP) decoding, it is considered as a promising solution for the decoding latency challenge of long polar codes. However, the error-correction performance of the classical BP decoding is inferior to that of the successive cancellation (SC) and the SC list (SCL) decoding. In this paper, an adaptive BP (ABP) decoding algorithm is proposed to bridge this performance discrepancy. It iteratively adjusts the a priori log-likelihood ratios (LLRs) of error-prone bits, which can be efficiently detected using the frozen and information processing elements (FIPEs). Moreover, a novel low-complexity FIPE-based early termination criterion (ETC) is proposed to further reduce the decoding complexity. It functions when all the frozen bits in the FIPEs are successfully decoded with stable LLR magnitudes. Our numerical results show that for the (1024,512) polar code, the ABP decoding outperforms the classical BP decoding by 0.3 dB at the frame error rate (FER) of 10–4over the additive white Gaussian noise (AWGN) channel. It can also achieve up to 78.5% latency reduction over the fast simplified SC (FSSC) decoding, while maintaining the same performance. The proposed ETC also exhibits a lower hardware complexity over the existing G-matrix criterion.

The NAND flash memory channel is corrupted by different types of noises, such as the data retention noise and the wear-out noise, which lead to unknown channel offset and make the flash memory channel non-stationary. In the literature, machine learning-based methods have been proposed for data detection for flash memory channels. However, these methods require a large number of training samples and labels to achieve a satisfactory performance, which is costly. Furthermore, with a large unknown channel offset, it may be impossible to obtain enough correct labels. In this paper, we reformulate the data detection for the flash memory channel as a transfer learning (TL) problem. We then propose a model-based deep TL (DTL) algorithm for flash memory channel detection. It can effectively reduce the training data size from 106samples to less than 104samples. Moreover, we propose an unsupervised domain adaptation (UDA)-based DTL algorithm using moment alignment, which can detect data without any labels. Hence, it is suitable for scenarios where the decoding of error-correcting code fails and no labels can be obtained. Finally, a UDA-based threshold detector is proposed to eliminate the need for a neural network. Both the channel raw error rate analysis and simulation results demonstrate that the proposed DTL-based detection schemes can achieve near-optimal bit error rate (BER) performance with much less training data and/or without using any labels.

Coded caching is an effective technique to reduce the data transmission load by exploiting the cache contents across the network. However, most coded caching schemes are designed for static networks that consist of only a placement phase and a delivery phase. In practice, a network maybe dynamic with multiple rounds of placement and delivery phases, and the number of users within the network may vary. In these dynamic networks, a conventional coded caching scheme may lead to the undesired updates at the existing users’ cache contents. This paper proposes a centralized coded caching scheme for dynamic networks that can support multiple rounds with newly joining users. It prevents cache contents of the existing users from being updated, extending the service duration of cache devices. Further recognizing the need of information security in coded caching, the considered dynamic networks are featured by two constraints: 1) the library files must be kept secure from a wiretapper who has access to the shared link; 2) any subset of users cannot obtain information from the demands of other users. This consideration leads to another dynamic coded caching scheme that ensures information security. It is shown that the proposed schemes can yield a small subpacketization level and achieve a good rate-memory tradeoff.

This paper proposes a novel shift-sum decoding method for non-binary cyclic codes, which only requires finite field operations but yields advanced decoding performance. Using the cyclically different minimum-weight dual codewords (MWDCs) and their proper shifts, a frequency matrix can be obtained as a reliability metric for identifying the error positions and magnitudes. By analyzing the statistical distributions of the matrix entries, the rationale for the shift-sum decoding’s advanced error-correction capability is revealed. Based on this decoding method, a hard-decision iterative shift-sum (HISS) decoding algorithm is first proposed. It can correct errors beyond half of the code’s minimum Hamming distance. By further utilizing the reliability information obtained from the channel, a soft-decision iterative shift-sum (SISS) decoding algorithm is then proposed to improve the decoding performance. Both the HISS and the SISS algorithms are realized only with polynomial multiplications and numerical comparisons, which are hardware-friendly. To further improve the error-correction performance, the HISS and SISS algorithms can be integrated in a Chase decoding mechanism for handling the test-vectors. Simulation results on Reed-Solomon (RS) and non-binary BCH (NB-BCH) codes show that the proposed algorithms yield a competent decoding and complexity performances in comparison with the existing decoding algorithms.

Non-volatile memory (NVM) channels suffer from unknown offsets due to the presence of various impairments of the memory devices. Machine learning based methods have been proposed for data detection for NVMs under unknown channel offsets. However, the existing methods require a large number of training samples and labels to achieve a satisfactory data detection performance, which will result in large read latency and more power consumption. In this paper, we formulate a deep learning based data detection framework as a transfer learning problem. A deep transfer learning (DTL) based data detection scheme is proposed to reduce the number of required training samples and labels. The optimal symbol error rate is also derived as the performance benchmark by assuming that the perfect channel knowledge is known to the detector. Our experiment results demonstrate that the proposed DTL-based data detection scheme can achieve near-optimal performance with the training data size being reduced by two orders of magnitude compared with the original deep learning-based detector.

Polarization-adjusted convolutional (PAC) codes can approach the normal approximation (NA) bound using Fano decoding. However, when the received information is unreliable, the decoding may linger over the decoding tree, resulting in both a high decoding complexity and latency. This paper proposes the modified PAC (MPAC) codes and their hybrid Fano-SC (HFSC) decoding that prevents an impractical decoding. For the MPAC codes, only a subset of the information bits undergo the convolutional transform. Its output then concatenates the remaining information bits for the inner polar transform. Consequently, the Fano decoding and the successive cancellation (SC) decoding are deployed to recover the information bits that have undergone the convolutional transform and the remaining information bits, respectively. Both the MPAC code design and the HFSC decoding insight are studied. Our simulation results show that with a limited complexity, HFSC decoding of MPAC codes can yield a better performance-complexity tradeoff than Fano decoding of PAC codes and SC list (SCL) decoding of cyclic redundancy check (CRC)-polar codes.

Coded caching is an effective technique to reduce the data transmission load by exploiting the cache contents across the network. However, most coded caching schemes are designed for static networks that consist of only a placement phase and a delivery phase among a constant number of users. In practice, a network maybe dynamic with multiple rounds of placement and delivery phases, and the number of users may vary. In such dynamic networks, a conventional coded caching scheme may lead to the undesired content updates at the users’ cache, which is caused by the newly joining users. This paper proposes a centralized coded caching scheme for dynamic networks that can support multiple rounds and accommodate the newly joining users during this process. It prevents cache contents of the existing users from being updated. It is shown that the proposed scheme can yield a reduced subpacketization level and achieve a good rate-memory tradeoff.

Coded caching is an effective technique to decongest the amount of traffic in the backhaul link. In such a scheme, each file hosted in the server is divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user’s cache. However, the implementation complexity of this scheme increases with the number of packets. It is important to design a scheme with a small subpacketization level and a relatively low transmission rate. Recently, placement delivery array (PDA) was proposed to address the subpacketization bottleneck of coded caching. This paper investigates the design of PDA from a new perspective, i.e., the injective arc coloring of regular digraphs. It is shown that the injective arc coloring of a regular digraph can yield a PDA with the same number of rows and columns. Based on this, a new class of regular digraphs are defined and the upper bounds on the injective chromatic index of such digraphs are derived. Consequently, four new coded caching schemes with a linear subpacketization level and a relatively small transmission rate are proposed, one of which generalizes the existing scheme for the scenario with a more flexible number of users.

U-UV codes were recently proposed as a competent short-to-medium length coding scheme. With well designed component codes, U-UV codes can outperform similar rate cyclic redundancy check (CRC)-polar codes with the successive cancellation (SC) and the SC list (SCL) decoding. In order to improve the coded transmission spectral efficiency, this paper proposes the bit-interleaved coded modulation (BICM) scheme with U-UV codes as the channel codes. A bit interleaver structure is proposed to facilitate the component code rate allocation based on the polarized subchannel capacities. Under the BICM paradigm, the component code rates can be allocated by first estimating the modulation subchannel capacities, then adjusting based on the finite length rates and the equal error probability rule. Theoretical performance bounds and their approximations on decoding error rates are further analyzed. It provides the theoretical benchmarks for our simulations and guides the optimized design of the coded modulation scheme. Finally, simulation results of the U-UV coded BICM scheme are provided to demonstrate its error-correction competency. It can outperform the relevant bit-interleaved polar coded modulation (BIPCM) scheme.

This paper proposes two interpolation-based algebraic Chase decoding for elliptic codes. It is introduced from the perspective of computing the Gröbner basis of the interpolation module, for which two Chase interpolation approaches are utilized. They are Kötter’s interpolation and the basis reduction (BR) interpolation. By identifying η unreliable symbols, 2ηdecoding test-vectors are formulated, and the corresponding interpolation modules can be defined. The re-encoding further helps transform the test-vectors, facilitating the two interpolation techniques. In particular, Kötter’s interpolation is performed for the common elements of the test-vectors, producing an intermediate outcome that is shared by the decoding of all test-vectors. The desired Gröbner bases w.r.t. all test-vectors can be obtained in a binary tree growing fashion, leading to a low complexity but its decoding latency cannot be contained. In contrast, the BR interpolation first performs the common computation in basis construction which is shared by all interpolation modules, and then conducts the module basis construction and reduction for all test-vectors in parallel. It results in a significantly lower decoding latency. Finally, simulation results are also presented to demonstrate the effectiveness of the proposed Chase decoding.

Coded caching is an effective technique to utilize multicasting opportunities to reduce the data transmission load in cached networks. In such a scheme, each file in the data center or library is usually divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user’s cache. However, the implementation complexity of this scheme increases with the number of packets. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. Recently, a combinatorial structure called placement delivery array (PDA) was proposed as an effective tool to design coded caching schemes with a low subpacketization level. This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs). It generalizes the existing construction, making it suitable to the scenario with a more flexible memory size. Based on the proposed PDA construction, a new coded caching scheme with the coded placement is further proposed. It is shown that the proposed schemes can yield a lower subpacketization level or transmission rate over the benchmark schemes.

This paper proposes a low-latency ordered statistics decoding (OSD) algorithm for BCH codes. The OSD latency is mainly caused by Gaussian elimination (GE) that produces a systematic generator matrix of the code. Considering BCH codes is binary subcodes of Reed-Solomon (RS) codes, we show that the BCH codeword candidates can be produced through the systematic generator matrix of the corresponding RS code. The systematic generator matrix of an RS code can be formed by generating the linearly independent RS codewords in parallel, replacing the GE process and enabling a low OSD latency. This paper further proposes a segmented variant that facilitates the decoding by reducing the number of test error patterns (TEPs). Complexity of the proposed OSD is also analyzed. Our simulation results show that the proposed decoding can achieve a similar performance as the conventional OSD, but with a lower decoding complexity. The decoding latency can be reduced over the conventional OSD substantially.

This paper proposes the algebraic soft decoding (ASD) for one-point elliptic codes, where the interpolation problem is solved from the perspective of module basis reduction. In ASD, the interpolation polynomial$\mathcal {Q}(x, y, z)$is the minimum candidate of a Gröbner basis. Based on a multiplicity matrix, an interpolation ideal can be defined. With the decoding output list size, an equivalent interpolation module can be led to. By further defining the set of interpolation points, a sequence of modules from the elliptic curve coordinate ring can be obtained. Based on the Lagrange interpolation functions over elliptic function field, a basis of the interpolation module can be constructed. The desired Gröbner basis that contains$\mathcal {Q}$can be determined by reducing the module basis. Re-encoding transform (ReT) is further introduced to reduce the basis reduction complexity. It is also shown that the interpolation can be facilitated by assessing the degree of the Lagrange interpolation polynomials. The decoding complexity is analyzed, which is verified by numerical results. That shows the advantage of this interpolation technique over the conventional Kötter’s interpolation. The ASD performance of elliptic codes is also presented.

Coded caching is an emerging technique to reduce the data transmission load during the peak-traffic times. In such a scheme, each file in the data center or library is divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user’s cache. However, the implementation complexity of this scheme increases with the number of packets. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. Recently, a combinatorial structure called placement delivery array (PDA) was proposed as an effective tool to design coded caching schemes with a relatively low subpacketization level. This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs), which generalizes the existing construction but with a more flexible memory size. Based on the proposed PDA construction, an effective transform is further proposed to enable a coded caching scheme to achieve a smaller subpacketization level. Moreover, two new coded caching schemes with the coded placement are derived. It is shown that the proposed schemes can yield a lower subpacketization level or transmission rate over the benchmark schemes.

This paper proposes the U-UV structured codes with BCH codes as its components. This coding construction will lead to polarized subchannels and rate of each component code can be designed accordingly. The component code will be decoded by the ordered statistic decoding (OSD), yielding multiple decoding outcomes. Integrated in a successive cancellation (SC) decoding mechanism, SC-list (SCL) decoding of the U-UV codes is further proposed. Our simulation results will show that over the short-to-medium length regime, SCL decoding of a BCH based U-UV code can outperform that of a similar rate polar code.

This paper proposes algebraic soft decoding (ASD) for one-point elliptic codes, where the interpolation is realized through the perspective of obtaining a Gröbner basis. The desired interpolation polynomial$\mathcal{Q}(x, y, z)$is the minimum candidate in the basis. This work shows how to obtain such a Gröbner basis. Based on an interpolation multiplicity matrix M, an interpolation ideal$\mathcal{I}_{\mathrm{M}}$can be defined. With a predefined decoding output list size (OLS)$l\ (l\geq\deg_{z}\mathcal{Q})$, an equivalent interpolation module$\mathcal{I}_{\mathrm{M}, l}$can be led to. By further defining the Lagrange interpolation functions, a basis of the interpolation module can be constructed. The desired Gröbner basis can be obtained by reducing this module basis. Finally, the decoding complexity is also analyzed.

Using the minimum weight dual codewords (MWDCs) of a cyclic code, the shift-sum decoding can correct errors beyond half of the code's minimum Hamming distance. It utilizes the frequency of the syndrome polynomials' coefficients to identify the erroneous positions and correct the errors. This paper analyzes the plausibility of the shift-sum decoding for both binary and non-binary cyclic codes. It first determines the probability distributions of the frequency of the syndrome polynomials' coefficients as well as their expected values for the erroneous and non-erroneous positions. Based on these characterizations, this work further provides an analysis for the iterative shift-sum decoding, unveiling the statistical rationale on the shift-sum decoding's capability of correcting errors beyond the half distance bound.

This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for one-point elliptic codes, in which the interpolation is realized by the module basis reduction (BR). Elliptic codes are a kind of algebraic-geometric (AG) codes with a genus of one. Over the same finite field, they have a greater codeword length than Reed-Solomon (RS) codes, capable of correcting more errors. The GS decoding consists of interpolation and root-finding, while the former that determines the interpolation polynomial$\mathcal {Q}(\text {x}, \text {y}, \text {z})$dominates the decoding complexity. By defining the Lagrange interpolation function over an elliptic function field, a basis of the interpolation module can be constructed. The desired Gröbner basis that contains$\mathcal {Q}(\text {x}, \text {y}, \text {z})$can be determined by reducing the constructed basis. This is namely the BR interpolation and it requires less finite field arithmetic operations than the conventional Kötter’s interpolation, facilitating the GS decoding. Re-encoding transform (ReT) is further introduced to facilitate the BR interpolation. This work also shows that both the BR interpolation and its ReT variant will have a lower complexity as the code rate${k}/{n}$increases, where n and${k}$are the length and dimension of the code, respectively. Our numerical results demonstrate the complexity advantage of the BR interpolation over Kötter’s interpolation, and the performance advantage of elliptic codes over RS codes.

This paper proposes the low-complexity Chase (LCC) decoding using basis reduction (BR) interpolation for Reed-Solomon (RS) codes, namely the LCC-BR algorithm. With received soft information, a number of decoding test-vectors are formulated. The LCC-BR algorithm first constructs a common basis which will be utilized by the following individual basis constructions of all test-vectors. This eliminates the redundant computation in BR interpolation, resulting in a low decoding complexity. Moreover, the LCC-BR algorithm can decode each test-vector in parallel, lowering the decoding latency. This paper further proposes the progressive LCC-BR (PLCC-BR) algorithm that decodes the test-vectors sequentially and terminates once the intended message is found. This progressive decoding is realized without additional memory cost. Simulation results show the complexity and latency advantages of the proposed algorithms over the other benchmark algorithms.

This paper proposes a novel shift-sum decoding scheme for non-binary cyclic codes. Using minimum-weight dual codewords and their cyclic shifts, a reliability measure can be yielded as an indicator for the error position and the error magnitude. Based on this shift-sum decoding concept, a harddecision iterative decoding algorithm is proposed, which can correct errors beyond half of the code’s minimum Hamming distance. By utilizing reliability information from the channel, a soft-decision iterative decoding algorithm is further introduced to improve the decoding performance. These two shift-sum based iterative decoding algorithms are realized with polynomial multiplication and integer (or real number) comparisons, which are hardware-friendly. Simulation results on Reed-Solomon codes and non-binary BCH codes show the decoding potential of the proposed algorithms.

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. In this paper, we introduce a systematic design to eliminate 4-cycles in a coupled protograph. Further using a quasi-cyclic (QC) lifting, we introduce a procedure for constructing QC-SC-LDPC codes of girth at least eight. This can be interpreted as a multi-stage graph lifting process that yields a greater flexibility in designing QC-SC-LDPC codes with a large girth than previous approaches. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random constructions. Finally, we determine the minimum coupling width required to eliminate 4-cycles in a coupled protograph.

The interpolation based algebraic soft decoding yields a high decoding performance for Reed-Solomon (RS) codes with a polynomial-time complexity. Its computationally expensive interpolation can be facilitated using the module structure. The desired Gröbner basis can be achieved by reducing the basis of a module. This paper proposes the low-complexity Chase (LCC) decoding algorithm using this module basis reduction (BR) interpolation technique, namely the LCC-BR algorithm. By identifying η unreliable symbols, 2ηdecoding test-vectors will be formulated. The LCC-BR algorithm first constructs a common basis which will be shared by the decoding of all test-vectors. This eliminates the redundant computation in decoding each test-vector, resulting in a lower decoding complexity and latency. This paper further proposes the progressive LCC-BR algorithm that decodes the test-vectors sequentially and terminates once the maximum-likelihood decision decoding outcome is reached. Exploiting the difference between the adjacent test-vectors, this progressive decoding is realized without any additional memory cost. Complexity analysis shows that the LCC-BR algorithm yields a lower complexity and latency, especially for high rate codes, which will be validated by the numerical results.

The Koetter-Vardy (KV) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes but with a high computational cost. This paper studies the lowcomplexity KV decoding that utilizes the module minimization (MM) interpolation technique, namely the KV-MM algorithm. A module contains bivariate polynomials that interpolate all the prescribed points with their multiplicity. Presenting the module basis as a matrix over univariate polynomials, row operation further reduces it into the Gröbner basis, delivering the interpolated polynomial. We will also introduce the re-encoding transformed KV-MM algorithm by giving an explicit construction for the module basis. This research shows MM interpolation yields a remarkably lower complexity for KV decoding than the conventional Koetter's interpolation, especially for high rate codes. This is also true when the re-encoding transform is applied. This finding is a rectification of some earlier results.

In this paper, we present a new class of spatially coupled low-density parity-check (SC-LDPC) codes, which are constructed by sending codewords of LDPC block code (LDPCBC) in a block Markov superposition transmission (BMST) manner. Different from the conventional SC-LDPC codes, the proposed SC-LDPC codes can have encoder/decoder implemented with the basis of the hardware components of the corresponding LDPC-BCs. The proposed SC-LDPC codes are also a special class of BMST-LDPC codes. Distinguished from other types of BMST codes, BMST-LDPC codes have lower error floors even with an encoding memory of one and hence have lower decoding latency. Also different from the original BMST codes, partial superposition is implemented to alleviate error propagation. To analyze the bit error rate (BER) performance, we present the genie-aided (GA) bounds, which can be obtained by simulation or estimated from the performance of the basic code. Numerical results are presented to validate our analysis and demonstrate the performance advantage of the BMST-LDPC codes over the LDPC-BCs.

The interpolation based algebraic decoding for Reed-Solomon (RS) codes can correct errors beyond half of the code's minimum Hamming distance through constructing a minimum polynomial Q(x,y) and finding its y-roots. The progressive algebraic soft decoding (PASD) constructs Q(x, y) with a progressively enlarged y-degree and terminates once the message is decoded, adapting the decoding capability and computation to the channel. This paper proposes the re-encoding transformed PASD algorithm, in which Q(x, y) is progressively constructed by the low-complexity module minimization (MM) technique. Re-encoding transform (ReT) results in a common divisor for polynomials of the image of the submodule basis. It can be removed, leading to a simpler image expansion and reduction. Consequently, Q(x,y) is constructed through the isomorphic image of the progressively enlarged submodule basis. Our complexity analysis characterizes the complexity reduction brought by the transform and shows high rate codes benefit a greater complexity reduction.

Advancing from Reed-Solomon (RS) codes, the length of algebraic-geometric (AG) codes can exceed the size of finite field, resulting in a greater error-correction capability. However, this is realized with a genus penalty. Usually, they are not maximum distance separable (MDS) codes. One-point elliptic codes are either MDS or almost MDS, yielding a good tradeoff between codeword length and distance property. This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for elliptic codes. To define the interpolated polynomial Q(x, y, z), an explicit construction for the zero basis of each affine point is introduced. Given an interpolation multiplicity m, the error-correction capability τmand the maximum decoding output cardinality lmof the GS algorithm are characterized. An efficient interpolation algorithm is further presented for elliptic codes. Performance of elliptic codes is shown for the first time, demonstrating their advantage over RS codes.

The interpolation‐based algebraic decoding for Reed–Solomon (RS) codes can correct errors beyond half of the code's minimum Hamming distance. Using soft information, the algebraic soft decoding (ASD) further improves the decoding performance. This paper presents a unified study of two classical ASD algorithms, the algebraic Chase decoding and the Koetter‐Vardy decoding. Their computationally expensive interpolation is solved by the module minimisation (MM) technique which consists of basis construction and basis reduction. Compared with Koetter's interpolation, the MM interpolation yields a smaller computational cost for the two ASD algorithms. Re‐encoding transform is further applied to reduce the decoding complexity by reducing the degree of module generators. Based on assessing the degree of module seeds, a complexity reducing approach is introduced to further facilitate the two ASD algorithms. Computational cost of the two algorithms as well as their re‐encoding transformed variants will be analysed. Performance of the two ASD algorithms will be compared under decoding expenditure benchmark, providing more practical insights of their applications.

This paper proposes multilevel Reed-Solomon (MRS) codes and their iterative multistage soft decoding (IMSD) for visible light communication (VLC), realizing both high decoding performance and transmission spectrum efficiency. The proposed IMSD algorithm decodes the MRS codes level-by-level through iterating either hard decisions or extrinsic information of RS coded bits. Each level RS decoding is realized by cascading the adaptive belief propagation (ABP) algorithm that produces the extrinsic information and the Berlekamp-Massey (BM) algorithm that estimates the codeword. The earlier level decoding provides better a priori information for the later ones. A complexity reducing IMSD (CR-IMSD) algorithm is also proposed to facilitate the decoding. This paper further investigates a joint design of color-shift keying (CSK) constellation and the MRS code, optimizing the decoding performance. The CSK constellation is designed by considering both the set partitioning (SP) criterion and the harmonic mean of constellation's minimum squared Euclidean distance (MSED). The MRS codes are further designed using the capacity and the equal error probability rules. Our simulation results show that the IMSD algorithm achieves significant iterative decoding gains. The performance of the designed MRS code is 0.3 dB away from the capacity limit at the bit error rate (BER) of 10-9.

The algebraic soft-decision decoding (ASD) of Reed–Solomon (RS) codes yields a competent decoding performance with a polynomial-time complexity. But its complexity remains high due to the interpolation that generates the interpolation polynomial$Q(x,y)$. The progressive ASD (PASD) algorithm has been introduced to construct$Q(x,y)$with a progressively enlarged$y$-degree, adjusting its error-correction capability and computation to the received information. However, this progressive decoding is realized at the cost of memorizing the intermediate decoding information. To overcome this challenge, this paper proposes a new PASD algorithm which is evolved from the ASD using module minimization (MM) interpolation. Polynomial$Q(x,y)$can be constructed through the image of the progressively enlarged submodule basis without the need of memorizing the intermediate decoding information, eliminating the memory cost of progressive decoding. The MM interpolation also attributes to a remarkably lower complexity than the original PASD algorithm. Furthermore, a complexity reducing variant is proposed based on assessing the degree of Lagrange interpolation polynomials. We also analyze the complexity of the proposed decoding methods and reveal their channel dependent feature. Our simulation results show their low-complexity and advanced decoding performances.

The algebraic soft decoding (ASD) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes. However, its complexity remains high making it impractical. This is due to the interpolation. The progressive ASD (PASD) algorithm adjusts the decoding computation to the reliability of received information. Its interpolation generates the intended polynomial Q(x, y) with a progressively enlarged y- degree, and terminates once the message is decoded. But this progressive decoding is realized at the cost of memorizing the intermediate decoding information. This paper proposes a new PASD algorithm, in which the progressive interpolation is realized by the module minimization (MM) technique. Polynomial Q(x, y) can be found through the progressively enlarged images of submodule's basis without memorizing the intermediate decoding information. The MM interpolation also grants it a significantly lower complexity than the original PASD algorithm that uses Koetter's interpolation. Our simulation results will verify its advanced decoding performance and low-complexity feature.

This paper proposes an iterative multistage soft decoding (IMSD) for multilevel Reed-Solomon (MRS) codes, achieving both high decoding performance and transmission spectrum efficiency. The proposed IMSD algorithm performs soft-in soft-out (SISO) decoding of each level RS code in a multistage mechanism. The RS decoding is realized by cascading the adaptive belief propagation (ABP) algorithm that produces the extrinsic probabilities for the coded bits and the Berlekamp-Massey (BM) algorithm that estimates the message. The earlier decoding outputs help a later one by providing better a priori information for its decoding. Armed with the IMSD algorithm, the MRS codes are designed by analyzing the equivalent channel capacity of each coded level, leading to the heterogeneous structure for MRS codes. Our simulation results demonstrate the performance advantages of the IMSD algorithm as well as the designed MRS codes.

Algebraic-geometric (AG) codes have good error-correction capability due to their generally large code word length. However, their decoding remains complex, preventing practical applications. Addressing the challenge, this paper proposes two interpolation-based low-complexity Chase (LCC) decoding algorithms for one of the most popular AG codes-Hermitian codes. By choosing η unreliable symbols and realizing them with the two most likely decisions, 2ηdecoding test-vectors can be formulated. The first LCC algorithm performs interpolation for the common elements of the test-vectors, producing an intermediate outcome that will be shared by the uncommon element interpolation. It eliminates the redundant computation for decoding each test-vector, resulting in a low-complexity. With an interpolation multiplicity of one, the decoding is further facilitated by removing the requirement of pre-calculating the Hermitian curve's corresponding coefficients. The second LCC algorithm is an adaptive variant of the first algorithm, where the number of test-vectors is determined by the reliability of received information. When the channel condition improves, it can reduce the complexity without compromising the decoding performance. Simulation results show that the both LCC algorithms outperform a number of existing algebraic decoding algorithms for Hermitian codes. Finally, our complexity analysis will reveal the proposals' low-complexity feature.

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. This paper introduces a systematic design of SC-LDPC codes to eliminate 4-cycles in the coupled photograph. Using a quasi-cyclic (QC) lifting, we obtain QC-SC-LDPC codes of girth at least eight. Coupling a chain of block protographs implies spreading edges from one protograph to the others. Our protograph-based design can be viewed as guiding the edge spreading and also the graph-lifting process. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random designs.

Spatially coupled low-density parity-check (SC-LDPC) codes can achieve capacity approaching performance with a small message recovery latency due to the sliding window decoding (SWD). Using a partial Tanner graph, the SWD performs iterative message passing until the average error probability Peof the target symbols falls below a threshold or the maximum iteration number is reached. However, Pedoes not decrease monotonically as iteration progresses. This implies the symbol likelihoods that were yielded when the decoding terminates may not be optimal for making decisions. Therefore, this paper proposes an improved SWD (ISWD) for SC-LDPC codes. The proposal monitors the achievable minimum of Peand stores its associated likelihoods, so that when the decoding terminates the target symbols will be estimated based on the stored likelihoods. Our research shows the ISWD is able to enhance the decoding performance, especially in the waterfall region. It exhibits an asymptotic convergence to the SWD performance. A complexity reducing variant of the ISWD is also proposed to facilitate the decoding but at the cost of error-correction performance.

Spatial diversity is an effective method to mitigate the effects of fading, and when used in conjunction with low-density parity-check (LDPC) codes, it can achieve excellent error-correcting performance. Noise added at each branch of the diversity combiner is generally assumed to be additive white Gaussian noise, but there are many applications where the received signal is impaired by noise with a non-Gaussian distribution. In this paper, we derive the exact bit-error probability of different linear combining techniques on Rayleigh fading channels with impulsive noise, which is modeled using symmetric alpha-stable distributions. The relationship for the signal-to-noise ratios of these linear combiners is derived and then different non-linear detectors are presented. A detector based on the bi-parameter Cauchy-Gaussian mixture model is used and shows near-optimal performance with a significant reduction in complexity when compared with the optimal detector. Furthermore, the threshold signal-to-noise ratio of LDPC codes for different combining techniques on these channels is derived using density evolution and an estimation of the waterfall performance of LDPC codes is derived that reduces the gap between simulated and asymptotic performance.

This paper proposes an interpolation based progressive algebraic Chase decoding (PACD) algorithm for Reed-Solomon (RS) codes. Based on the received information, 2η (η > 0) interpolation test-vectors are constructed. They are ordered using a reliability function, assessing their potential of yielding the intended message. The decoding is performed progressively granting priority to decode the test-vectors that are more likely to yield the intended message, and it will be terminated once the intended message is found. In the proposal, the decoding of a later test-vector utilizes the interpolation information that is generated during the decoding of the earlier ones. It results in the binary tree that represents the evolution of the interpolated polynomial sets growing in a depth-first-search manner. The PACD algorithm has the advantage of adapting its decoding computation to the channel condition, leveraging the average decoding complexity. This channel dependent feature will be validated by our simulation results which show that the PACD algorithm is less complex than various interpolation based algebraic decoding algorithms. We will also demonstrate that it can achieve a high RS decoding performance.

Algebraic-geometric (AG) codes have long been considered as a possible candidate to replace Reed-Solomon (RS) codes. However, their decoding remains complex and infeasible to implement. Addressing this challenge, our paper proposes a low-complexity Chase (LCC) decoding algorithm for the most popular class of AG codes - Hermitian codes. The LCC decoding is realised by formulating decoding test-vectors, which allows Koetter's interpolation to be performed for common and uncommon elements. This reduces redundant computations and also removes the need to calculate the corresponding coefficients of a Hermitian curve, thus facilitating message recovery. Our simulation results show that significant coding gains can be achieved over the conventional Koetter-Vardy (KV) soft decoding algorithm, but with a much lower computational cost. Moreover, we also show that in comparison with RS codes of a similar length, Chase decoding has a more significant impact on enhancing the performance of Hermitian codes.

This study proposes a progressive algebraic Chase decoding (PACD) algorithm for Reed–Solomon (RS) codes. On the basis of the received information, 2 η ( η > 0) interpolation test‐vectors are constructed for the interpolation‐based algebraic Chase decoding. A test‐vector reliability function is defined to assess their potential for yielding the intended message. The algebraic Chase decoding will then be performed progressively granting priority to decode the test‐vectors that are more likely to yield the message, and is then terminated once it is found. Consequently, the decoding complexity can be adapted to the quality of the received information. An enhanced‐PACD (E‐PACD) algorithm is further proposed by coupling the PACD algorithm with the adaptive belief propagation (ABP) decoding. The ABP decoding generates new test‐vectors for the PACD algorithm by enhancing the received information. It improves the Chase decoding performance without increasing the decoding complexity exponentially. It is shown that the E‐PACD algorithm's complexity can be significantly reduced by utilising the existing interpolation information of the previous Chase decodings’. Our performance evaluations show that the two proposed decoders outperform a number of existing algebraic decoding approaches. Complexity and memory analyses of the PACD algorithm are also presented, demonstrating that this is an efficient RS decoding strategy.

The progressive algebraic soft decoding (PASD) algorithm can leverage the average complexity for algebraic soft decoding (ASD) of Reed-Solomon (RS) codes. With a progressively enlarged decoding parameter that is the designed factorization output list size (OLS), it adapts the expensive interpolation computation to the quality of the received information and makes the average complexity of multiple decoding events channel dependent. However, the complexity reduction is realized at the expense of system memory since the intermediate interpolation information needs to be stored. Addressing this issue, this paper proposes a new PASD algorithm that can significantly reduce the memory requirement through the establishment of a condition on expanding the interpolated polynomial group without using the intermediate information. It has also embraced the interpolation coordinate transform (ICT) that alleviates the iterative polynomial construction task, resulting in the new proposal less computationally expensive than its predecessor, the PASD algorithm. Our numerical analysis shows that its memory requirement will be at most half of that of the PASD algorithm and it is less complex than various ASD algorithms, while the error-correction capability of ASD is preserved.

Traditionally, Reed-Solomon (RS) codes have been employed in magnetic data storage devices due to their effectiveness in correcting random errors and burst errors caused by thermal asperities and inter-symbol interference (ISI). However, as storage densities increase the effect of ISI becomes more severe and much longer RS codes are needed, but this requires significantly increasing the size of the finite field. A possible replacement for RS codes are the one-point Hermitian codes, which are a class of algebraic-geometric (AG) code that have larger block sizes and minimum Hamming distances over the same finite field. In this paper, we present a novel iterative soft detection-decoding algorithm for interleaved Hermitian codes. The soft decoding employs a joint adaptive belief propagation (ABP) algorithm and Koetter-Vardy (KV) list decoding algorithm. It is combined with a maximum a posteriori (MAP) partial response (PR) equalizer and likelihoods from the output of the KV or the ABP algorithm are fed back to the equalizer. The proposed scheme's iterative detection-decoding behavior will be analyzed by utilizing the Extrinsic Information Transfer (ExIT) chart. Our simulation results demonstrate the performance gains achieved by iterations and Hermitian codes' performance advantage over RS codes.

Reed-Solomon convolutional concatenated (RSCC) code has been widely applied in wireless and space communications. However, iterative soft-decision decoding of the concatenated code is yet to be developed. This paper proposes a novel iterative soft decoding algorithm for the concatenated coding scheme. The maximum a posteriori (MAP) algorithm is used to decode the inner convolutional code. Its soft output will be deinterleaved and then passed to the soft-in-soft-out (SISO) decoding algorithm for the outer Reed-Solomon (RS) code. The outer SISO decoder integrates the adaptive belief propagation (ABP) algorithm and the Koetter-Vardy (KV) list decoding algorithm, attempting to find out the transmitted message. If it is found, the deterministic probabilities of the corresponding RS coded bits will be fed back. Otherwise, the extrinsic probabilities that are yielded by the ABP algorithm will be given as the feedback. With the proposed soft information exchange decoding mechanism, error-correction potential of the concatenated code can be better exploited. Our simulation results show that significant performance improvement can be achieved over the existing decoding algorithms.

This paper proposes an iterative soft-decision decoding algorithm for one of the most popular algebraic-geometric (AG) codes - Hermitian codes. The algorithm is designed by integrating the two most powerful soft-decision decoding algorithms, the adaptive belief propagation (ABP) algorithm and the Koetter-Vardy (KV) list decoding algorithm. The ABP algorithm performs iterative decoding based on an adapted parity-check matrix of a Hermitian code to enhance the reliability of the soft received information. With the enhanced reliability, the KV algorithm performs soft-decision list decoding to obtain the original message. Since the matrix adaptation relies on bit reliabilities, regrouping of the unreliable bits is introduced to assist the ABP decoding. A complexity reducing ABP-KV decoding approach is proposed based on assessing the soft information provided by the ABP algorithm and determining whether the following KV decoding steps should be carried out. Geometric interpretation of the ABP algorithm is presented, demonstrating the necessity of performing matrix adaptation. Our performance analysis shows the proposed iterative decoding algorithm outperforms both the existing decoding approaches for Hermitian codes and the ABP-KV decoding of Reed-Solomon (RS) codes.

Reed-Solomon convolutional concatenated (RSCC) code is a popular coding scheme whose application can be found in wireless and space communications. However, iterative soft decoding of the concatenated code is yet to be developed. This paper proposes a novel iterative soft decoding algorithm for the concatenated code, aiming to better exploit its error-correction potential. The maximum a posteriori (MAP) algorithm is used to decode the inner convolutional code. Its soft output will be deinterleaved and then given to the soft-in-soft-out (SISO) decoder of the outer Reed-Solomon (RS) code. The RS SISO decoder integrates the adaptive belief propagation (ABP) algorithm and the Koetter-Vardy (KV) list decoding algorithm, attempting to find out the transmitted message. It feeds back both the deterministic and the extrinsic probabilities of RS coded bits, enabling the soft information to be exchanged between the inner and outer decoders. An extrinsic information transfer (EXIT) analysis of the proposed algorithm is presented, analyzing its iterative decoding behavior for RSCC codes. The EXIT analysis also leads to the design insight of inner code in the concatenation. Computational complexity of the proposed algorithm is also analyzed. Finally, the iterative decoding performance is shown and its advantage over the existing decoding algorithms is demonstrated.

The algebraic soft-decision decoding (ASD) algorithm is a polynomial-time soft decoding algorithm for Reed-Solomon (RS) codes. It outperforms both the algebraic hard-decision decoding (AHD) and the conventional unique decoding algorithms, but with a high computational cost. This paper proposes a progressive ASD (PASD) algorithm that enables the conventional ASD algorithm to perform decoding with an adjustable designed factorization output list size (OLS). The OLS is enlarged progressively leading to an incremental computation for the interpolation and an enhanced error-correction capability. Multiple factorizations are performed in order to find out the intended message polynomial which will be validated by a cyclic redundant check (CRC) code. The incremental interpolation constraints are introduced to characterize the progressive decoding. The validity analysis of the algorithm shows the PASD algorithm is a natural and computationally saving generalization of the ASD algorithm, delivering the same interpolation solution. The average decoding complexity of the algorithm is further theoretically characterized, revealing its dependence on the channel condition. The simulation results further validate the analysis by showing that the average decoding complexity can be converged to the minimal level in a good channel condition. Finally, performance evaluation shows the PASD algorithm preserves the error-correction capability of the ASD algorithm.

In this letter, a Sum-Product algorithm (SPA) utilizing soft distances is shown to be more resilient to impulsive noise than conventional likelihood-based SPAs, when the noise distribution is unknown. An efficient version of the soft distance SPA is also developed but with half the storage requirements and running time.

This paper proposes an opportunistic nonorthogonal amplify-and-forward (ONAF) scheme, assisted by intelligent relay selection. Through analysing the mutual information of the scheme, the novel optimal relay selection criterion is proposed along with its implementation strategy. In order to reduce the system complexity, a sub-optimal selection criterion is then provided. The diversity-multiplexing tradeoff (DMT) analysis shows that the proposed scheme can achieve a diversity gain of the order of the number of candidate relays, and a maximal multiplexing gain of 1. Since the previous work on opportunistic relaying were established under the orthogonal constraint, ONAF is one of the most advanced opportunistic relaying schemes. Our numerical results show the ONAF scheme can outperform the existing nonorthogonal and opportunistic relaying schemes where the relays forward the message using the amplify-and-forward (AF) mode. More importantly, it is a flexible cooperative scheme that can reduce network power consumption, alleviate interference caused among relays' re-transmissions and avoid the negative impact of the weak source-relay-destination channels.

This paper proposes a new distributed Amplify-and-Forward (AF) scheme which is integrated with the Ring-Trellis Coded Modulation (TCM) codes in order to achieve both high spectral efficiency and large diversity gain. In the distributed AF scheme, more users cooperate with each other. Fach user still uses half of its transmission freedom for relaying others' signal. However, different to the conventional AF scheme, each user further partitions its relay transmission into smaller divisions in order to help more users. As a result, for each user, the distributed AF scheme will have the same spectral efficiency as the conventional AF scheme, but creating more diverse transition paths and providing better diversity gain. In the scheme, output symbols are demultiplexed into several subframes, each of which will be relayed by a different user. As a result, each output symbol from a trellis transition branch can be relayed by a different user, assisting error-correction performance of the decoder. This distributed coding scheme is suitable for different wireless access systems, such as WiLAN and WiMAX systems. Our simulation results show that with the same spectral efficiency, the distributed coded AF scheme can significantly outperform the conventional coded AF scheme.

In a cooperative communication network, individual users are encouraged not only to transmit their own data, but also relay other user's data. This relaying transmission creates spatial diversity to combat the effect of individual severe fading and path loss. Since cooperative users utilize some degree of their transmission freedom for relaying other user's data, cooperative transmission results in lowering each user's transmission spectral efficiency. Therefore, a coding scheme with high spectral efficiency and optimized performance would be desirable for a cooperative network. This paper proposes the Trellis Coded Modulation (TCM) scheme to be incorporated with the cooperative Amplify-and- Forward (AF) systems. A criterion for designing good TCM codes for AF systems is also derived and two cooperative AF systems achieving 1 bits/sec/Hz and 1.5 bits/sec/Hz for each user are presented. Analyses in this paper show that cooperative TCM schemes can not only achieve high spectral efficiency, but also outperform convolutional codes with a high order modulation scheme.

This paper proposes the first complete soft-decision list decoding algorithm for Hermitian codes based on the Koetter-Vardy's Reed-Solomon code decoding algorithm. For Hermitian codes, interpolation processes trivariate polynomials which are defined over the pole basis of a Hermitian curve. In this paper, the interpolated zero condition of a trivariate polynomial with respect to a multiplicity matrix M is redefined followed by a proof of the validity of the soft-decision scheme. This paper also introduces a new stopping criterion for the algorithm that tranforms the reliability matrix Pi to the multiplicity matrix M. Geometric characterisation of the trivariate monomial decoding region is investigated, resulting in an asymptotic optimal performance bound for the soft-decision decoder. By defining the weighted degree upper bound of the interpolated polynomial, two complexity reducing modifications are introduced for the soft-decision scheme: elimination of unnecessary interpolated polynomials and pre-calculation of the coefficients that relate the pole basis monomials to the zero basis functions of a Hermitian curve. Our simulation results and analyses show that soft-decision list decoding of Hermitian code can outperform Koetter-Vardy decoding of Reed-Solomon code which is defined in a larger finite field, but with less decoding complexity.

List decoding Hermitian codes using the Guruswami-Sudan (GS) algorithm can correct errors beyond half the designed minimum distance. It consists of two processes: interpolation and factorisation. By first defining a Hermitian curve, these processes can be implemented with an iterative polynomial construction algorithm and a recursive coefficient search algorithm respectively. To improve the efficiency of list decoding Hermitian codes, this paper presents two contributions to reduce the interpolation complexity. First, in order to simplify the calculation of a polynomialiquests zero condition during the iterative interpolation, we propose an algorithm to determine the corresponding coefficients between the pole basis monomials and zero basis functions of a Hermitian curve. Second, we propose a modified complexity reducing interpolation algorithm. This scheme identifies any unnecessary polynomials during iterations and eliminates them to improve the interpolation efficiency. Due to the above complexity reducing modifications, list decoding long Hermitian codes with higher interpolation multiplicity becomes feasible. This paper shows list decoding algorithm can achieve significant coding gain over the conventional unique decoding algorithm.

The list decoding algorithm can outperform the conventional unique decoding algorithm by producing a list of candidate decoded messages. An efficient list decoding algorithm for algebraic-geometric (AG) codes and Reed-Solomon (RS) codes has been developed by Guruswami and Sudan, called the Guruswami-Sudan (GS) algorithm. The algorithm includes two steps: Interpolation and Factorisation. To implement interpolation, Koetter proposed an iterative polynomial construction algorithm for RS codes. By redefining a polynomial over algebraic function fields, Koetter's algorithm can also be applied to AG codes. To implement factorisation, Roth and Ruckenstein proposed an efficient algorithm for RS codes and later Wu and Siegel extended it to AG codes. Following on from their previous work, we propose a more general factorisation algorithm which can be applied to both AG and RS codes. This algorithm avoids rational function quotient calculations required by Wu and SiegePs algorithm, making it more efficient to implement. As well as employing this algorithm to list decode AG and RS codes this paper also presents the first simulation results evaluating the list decoding performance comparison between AG and RS codes of a similar code rate defined over the same finite field.

List decoding is a novel method for decoding Reed–Solomon (RS) codes that generates a list of candidate transmitted messages instead of one unique message as with conventional algebraic decoding, making it possible to correct more errors. The Guruswami–Sudan (GS) algorithm is the most efficient list decoding algorithm for RS codes. Until recently only a few papers in the literature suggested practical methods to implement the key steps (interpolation and factorisation) of the GS algorithm that make the list decoding of RS codes feasible. However, the algorithm's high decoding complexity is unsolved and a novel complexity-reduced modification to improve its efficiency is presented. A detailed explanation of the GS algorithm with the complexity-reduced modification is given with simulation results of RS codes for different list decoding parameters over the AWGN and Rayleigh fading channels. A complexity analysis is presented comparing the GS algorithm with our modified GS algorithm, showing the modification can reduce complexity significantly in low error weight situations. Simulation results using the modified GS algorithm show larger coding gains for RS codes with lower code rates, with more significant gains being achieved over the Rayleigh fading channels.