Mahyar Shirvanimoghaddam

Research

Design of Short Channel Codes

Primitive Rateless Codes

In 2021, I proposed Primitive Rateless Codes [1], which are mainly characterized by the message length k and a primitive polynomial of degree k. Primitive Rateless (PR) codes have excellent properties, which are listed below:

  • The Encoding Process

A primitive rateless (PR) code, denoted by PR(k,p(x)), is characterized by the information block length k and a binary primitive polynomial p(x) of degree k. The generator matrix of a PR code truncated at length n, is constructed as follows, where a is the primitive element:

it can be easily observed that for the PR code, the codeword associated with the message b, satisfies the linear recurrence which is characterized by p(x). In other words, each codeword of a PR code is a subsequence of length n of a maximum-length sequence (m-sequence) [Remark 1, 1].

  • Any PR code is the dual of a polynomial code of codeword length n, message length n-k, and generator polynomial p(x) [Remark 4, 1].

  • Any two PR codes PR(k1,n,p1(x)) and PR(k2,n,p2(x)) do not have any non-zero codeword in common, when n>max{k1,k2} and p1(x) is different than p2(x) [Remark 5, 1].

  • The average number of codewords of Hamming weight j>2 of all PR codes PR(k,n,p(x)) is approximated by [Lemma 5, 1]:

  • The following figure shows the average Hamming weight distribution of a PR codes of dimension k=10 and k=15 at different lengths. The Hamming weight distribution of PR codes can be well approximated by a binomial distribution.

  • For given k and n≥2k, there is at least one PR code with the minimum Hamming weight lower bounded by d, where [Theorem 1, 1]

  • The bound provided above is identical to Gilbert-Varshamov bound when k and n are sufficiently large. The following figure shows the minimum Hamming weight for three PR codes of dimension k= 16, k= 20, and k= 39 at different block length. As can be seen in this figure, a PR code with a properly chosen primitive polynomial will have a minimum Hamming weight close to the Gilbert-Varshamov bound at any block length n≥2k.

  • Performance of PR codes at fixed rates

PR codes have almost identical performance as BCH codes in terms of block error rate (BLER)

  • Comparison with Polar and LDPC codes

PR codes with an ordered statistics decoder (OSD) outperform 5G Polar and LDPC codes.

  • Rateless Performance of PR codes over BI-AWGN channel

PR codes can closely approach the normal approximation bound in a wide range of SNRs without any channel state information at the transmitter side

  • Rateless Performance of PR codes over Rayleigh fading channel

PR codes can closely approach the normal approximation bound in a wide range of SNRs without any channel state information at the transmitter side

  • PR codes can be designed for any message length and the primitive polynomial can be optimized for any block length. They demonstrates a truely rateless performance, thus, they are promising solutions for the future wireless communications.

[1] M. Shirvanimoghaddam, "Primitive Rateless Codes," in IEEE Transactions on Communications, doi: 10.1109/TCOMM.2021.3096961.

Analog Fountain Codes

In 2013, I invented Analog Fountain Codes (AFC) for wireless channels [1]. In AFC, the number of generated coded symbols is potentially limitless. In contrast to the conventional binary rateless codes, each coded symbol in AFC is a real-valued symbol, generated as a weighted sum of d randomly selected information bits, where d and the weight coefficients are randomly selected from predefined probability mass functions. The coded symbols are then directly transmitted through wireless channels.

Weighted bipartite graph of the analog fountain code

[2] Mahyar Shirvanimoghaddam, From Binary to Analog Fountain Codes, PhD Dissertation, The University of Sydney, 2014.

[3] Mahyar Shirvanimoghaddam, et. al., Near-Capacity Adaptive Analog Fountain Codes for Wireless Channels, in IEEE Communications Letters, vol. 17, no. 12, pp. 2241-2244, December 2013.