Amir H. Banihashemi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Amir H. Banihashemi has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Ali Dehghan
Systems and Computer Engineering Department, Carleton University, Ottawa, Canada
9 shared publications Yoones Hashemi
Carleton Univ, Dept Syst & Comp Engn, Ottawa, ON K1S 5B6, Canada
7 shared publications- Ali Farsiabi
Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada
5 shared publications - Hua Xiao
SCE Dept., Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6
3 shared publications - Mahmoud Ahmadian-Attari
Faculty of Electrical Engineering K.N Toosi University of Technology Tehran Iran
3 shared publications - Reza Asvadi
Department of Electrical and Computer Engineering K. N Toosi University of Technology Tehran Iran
3 shared publications
Latest Publications
- 6 October 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 70  (11) , 7075-7088
A Semi Linear State Space Model for Error Floor Estimation of LDPC Codes Over the AWGN Channel
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed in [1] for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.
- 6 October 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 70  (11) , 7075-7088
A Semi Linear State Space Model for Error Floor Estimation of LDPC Codes Over the AWGN Channel
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed in [1] for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.
- 26 June 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2928-2933
A Semi Linear State Space Model for Error Floor Estimation of LDPC codes over the AWGN Channel
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate such behavior at around the operating point of zero. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model.
- 26 June 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2928-2933
A Semi Linear State Space Model for Error Floor Estimation of LDPC codes over the AWGN Channel
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate such behavior at around the operating point of zero. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model.
- 21 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 26  (3) , 485-489
Error Floor Analysis of LDPC Column Layered Decoders
In this letter, we analyze the error floor of column layered decoders, also known as shuffled decoders, for low-density parity-check (LDPC) codes under saturating sum-product algorithm (SPA). To estimate the error floor, we evaluate the failure rate of different trapping sets (TSs) that contribute to the frame error rate in the error floor region. For each such TS, we model the dynamics of SPA in the vicinity of the TS by a linear state-space model that incorporates the information of the layered message-passing schedule. Consequently, the model parameters and the failure rate of the TS change as a result of the change in the order by which the messages of different layers are updated. This, in turn, causes the error floor of the code to change as a function of scheduling. Based on the proposed analysis, we then devise an efficient search algorithm to find a schedule that minimizes the error floor. Simulation results are presented to verify the accuracy of the proposed error floor estimation technique.
- 21 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 26  (3) , 485-489
Error Floor Analysis of LDPC Column Layered Decoders
In this letter, we analyze the error floor of column layered decoders, also known as shuffled decoders, for low-density parity-check (LDPC) codes under saturating sum-product algorithm (SPA). To estimate the error floor, we evaluate the failure rate of different trapping sets (TSs) that contribute to the frame error rate in the error floor region. For each such TS, we model the dynamics of SPA in the vicinity of the TS by a linear state-space model that incorporates the information of the layered message-passing schedule. Consequently, the model parameters and the failure rate of the TS change as a result of the change in the order by which the messages of different layers are updated. This, in turn, causes the error floor of the code to change as a function of scheduling. Based on the proposed analysis, we then devise an efficient search algorithm to find a schedule that minimizes the error floor. Simulation results are presented to verify the accuracy of the proposed error floor estimation technique.
- 21 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67  (9) , 5804-5826
Error Floor Analysis of LDPC Row Layered Decoders
In this paper, we analyze the error floor of quasi-cyclic (QC) low-density parity-check (LDPC) codes decoded by the sum-product algorithm (SPA) with row layered message-passing scheduling. For this, we develop a linear state-space model of trapping sets (TSs) which incorporates the layered nature of scheduling. We demonstrate that the contribution of each TS to the error floor is not only a function of the topology of the TS, but also depends on the row layers in which different check nodes of the TS are located. This information, referred to as TS layer profile (TSLP), plays an important role in the harmfulness of a TS. As a result, the harmfulness of a TS in particular, and the error floor of the code in general, can significantly change by changing the order in which the information of different layers, corresponding to different row blocks of the parity-check matrix, is updated. We also study the problem of finding a layer ordering that minimizes the error floor, and obtain row layered decoders with error floor significantly lower than that of their flooding counterparts. As part of our analysis, we make connections between the parameters of the state-space model for a row layered schedule and those of the flooding schedule. Simulation results are presented to show the accuracy of analytical error floor estimates.
- 21 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67  (9) , 5804-5826
Error Floor Analysis of LDPC Row Layered Decoders
In this paper, we analyze the error floor of quasi-cyclic (QC) low-density parity-check (LDPC) codes decoded by the sum-product algorithm (SPA) with row layered message-passing scheduling. For this, we develop a linear state-space model of trapping sets (TSs) which incorporates the layered nature of scheduling. We demonstrate that the contribution of each TS to the error floor is not only a function of the topology of the TS, but also depends on the row layers in which different check nodes of the TS are located. This information, referred to as TS layer profile (TSLP), plays an important role in the harmfulness of a TS. As a result, the harmfulness of a TS in particular, and the error floor of the code in general, can significantly change by changing the order in which the information of different layers, corresponding to different row blocks of the parity-check matrix, is updated. We also study the problem of finding a layer ordering that minimizes the error floor, and obtain row layered decoders with error floor significantly lower than that of their flooding counterparts. As part of our analysis, we make connections between the parameters of the state-space model for a row layered schedule and those of the flooding schedule. Simulation results are presented to show the accuracy of analytical error floor estimates.
- 15 March 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (6) , 3528-3540
ADMM Check Node Penalized Decoders for LDPC Codes
Alternating direction method of multipliers (ADMM) is an efficient implementation of linear programming (LP) decoding for low-density parity-check (LDPC) codes. By adding penalty terms to the objective function of the LP decoding model, ADMM variable node (VN) penalized decoding can suppress the non-integral solutions and improve the frame error rate (FER) performance in the low signal-to-noise ratio (SNR) region. In this paper, we propose a novel ADMM check node (CN) penalized decoding algorithm. Codeword solutions which satisfy all parity-check equations will have smaller penalty values than non-codeword solutions, including the non-integral solutions. We discuss the required properties of CN-penalty functions, propose a few functions that satisfy those properties, and study their performance/complexity trade-offs. We also investigate the convergence properties of the proposed algorithm and prove that its performance is independent of the transmitted codeword. Using Monte Carlo simulations and instanton analysis, we then demonstrate that the proposed CN-penalized decoder outperforms ADMM VN penalized decoders in both waterfall and error floor regions. This comes at the expense of some increase in the decoding complexity.
- 15 March 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (6) , 3528-3540
ADMM Check Node Penalized Decoders for LDPC Codes
Alternating direction method of multipliers (ADMM) is an efficient implementation of linear programming (LP) decoding for low-density parity-check (LDPC) codes. By adding penalty terms to the objective function of the LP decoding model, ADMM variable node (VN) penalized decoding can suppress the non-integral solutions and improve the frame error rate (FER) performance in the low signal-to-noise ratio (SNR) region. In this paper, we propose a novel ADMM check node (CN) penalized decoding algorithm. Codeword solutions which satisfy all parity-check equations will have smaller penalty values than non-codeword solutions, including the non-integral solutions. We discuss the required properties of CN-penalty functions, propose a few functions that satisfy those properties, and study their performance/complexity trade-offs. We also investigate the convergence properties of the proposed algorithm and prove that its performance is independent of the transmitted codeword. Using Monte Carlo simulations and instanton analysis, we then demonstrate that the proposed CN-penalized decoder outperforms ADMM VN penalized decoders in both waterfall and error floor regions. This comes at the expense of some increase in the decoding complexity.
- 22 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (6) , 3485-3501
Construction of Time Invariant Spatially Coupled LDPC Codes Free of Small Trapping Sets
In this paper, we propose a design technique for the construction of variable-regular time-invariant spatially-coupled low-density parity-check (SC-LDPC) codes with small constraint length and low error floor. The proposed technique reduces the error floor by imposing simple constraints on the short cycles in the code's Tanner graph, which in turn, result in the elimination of the most dominant trapping sets of the code. In some cases, we also derive lower bounds on the syndrome former memory for satisfying such constraints. The designed codes are superior to the state-of-the-art in terms of error floor performance and/or decoding complexity and latency.
- 22 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (6) , 3485-3501
Construction of Time Invariant Spatially Coupled LDPC Codes Free of Small Trapping Sets
In this paper, we propose a design technique for the construction of variable-regular time-invariant spatially-coupled low-density parity-check (SC-LDPC) codes with small constraint length and low error floor. The proposed technique reduces the error floor by imposing simple constraints on the short cycles in the code's Tanner graph, which in turn, result in the elimination of the most dominant trapping sets of the code. In some cases, we also derive lower bounds on the syndrome former memory for satisfying such constraints. The designed codes are superior to the state-of-the-art in terms of error floor performance and/or decoding complexity and latency.
- 8 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (5) , 2784-2799
Error Floor Estimation of LDPC Coded Modulation Systems Using Importance Sampling
One of the key weaknesses of low-density parity-check (LDPC) codes is the error floor that they typically exhibit at high signal-to-noise ratios (SNRs). Such an error floor is usually attributed to problematic structures known as trapping sets (TSs). The overwhelming majority of existing error floor estimation schemes consider the case of binary phase shift keying (BPSK) signalling. Unfortunately, these schemes are not readily extensible to estimate the error floor of high order LDPC coded modulation systems considered herein. To provide such a scheme, in this work, we use mean-shift importance sampling (MS-IS) to develop a novel error floor estimation methodology for high-order pulse amplitude modulation (PAM) and quadrature amplitude modulation (QAM) LDPC coded systems. First, a computationally efficient graphical-based approach is used to identify the TSs of a given LDPC code. Subsequently, a novel analytical approach is devised to identify the TSs that are likely to have a higher contribution in the error floor. These TSs are referred to as potentially dominant TSs (PDTSs). Finally, a new methodology for categorizing the PDTSs into equivalence classes is developed. A representative PDTS of each equivalence class is chosen and an MS-IS framework is devised to obtain the error rate corresponding to each equivalence class. To arrive at the desired MS-IS scheme, we develop an algorithm that invokes the geometry of the constellation to determine the MS value. In contrast with the conventional MS-IS method used in BPSK signalling, in the proposed MS-IS scheme, the MS value is a variable that is determined based on the TS and the transmitted codeword. The computational complexity of the three main steps of our methodology, viz. extracting the PDTSs, determining the MS values, and applying the MS-IS scheme, depends merely on the size of the constellation and the structure of the code, but not on the SNR. Numerical simulations confirm the efficacy and accuracy of the proposed technique at different SNRs.
- 8 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (5) , 2784-2799
Error Floor Estimation of LDPC Coded Modulation Systems Using Importance Sampling
One of the key weaknesses of low-density parity-check (LDPC) codes is the error floor that they typically exhibit at high signal-to-noise ratios (SNRs). Such an error floor is usually attributed to problematic structures known as trapping sets (TSs). The overwhelming majority of existing error floor estimation schemes consider the case of binary phase shift keying (BPSK) signalling. Unfortunately, these schemes are not readily extensible to estimate the error floor of high order LDPC coded modulation systems considered herein. To provide such a scheme, in this work, we use mean-shift importance sampling (MS-IS) to develop a novel error floor estimation methodology for high-order pulse amplitude modulation (PAM) and quadrature amplitude modulation (QAM) LDPC coded systems. First, a computationally efficient graphical-based approach is used to identify the TSs of a given LDPC code. Subsequently, a novel analytical approach is devised to identify the TSs that are likely to have a higher contribution in the error floor. These TSs are referred to as potentially dominant TSs (PDTSs). Finally, a new methodology for categorizing the PDTSs into equivalence classes is developed. A representative PDTS of each equivalence class is chosen and an MS-IS framework is devised to obtain the error rate corresponding to each equivalence class. To arrive at the desired MS-IS scheme, we develop an algorithm that invokes the geometry of the constellation to determine the MS value. In contrast with the conventional MS-IS method used in BPSK signalling, in the proposed MS-IS scheme, the MS value is a variable that is determined based on the TS and the transmitted codeword. The computational complexity of the three main steps of our methodology, viz. extracting the PDTSs, determining the MS values, and applying the MS-IS scheme, depends merely on the size of the constellation and the structure of the code, but not on the SNR. Numerical simulations confirm the efficacy and accuracy of the proposed technique at different SNRs.
- 1 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (1) , 3-18
Construction of Irregular Protograph-Based QC-LDPC Codes With Low Error Floor
- 1 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69  (1) , 3-18
Construction of Irregular Protograph-Based QC-LDPC Codes With Low Error Floor
- 17 August 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66  (10) , 6024-6036
On Finding Bipartite Graphs With a Small Number of Short Cycles and Large Girth
The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for a given set of integers α, β, and γ, and degree sequences π and π’, the problem of determining whether there exists a simple bipartite graph with degree sequences (π,π’) that has at most α (β and γ) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced.
- 17 August 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66  (10) , 6024-6036
On Finding Bipartite Graphs With a Small Number of Short Cycles and Large Girth
The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for a given set of integers α, β, and γ, and degree sequences π and π’, the problem of determining whether there exists a simple bipartite graph with degree sequences (π,π’) that has at most α (β and γ) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced.
- 23 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66  (10) , 6037-6047
On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix
Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than 2g, where g is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum {η i } of the directed edge matrix of the graph to compute the multiplicity N k of k-cycles with k <; 2g through the simple equation N k = Σ i η i k /(2k). This approach has a computational complexity O(|E| 3 ), where |E| is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum {λ i } of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute N k . The complexity of this approach is O(|V| 3 ), where |V| is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are complex and tedious, particularly for k ≥ g+6. In fact, the computational complexity of the equations increases exponentially with k. In this paper, we establish an analytical relationship between the two spectra {η i } and {λ i } for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations with computational complexity constant in k. This allows the computation of N k using N k = Σ i η i k /(2k) but with a complexity of O(|V| 3 ) rather than O(|E| 3 ).
- 23 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66  (10) , 6037-6047
On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix
Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than 2g, where g is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum {η i } of the directed edge matrix of the graph to compute the multiplicity N k of k-cycles with k <; 2g through the simple equation N k = Σ i η i k /(2k). This approach has a computational complexity O(|E| 3 ), where |E| is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum {λ i } of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute N k . The complexity of this approach is O(|V| 3 ), where |V| is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are complex and tedious, particularly for k ≥ g+6. In fact, the computational complexity of the equations increases exponentially with k. In this paper, we establish an analytical relationship between the two spectra {η i } and {λ i } for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations with computational complexity constant in k. This allows the computation of N k using N k = Σ i η i k /(2k) but with a complexity of O(|V| 3 ) rather than O(|E| 3 ).