Showing 1–50 of 86 results for author: Viterbo, E

Block Circulant Codes with Application to Decentralized Systems

Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau

Abstract: The structure of linear dependence relations between coded symbols of a linear code, irrespective of specific coefficients involved, is referred to as the {\em topology} of the code. The specification of coefficients is referred to as an {\em instantiation} of the topology. In this paper, we propose a new block circulant topology $T_{[μ,λ,ω]}(ρ)$ parameterized by integers $ρ\geq 2$, $ω\geq 1$,… ▽ More The structure of linear dependence relations between coded symbols of a linear code, irrespective of specific coefficients involved, is referred to as the {\em topology} of the code. The specification of coefficients is referred to as an {\em instantiation} of the topology. In this paper, we propose a new block circulant topology $T_{[μ,λ,ω]}(ρ)$ parameterized by integers $ρ\geq 2$, $ω\geq 1$, $λ\geq 2$, and $μ$ a multiple of $λ$. In this topology, the code has $μ$ local codes with $ρ$ parity-check (p-c) constraints and a total of $μρ$ p-c equations fully define the code. Next, we construct a class of block circulant (BC) codes ${\cal C}_{\text{BC}}[μ,λ,ω,ρ]$ with blocklength $n=μ(ρ+ω)$, dimension $k=μω$ that instantiate $T_{[μ,λ,ω]}(ρ)$. Every local code of ${\cal C}_{\text{BC}}[μ,λ,ω,ρ]$ is a $[ρ+λω,λω,ρ+1]$ generalized Reed-Solomon (RS) code. The overlap between supports of local codes helps to enhance the minimum distance $ρ+1$ to $2ρ+1$, without compromising much on the rate. We provide an efficient, parallelizable decoding algorithm to correct $2ρ$ erasures when $λ=2$. Finally, we illustrate that the BC codes serve as a viable alternative to 2D RS codes in protocols designed to tackle blockchain networks' data availability (DA) problem. In these protocols, every node in a network of light nodes randomly queries symbols from a codeword stored in full nodes and verifies them using a cryptographic commitment scheme. For the same performance in tackling the DA problem, the BC code requires querying a smaller number of symbols than a comparable 2D RS code for a fixed high rate. Furthermore, the number of local codes in the BC code is typically smaller, yielding a reduction in the complexity of realizing the commitment scheme. △ Less

Submitted 17 June, 2024; originally announced June 2024.

Repairing Reed-Solomon Codes with Side Information

Authors: Thi Xinh Dinh, Ba Thong Le, Son Hoang Dau, Serdar Boztas, Stanislav Kruglik, Han Mao Kiah, Emanuele Viterbo, Tuvi Etzion, Yeow Meng Chee

Abstract: We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is… ▽ More We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on $|S|$ and not the content of $S$ and construct a lower bound on the repair bandwidth of a linear repair scheme with side information $S$. We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes. △ Less

Submitted 12 May, 2024; originally announced May 2024.

MSC Class: 94B05; 94B60 ACM Class: E.4

On noisy duplication channels with Markov sources

Authors: Brendon McBain, James Saunderson, Emanuele Viterbo

Abstract: Channels with noisy duplications have recently been used to model the nanopore sequencer. This paper extends some foundational information-theoretic results to this new scenario. We prove the asymptotic equipartition property (AEP) for noisy duplication processes based on ergodic Markov processes. A consequence is that the noisy duplication channel is information stable for ergodic Markov sources,… ▽ More Channels with noisy duplications have recently been used to model the nanopore sequencer. This paper extends some foundational information-theoretic results to this new scenario. We prove the asymptotic equipartition property (AEP) for noisy duplication processes based on ergodic Markov processes. A consequence is that the noisy duplication channel is information stable for ergodic Markov sources, and therefore the channel capacity constrained to Markov sources is the Markov-constrained Shannon capacity. We use the AEP to estimate lower bounds on the capacity of the binary symmetric channel with Bernoulli and geometric duplications using Monte Carlo simulations. In addition, we relate the AEP for noisy duplication processes to the AEP for hidden semi-Markov processes. △ Less

Submitted 9 May, 2024; originally announced May 2024.

Comments: To appear in the Proceedings of the 2024 IEEE International Symposium on Information Theory (ISIT)

Lightweight Conceptual Dictionary Learning for Text Classification Using Information Compression

Authors: Li Wan, Tansu Alpcan, Margreta Kuijper, Emanuele Viterbo

Abstract: We propose a novel, lightweight supervised dictionary learning framework for text classification based on data compression and representation. This two-phase algorithm initially employs the Lempel-Ziv-Welch (LZW) algorithm to construct a dictionary from text datasets, focusing on the conceptual significance of dictionary elements. Subsequently, dictionaries are refined considering label data, opti… ▽ More We propose a novel, lightweight supervised dictionary learning framework for text classification based on data compression and representation. This two-phase algorithm initially employs the Lempel-Ziv-Welch (LZW) algorithm to construct a dictionary from text datasets, focusing on the conceptual significance of dictionary elements. Subsequently, dictionaries are refined considering label data, optimizing dictionary atoms to enhance discriminative power based on mutual information and class distribution. This process generates discriminative numerical representations, facilitating the training of simple classifiers such as SVMs and neural networks. We evaluate our algorithm's information-theoretic performance using information bottleneck principles and introduce the information plane area rank (IPAR) as a novel metric to quantify the information-theoretic performance. Tested on six benchmark text datasets, our algorithm competes closely with top models, especially in limited-vocabulary contexts, using significantly fewer parameters. \review{Our algorithm closely matches top-performing models, deviating by only ~2\% on limited-vocabulary datasets, using just 10\% of their parameters. However, it falls short on diverse-vocabulary datasets, likely due to the LZW algorithm's constraints with low-repetition data. This contrast highlights its efficiency and limitations across different dataset types. △ Less

Submitted 28 April, 2024; originally announced May 2024.

Comments: 12 pages, TKDE format

OTFS Channel Estimation and Detection for Channels with Very Large Delay Spread

Authors: Preety Priya, Yi Hong, Emanuele Viterbo

Abstract: In low latency applications and in general, for overspread channels, channel delay spread is a large percentage of the transmission frame duration. In this paper, we consider OTFS in an overspread channel exhibiting a delay spread that exceeds the block duration in a frame, where traditional channel estimation (CE) fails. We propose a two-stage CE method based on a delay-Doppler (DD) training fram… ▽ More In low latency applications and in general, for overspread channels, channel delay spread is a large percentage of the transmission frame duration. In this paper, we consider OTFS in an overspread channel exhibiting a delay spread that exceeds the block duration in a frame, where traditional channel estimation (CE) fails. We propose a two-stage CE method based on a delay-Doppler (DD) training frame, consisting of a dual chirp converted from time domain and a higher power pilot. The first stage employs a DD domain embedded pilot CE to estimate the aliased delays (due to modulo operation) and Doppler shifts, followed by identifying all the underspread paths not coinciding with any overspread path. The second stage utilizes time domain dual chirp correlation to estimate the actual delays and Doppler shifts of the remaining paths. This stage also resolves ambiguity in estimating delays and Doppler shifts for paths sharing same aliased delay. Furthermore, we present a modified low-complexity maximum ratio combining (MRC) detection algorithm for OTFS in overspread channels. Finally, we evaluate performance of OTFS using the proposed CE and the modified MRC detection in terms of normalized mean square error (NMSE) and bit error rate (BER). △ Less

Submitted 12 April, 2024; originally announced April 2024.

A Family of Low-Complexity Binary Codes with Constant Hamming Weights

Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau

Abstract: In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have a size $M=2^k$. For every integer $\ell \geq 3$, we construct a $(n=2^\ell, M=2^{k_{\ell}}, d=2)$ constant weight code ${\cal C}[\ell]$ of weight $\ell$ by encoding information in the gaps between successive $1$'s. The code is associated with an integer se… ▽ More In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have a size $M=2^k$. For every integer $\ell \geq 3$, we construct a $(n=2^\ell, M=2^{k_{\ell}}, d=2)$ constant weight code ${\cal C}[\ell]$ of weight $\ell$ by encoding information in the gaps between successive $1$'s. The code is associated with an integer sequence of length $\ell$ with a constraint defined as {\em anchor-decodability} that ensures low complexity for encoding and decoding. The complexity of the encoding is linear in the input size $k$, and that of the decoding is poly-logarithmic in the input size $n$, discounting the linear time spent on parsing the input. Both the algorithms do not require expensive computation of binomial coefficients, unlike the case in many existing schemes. Among codes generated by all anchor-decodable sequences, we show that ${\cal C}[\ell]$ has the maximum size with $k_{\ell} \geq \ell^2-\ell\log_2\ell + \log_2\ell - 0.279\ell - 0.721$. As $k$ is upper bounded by $\ell^2-\ell\log_2\ell +O(\ell)$ information-theoretically, the code ${\cal C}[\ell]$ is optimal in its size with respect to two higher order terms of $\ell$. In particular, $k_\ell$ meets the upper bound for $\ell=3$ and one-bit away for $\ell=4$. On the other hand, we show that ${\cal C}[\ell]$ is not unique in attaining $k_{\ell}$ by constructing an alternate code ${\cal \hat{C}}[\ell]$ again parameterized by an integer $\ell \geq 3$ with a different low-complexity decoder, yet having the same size $2^{k_{\ell}}$ when $3 \leq \ell \leq 7$. Finally, we also derive new codes by modifying ${\cal C}[\ell]$ that offer a wider range on blocklength and weight while retaining low complexity for encoding and decoding. For certain selected values of parameters, these modified codes too have an optimal $k$. △ Less

Submitted 30 June, 2024; v1 submitted 29 January, 2024; originally announced January 2024.

Comments: Submitted to Designs, Codes and Cryptography

Robust Localization and Tracking of UAVs in OTFS-based Networks

Authors: Alessandro Nordio, Carla Fabiana Chiasserini, Emanuele Viterbo

Abstract: We consider the problem of accurately localizing N unmanned aerial vehicles (UAV) in 3D space where the UAVs are part of a swarm and communicate with each other through orthogonal time-frequency space (OTFS) modulated signals. Each receiving UAV estimates the multipath wireless channel on each link formed by the line-of-sight (LoS) transmission and by the single reflections from the remaining N-2… ▽ More We consider the problem of accurately localizing N unmanned aerial vehicles (UAV) in 3D space where the UAVs are part of a swarm and communicate with each other through orthogonal time-frequency space (OTFS) modulated signals. Each receiving UAV estimates the multipath wireless channel on each link formed by the line-of-sight (LoS) transmission and by the single reflections from the remaining N-2 UAVs. The estimated power delay profiles are communicated to an edge server, which is in charge of computing the exact location and speed of the UAVs. To obtain the UAVs locations and velocities, we propose an iterative algorithm, named Turbo Iterative Positioning (TIP), which, using a belief-propagation approach, effectively exploits the time difference of arrival (TDoA) measurements between the LoS and the non-LoS paths. Enabling a full cold start (no prior knowledge), our solution first maps each TDoA's profile element to a specific ID of the reflecting UAV's. The Doppler shifts measured by the OTFS receivers associated with each path are also used to estimate the UAV's velocities. The localization of the N UAVs is then derived via gradient descent optimization, with the aid of turbo-like iterations that can progressively correct some of the residual errors in the initial ID mapping operation. Our numerical results, obtained also using real-world traces, show how the multipath links are beneficial to achieving very accurate localization and speed of all UAVs, even with a limited delay-Doppler resolution. Robustness of our scheme is proven by its performance approaching the Cramer-Rao bound. △ Less

Submitted 29 November, 2023; originally announced November 2023.

From Programming Bugs to Multimillion-Dollar Scams: An Analysis of Trapdoor Tokens on Decentralized Exchanges

Authors: Phuong Duy Huynh, Thisal De Silva, Son Hoang Dau, Xiaodong Li, Iqbal Gondal, Emanuele Viterbo

Abstract: We investigate in this work a recently emerging type of scam token called Trapdoor, which has caused the investors hundreds of millions of dollars in the period of 2020-2023. In a nutshell, by embedding logical bugs and/or owner-only features to the smart contract codes, a Trapdoor token allows users to buy but prevent them from selling. We develop the first systematic classification of Trapdoor t… ▽ More We investigate in this work a recently emerging type of scam token called Trapdoor, which has caused the investors hundreds of millions of dollars in the period of 2020-2023. In a nutshell, by embedding logical bugs and/or owner-only features to the smart contract codes, a Trapdoor token allows users to buy but prevent them from selling. We develop the first systematic classification of Trapdoor tokens and a comprehensive list of their programming techniques, accompanied by a detailed analysis on representative scam contracts. We also construct the very first dataset of 1859 manually verified Trapdoor tokens on Uniswap and build effective opcode-based detection tools using popular machine learning classifiers such as Random Forest, XGBoost, and LightGBM, which achieve at least 0.98% accuracies, precisions, recalls, and F1-scores. △ Less

Submitted 21 September, 2023; v1 submitted 9 September, 2023; originally announced September 2023.

Comments: 22 pages, 11 figures

Improving Robustness and Accuracy of Ponzi Scheme Detection on Ethereum Using Time-Dependent Features

Authors: Phuong Duy Huynh, Son Hoang Dau, Xiaodong Li, Phuc Luong, Emanuele Viterbo

Abstract: The rapid development of blockchain has led to more and more funding pouring into the cryptocurrency market, which also attracted cybercriminals' interest in recent years. The Ponzi scheme, an old-fashioned fraud, is now popular on the blockchain, causing considerable financial losses to many crypto-investors. A few Ponzi detection methods have been proposed in the literature, most of which detect… ▽ More The rapid development of blockchain has led to more and more funding pouring into the cryptocurrency market, which also attracted cybercriminals' interest in recent years. The Ponzi scheme, an old-fashioned fraud, is now popular on the blockchain, causing considerable financial losses to many crypto-investors. A few Ponzi detection methods have been proposed in the literature, most of which detect a Ponzi scheme based on its smart contract source code or opcode. The contract-code-based approach, while achieving very high accuracy, is not robust: first, the source codes of a majority of contracts on Ethereum are not available, and second, a Ponzi developer can fool a contract-code-based detection model by obfuscating the opcode or inventing a new profit distribution logic that cannot be detected (since these models were trained on existing Ponzi logics only). A transaction-based approach could improve the robustness of detection because transactions, unlike smart contracts, are harder to be manipulated. However, the current transaction-based detection models achieve fairly low accuracy. We address this gap in the literature by developing new detection models that rely only on the transactions, hence guaranteeing the robustness, and moreover, achieve considerably higher Accuracy, Precision, Recall, and F1-score than existing transaction-based models. This is made possible thanks to the introduction of novel time-dependent features that capture Ponzi behaviours characteristics derived from our comprehensive data analyses on Ponzi and non-Ponzi data from the XBlock-ETH repository △ Less

Submitted 30 August, 2023; originally announced August 2023.

Comments: 17 pages, 9 figures, 4 tables

Designing Compact Repair Groups for Reed-Solomon Codes

Authors: Thi Xinh Dinh, Serdar Boztas, Son Hoang Dau, Emanuele Viterbo

Abstract: Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair sch… ▽ More Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair schemes, thus saving the time and space required for finding and storing them. The goal is to design compact repair groups that can tolerate as many failures as possible. It turns out that the maximum number of failures a collection of repair groups can tolerate equals the size of a minimum hitting set of a collection of subsets of the finite field {\mathbb{F}_{q^{\ell}}} minus one. When the repair groups for each symbol are generated from a single subspace, we establish a pair of asymptotically tight lower bound and upper bound on the size of such a minimum hitting set. Using Burnside's Lemma and the Möbius inversion formula, we determine a number of subspaces that together attain the upper bound on the minimum hitting set size when the repair groups are generated from multiple subspaces. △ Less

Submitted 11 May, 2023; originally announced May 2023.

Committed Private Information Retrieval

Authors: Quang Cao, Hong Yen Tran, Son Hoang Dau, Xun Yi, Emanuele Viterbo, Chen Feng, Yu-Chih Huang, Jingge Zhu, Stanislav Kruglik, Han Mao Kiah

Abstract: A private information retrieval (PIR) scheme allows a client to retrieve a data item $x_i$ among $n$ items $x_1,x_2,\ldots,x_n$ from $k$ servers, without revealing what $i$ is even when $t < k$ servers collude and try to learn $i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is $v$-verifiable if the client can verify the correctness of the retrieved $x_i$ even when $v \leq k$ servers… ▽ More A private information retrieval (PIR) scheme allows a client to retrieve a data item $x_i$ among $n$ items $x_1,x_2,\ldots,x_n$ from $k$ servers, without revealing what $i$ is even when $t < k$ servers collude and try to learn $i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is $v$-verifiable if the client can verify the correctness of the retrieved $x_i$ even when $v \leq k$ servers collude and try to fool the client by sending manipulated data. Most of the previous works in the literature on PIR assumed that $v < k$, leaving the case of all-colluding servers open. We propose a generic construction that combines a linear map commitment (LMC) and an arbitrary linear PIR scheme to produce a $k$-verifiable PIR scheme, termed a committed PIR scheme. Such a scheme guarantees that even in the worst scenario, when all servers are under the control of an attacker, although the privacy is unavoidably lost, the client won't be fooled into accepting an incorrect $x_i$. We demonstrate the practicality of our proposal by implementing the committed PIR schemes based on the Lai-Malavolta LMC and three well-known PIR schemes using the GMP library and blst, the current fastest C library for elliptic curve pairings. △ Less

Submitted 25 September, 2023; v1 submitted 3 February, 2023; originally announced February 2023.

Comments: Accepted at ESORICS 2023

TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead

Authors: Son Hoang Dau, Quang Cao, Rinaldo Gagiano, Duy Huynh, Xun Yi, Phuc Lu Le, Quang-Hung Luu, Emanuele Viterbo, Yu-Chih Huang, Jingge Zhu, Mohammad M. Jalalzai, Chen Feng

Abstract: A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch-PIR are based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that \textit{zero} storage overhead… ▽ More A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch-PIR are based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that \textit{zero} storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of trees has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving $3\times$ lower total storage and $1.5$-$2\times$ lower computation and communication costs. Most notably, TreePIR has $8$-$160\times$ lower setup time and its polylog-complexity indexing algorithm is $19$-$160\times$ faster than PBC for trees of $2^{10}$-$2^{24}$ leaves. △ Less

Submitted 4 June, 2024; v1 submitted 10 May, 2022; originally announced May 2022.

Comments: 25 pages

MSC Class: 05C05; 05C15; 05C85; 05C90; ACM Class: G.2.2; F.2.0; E.1

Finite-State Semi-Markov Channels for Nanopore Sequencing

Authors: Brendon McBain, Emanuele Viterbo, James Saunderson

Abstract: Nanopore sequencing is an emerging DNA sequencing technology that has been proposed for use in DNA storage systems. We propose the noisy nanopore channel model for nanopore sequencing. This model captures duplications, inter-symbol interference, and noisy measurements by concatenating an i.i.d. duplication channel with a finite-state semi-Markov channel. Compared to previous models, this channel m… ▽ More Nanopore sequencing is an emerging DNA sequencing technology that has been proposed for use in DNA storage systems. We propose the noisy nanopore channel model for nanopore sequencing. This model captures duplications, inter-symbol interference, and noisy measurements by concatenating an i.i.d. duplication channel with a finite-state semi-Markov channel. Compared to previous models, this channel models the dominant distortions of the nanopore while remaining tractable. Anticipating future coding schemes, we derive MAP detection algorithms and estimate achievable rates. Given that finite-state semi-Markov channels are a subclass of channels with memory, we conjecture that the achievable rate of the noisy nanopore channel can be optimised using a variation of the generalised Blahut-Arimoto algorithm. △ Less

Submitted 9 May, 2022; originally announced May 2022.

Comments: 6 pages. 4 figures. To appear in the Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT)

Unitary-Precoded Single-Carrier Waveforms for High Mobility: Detection and Channel Estimation

Authors: Tharaj Thaj, Emanuele Viterbo

Abstract: This paper presents unitary-precoded single-carrier (USC) modulation as a family of waveforms based on multiplexing the information symbols on time domain unitary basis functions. The common property of these basis functions is that they span the entire time and frequency plane. The recently proposed orthogonal time frequency space (OTFS) and orthogonal time sequency multiplexing (OTSM) based on d… ▽ More This paper presents unitary-precoded single-carrier (USC) modulation as a family of waveforms based on multiplexing the information symbols on time domain unitary basis functions. The common property of these basis functions is that they span the entire time and frequency plane. The recently proposed orthogonal time frequency space (OTFS) and orthogonal time sequency multiplexing (OTSM) based on discrete Fourier transform (DFT) and Walsh Hadamard transform (WHT), respectively, fall in the general framework of USC waveforms. In this work, we present channel estimation and detection methods that work for any USC waveform and numerically show that any choice of unitary precoding results in the same error performance. Lastly, we implement some USC systems and compare their performance with OFDM in a real-time indoor setting using an SDR platform. △ Less

Submitted 25 January, 2022; originally announced January 2022.

Comments: Accepted for publication in IEEE Wireless Communications and Networking Conference, 10-13 April 2022, Austin, TX, USA

On the Formation of Min-weight Codewords of Polar/PAC Codes and Its Applications

Authors: Mohammad Rowshan, Son Hoang Dau, Emanuele Viterbo

Abstract: Minimum weight codewords play a crucial role in the error correction performance of a linear block code. In this work, we establish an explicit construction for these codewords of polar codes as a sum of the generator matrix rows, which can then be used as a foundation for two applications. In the first application, we obtain a lower bound for the number of minimum-weight codewords (a.k.a. the err… ▽ More Minimum weight codewords play a crucial role in the error correction performance of a linear block code. In this work, we establish an explicit construction for these codewords of polar codes as a sum of the generator matrix rows, which can then be used as a foundation for two applications. In the first application, we obtain a lower bound for the number of minimum-weight codewords (a.k.a. the error coefficient), which matches the exact number established previously in the literature. In the second application, we derive a novel method that modifies the information set (a.k.a. rate profile) of polar codes and PAC codes in order to reduce the error coefficient, hence improving their performance. More specifically, by analyzing the structure of minimum-weight codewords of polar codes (as special sums of the rows in the polar transform matrix), we can identify rows (corresponding to \textit{information} bits) that contribute the most to the formation of such codewords and then replace them with other rows (corresponding to \textit{frozen} bits) that bring in few minimum-weight codewords. A similar process can also be applied to PAC codes. Our approach deviates from the traditional constructions of polar codes, which mostly focus on the reliability of the sub-channels, by taking into account another important factor - the weight distribution. Extensive numerical results show that the modified codes outperform PAC codes and CRC-Polar codes at the practical block error rate of $10^{-2}$-$10^{-3}$. △ Less

Submitted 20 September, 2023; v1 submitted 16 November, 2021; originally announced November 2021.

Comments: Accepted in IEEE Trans. Inf. Theory, 23 pages, 13 figures, 6 tables, 3 listings

Efficient Partial Rewind of Polar Codes' Successive Cancellation-based Decoders for Re-decoding Attempts

Authors: Mohammad Rowshan, Emanuele Viterbo

Abstract: Successive cancellation (SC) process is an essential component of various decoding algorithms used for polar codes and their variants. Rewinding this process seems trivial if we have access to all intermediate log-likelihood ratios (LLRs) and partial sums. However, as the block length increases, retaining all of the intermediate information becomes inefficient and impractical. Rewinding the SC pro… ▽ More Successive cancellation (SC) process is an essential component of various decoding algorithms used for polar codes and their variants. Rewinding this process seems trivial if we have access to all intermediate log-likelihood ratios (LLRs) and partial sums. However, as the block length increases, retaining all of the intermediate information becomes inefficient and impractical. Rewinding the SC process in a memory-efficient way is a problem that we address in this paper. We first explore the properties of the SC process based on the binary representation of the bit indices by introducing a new operator used for grouping the bit indices. This special grouping helps us in finding the closest bit index to the target index for rewinding. We also analytically prove that this approach gives access to the untouched intermediate information stored in the memory which is essential in resuming the SC process. Then, we adapt the proposed approach to multiple rewinds and apply it on SC-flip decoding and shifted-pruning based list decoding. The numerical evaluation of the proposed solution shows a significant reduction of >=50% in the complexity of the additional decoding attempts at medium and high SNR regimes for SC-flip decoding and less for shifted-pruning based list decoding. △ Less

Submitted 21 September, 2021; originally announced September 2021.

Hybrid Non-Binary Repeated Polar Codes

Authors: Fariba Abbasi, Hessam Mahdavifar, Emanuele Viterbo

Abstract: Concatenating the state-of-the-art codes at moderate rates with repetition codes has emerged as a practical solution deployed in various standards for ultra-low-power devices such as in Internet-of-Things (IoT) networks. In this paper, we propose a novel concatenation mechanism for such applications which need to operate at very low signal-to-noise ratio (SNR) regime. In the proposed scheme, the o… ▽ More Concatenating the state-of-the-art codes at moderate rates with repetition codes has emerged as a practical solution deployed in various standards for ultra-low-power devices such as in Internet-of-Things (IoT) networks. In this paper, we propose a novel concatenation mechanism for such applications which need to operate at very low signal-to-noise ratio (SNR) regime. In the proposed scheme, the outer code is a hybrid polar code constructed in two stages, one with a binary kernel and another also with a binary kernel but applied over a binary extension field. The inner code is a non-binary multiplicative repetition code. This particular structure inherits low-complexity decoding structures of polar codes while enabling concatenation with an inner non-binary multiplicative repetition scheme. The decoding for the proposed scheme is done using cyclic redundancy check (CRC) aided successive cancellation list (SCL) decoder over AWGN channel. Simulation results demonstrate that the proposed hybrid non-binary repeated polar code provides performance gain compared to a polar-repetition scheme with comparable decoding complexity. △ Less

Submitted 23 March, 2022; v1 submitted 22 June, 2021; originally announced June 2021.

Optimized Rate-Profiling for PAC Codes

Authors: He Sun, Emanuele Viterbo, Rongke Liu

Abstract: The polarization-adjusted convolutional (PAC) codes concatenate the polar transform and the convolutional transform to improve the decoding performance of the finite-length polar codes, where the rate-profile is used to construct the PAC codes by setting the positions of frozen bits. However, the optimal rateprofile method of PAC codes is still unknown. In this paper, an optimized rate-profile alg… ▽ More The polarization-adjusted convolutional (PAC) codes concatenate the polar transform and the convolutional transform to improve the decoding performance of the finite-length polar codes, where the rate-profile is used to construct the PAC codes by setting the positions of frozen bits. However, the optimal rateprofile method of PAC codes is still unknown. In this paper, an optimized rate-profile algorithm of PAC codes is proposed. First, we propose the normalized compression factor (NCF) to quantify the transmission efficiency of useful information, showing that the distribution of useful information that needs to be transmitted after the convolutional transform should be adaptive to the capacity profile after finite-length polar transform. This phenomenon indicates that the PAC code improves the transmission efficiency of useful information, which leads to a better decoding performance than the polar codes with the same length. Then, we propose a novel rate-profile method of PAC codes, where a quadratic optimization model is established and the Euclidean norm of the NCF spectrum is adopted to construct the objective function. Finally, a heuristic bit-swapping strategy is designed to search for the frozen set with high objective function values, where the search space is limited by considering the only bits with medium Hamming weight of the row index. Simulation results show that the PAC codes with the proposed optimized rate-profile construction have better decoding performance than the PAC codes with the originally proposed Reed-Muller design construction. △ Less

Submitted 7 June, 2021; originally announced June 2021.

Orthogonal Time Sequency Multiplexing Modulation: Analysis and Low-Complexity Receiver Design

Authors: Tharaj Thaj, Emanuele Viterbo, Yi Hong

Abstract: This paper proposes orthogonal time sequency multiplexing (OTSM), a novel single carrier modulation scheme that places information symbols in the delay-sequency domain followed by a cascade of time-division multiplexing (TDM) and Walsh-Hadamard sequence multiplexing. Thanks to the Walsh Hadamard transform (WHT), the modulation and demodulation do not require complex domain multiplications. For the… ▽ More This paper proposes orthogonal time sequency multiplexing (OTSM), a novel single carrier modulation scheme that places information symbols in the delay-sequency domain followed by a cascade of time-division multiplexing (TDM) and Walsh-Hadamard sequence multiplexing. Thanks to the Walsh Hadamard transform (WHT), the modulation and demodulation do not require complex domain multiplications. For the proposed OTSM, we first derive the input-output relation in the delay-sequency domain and present a low complexity detection method taking advantage of zero-padding. We demonstrate via simulations that OTSM offers high performance gains over orthogonal frequency division multiplexing (OFDM) and similar performance to orthogonal time frequency space (OTFS), but at lower complexity owing to WHT. Then we propose a low complexity time-domain channel estimation method. Finally, we show how to include an outer error control code and a turbo decoder to improve error performance of the coded system. △ Less

Submitted 13 April, 2021; originally announced April 2021.

On Convolutional Precoding in PAC Codes

Authors: Mohammad Rowshan, Emanuele Viterbo

Abstract: Polarization-adjusted convolutional (PAC) codes are special concatenated codes in which we employ a one-to-one convolutional transform as a precoding step before the polar transform. In this scheme, the polar transform (as a mapper) and the successive cancellation process (as a demapper) present a synthetic vector channel to the convolutional transformation. The numerical results in the literature… ▽ More Polarization-adjusted convolutional (PAC) codes are special concatenated codes in which we employ a one-to-one convolutional transform as a precoding step before the polar transform. In this scheme, the polar transform (as a mapper) and the successive cancellation process (as a demapper) present a synthetic vector channel to the convolutional transformation. The numerical results in the literature show that this concatenation improves the weight distribution of polar codes which justifies the superior error correction performance of PAC codes relative to polar codes. In this work, we explicitly show why the convolutional precoding reduces the number of minimumweight codewords. Further analysis exhibits where the precoding stage is not effective. Then, we recognize weaknesses of the convolutional precoding which are unequal error protection (UEP) of the information bits due to rate profiling and lack of cross-segmental convolution. Finally, we assess the possibility of improving the precoding stage by proposing some irregular convolutional precodings. △ Less

Submitted 23 March, 2021; originally announced March 2021.

Low Complexity Precoding and Detection in Multi-user Massive MIMO OTFS Downlink

Authors: Brijesh Chander Pandey, Saif Khan Mohammed, P. Raviteja, Yi Hong, Emanuele Viterbo

Abstract: We consider the problem of degradation in performance of multi-carrier multi-user massive MIMO systems when channel induced Doppler spread is high. Recently, Orthogonal Time Frequency Space (OTFS) modulation has been shown to be robust to channel induced Doppler spread. In OTFS based systems, information symbols are embedded in the delay-Doppler (DD) domain where they are jointly modulated to gene… ▽ More We consider the problem of degradation in performance of multi-carrier multi-user massive MIMO systems when channel induced Doppler spread is high. Recently, Orthogonal Time Frequency Space (OTFS) modulation has been shown to be robust to channel induced Doppler spread. In OTFS based systems, information symbols are embedded in the delay-Doppler (DD) domain where they are jointly modulated to generate the time-domain transmit signal. Due to the multi-path delay and Doppler shifts, the DD domain information symbols need to be jointly demodulated at the receiver. For multi-carrier based communication (e.g., Orthogonal Frequency Division Multiplexing (OFDM)), massive MIMO systems have been shown to achieve high spectral and energy efficiency with low complexity multi-user precoding in the downlink. Extending the same to OTFS based downlink multi-user massive MIMO systems is challenging due to the requirement for joint demodulation of all information symbols at the user terminal (UT). In this paper, we solve this problem by proposing a novel OTFS based multi-user precoder at the base station (BS) and a corresponding low complexity detector (LCD) at the user terminals (UTs), which allows for separate demodulation of each DD domain information symbol at the UT. The complexity of the proposed precoder increases only linearly with increasing number BS antennas Q and the number of UTs. We show, through analysis, that as Q increases (with total transmitted power decreased linearly with Q), the proposed low complexity detector achieves a sum SE close to that achieved with optimal joint demodulation at each UT. Numerical simulations confirm our analysis and also show that the SE and error rate performance of the proposed OTFS based massive MIMO precoder and LCD detector is significantly more robust to channel induced Doppler spread when compared to OFDM based multi-user massive MIMO systems. △ Less

Submitted 24 November, 2020; originally announced November 2020.

Comments: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Polar Coded Repetition for Low-Capacity Channels

Authors: Fariba Abbasi, Hessam Mahdavifar, Emanuele Viterbo

Abstract: Constructing efficient low-rate error-correcting codes with low-complexity encoding and decoding have become increasingly important for applications involving ultra-low-power devices such as Internet-of-Things (IoT) networks. To this end, schemes based on concatenating the state-of-the-art codes at moderate rates with repetition codes have emerged as practical solutions deployed in various standar… ▽ More Constructing efficient low-rate error-correcting codes with low-complexity encoding and decoding have become increasingly important for applications involving ultra-low-power devices such as Internet-of-Things (IoT) networks. To this end, schemes based on concatenating the state-of-the-art codes at moderate rates with repetition codes have emerged as practical solutions deployed in various standards. In this paper, we propose a novel mechanism for concatenating outer polar codes with inner repetition codes which we refer to as polar coded repetition. More specifically, we propose to transmit a slightly modified polar codeword by deviating from Arikan's standard 2 x 2 Kernel in a certain number of polarization recursions at each repetition block. We show how this modification can improve the asymptotic achievable rate of the polar-repetition scheme, while ensuring that the overall encoding and decoding complexity is kept almost the same. The achievable rate is analyzed for the binary erasure channels (BEC). △ Less

Submitted 30 October, 2020; originally announced October 2020.

OTFS Based Random Access Preamble Transmission For High Mobility Scenarios

Authors: Alok Kumar Sinha, Saif Khan Mohammed, P. Raviteja, Yi Hong, Emanuele Viterbo

Abstract: We consider the problem of uplink timing synchronization for Orthogonal Time Frequency Space (OTFS) modulation based systems where information is embedded in the delay-Doppler (DD) domain. For this, we propose a novel Random Access (RA) preamble waveform based on OTFS modulation. We also propose a method to estimate the round-trip propagation delay between a user terminal (UT) and the base station… ▽ More We consider the problem of uplink timing synchronization for Orthogonal Time Frequency Space (OTFS) modulation based systems where information is embedded in the delay-Doppler (DD) domain. For this, we propose a novel Random Access (RA) preamble waveform based on OTFS modulation. We also propose a method to estimate the round-trip propagation delay between a user terminal (UT) and the base station (BS) based on the received RA preambles in the DD domain. This estimate (known as the timing advance estimate) is fed back to the respective UTs so that they can advance their uplink timing in order that the signal from all UTs in a cell is received at the BS in a time-synchronized manner. Through analysis and simulations we study the impact of OTFS modulation parameters of the RA preamble on the probability of timing error, which gives valuable insights on how to choose these parameters. Exhaustive numerical simulations of high mobility scenarios suggests that the timing error probability (TEP) performance of the proposed OTFS based RA is much more robust to channel induced multi-path Doppler shift when compared to the RA method in Fourth Generation (4G) systems. △ Less

Submitted 24 October, 2020; originally announced October 2020.

Comments: Accepted in IEEE Transactions on Vehicular Technology. Copyright 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses (see IEEE Publication Services and Products Board Operations Manual)

Journal ref: IEEE Transactions on Vehicular Technology, vol. 69, no. 12, December 2020

Index Coding at the WiFi Edge: An Implementation Study for Video Delivery

Authors: Lalhruaizela Chhangte, Emanuele Viterbo, D Manjunath, Nikhil Karamchandani

Abstract: HTTP based video streaming has become the de facto standard for video content delivery across different video streaming services. However, video content delivery continues to be challenged at the wireless edge by inadequate and highly variable bandwidth. In this paper, we describe WiCode, a platform that improves HTTP based video content delivery at the WiFi edge. WiCode uses coded delivery at the… ▽ More HTTP based video streaming has become the de facto standard for video content delivery across different video streaming services. However, video content delivery continues to be challenged at the wireless edge by inadequate and highly variable bandwidth. In this paper, we describe WiCode, a platform that improves HTTP based video content delivery at the WiFi edge. WiCode uses coded delivery at the WiFi AP to reduce data transmissions in order to improve the perceived performance of video streaming at the users. WiCode performs index coding on video segments to reduce the number of bits transmitted. Further, it also performs index coding on UDP packets that are retransmitted to reduce the number of bits transmitted. This paper describes the design and implementation of WiCode, and the practical gains achievable due to employing coded delivery in a real system taking into account the overheads introduced by WiCode. The WiCode module at the client side is a browser plugin that does not require any client side device configuration changes. We also show the effect of variable and fixed length segment size on the perceived performance of WiCode. △ Less

Submitted 27 July, 2020; originally announced July 2020.

Comments: International Conference on Signal Processing and Communications (SPCOM 2020)

List Viterbi Decoding of PAC Codes

Authors: Mohammad Rowshan, Emanuele Viterbo

Abstract: Polarization-adjusted convolutional (PAC) codes are special concatenated codes in which we employ a one-to-one convolutional transform as a pre-coding step before the polar transform. In this scheme, the polar transform (as a mapper) and the successive cancellation process (as a demapper) present a synthetic vector channel to the convolutional transformation. The numerical results show that this c… ▽ More Polarization-adjusted convolutional (PAC) codes are special concatenated codes in which we employ a one-to-one convolutional transform as a pre-coding step before the polar transform. In this scheme, the polar transform (as a mapper) and the successive cancellation process (as a demapper) present a synthetic vector channel to the convolutional transformation. The numerical results show that this concatenation improves the Hamming distance properties of polar codes. In this work, we implement the parallel list Viterbi algorithm (LVA) and show how the error correction performance moves from the poor performance of the Viterbi algorithm (VA) to the superior performance of list decoding by changing the constraint length, list size, and the sorting strategy (local sorting and global sorting) in the LVA. Also, we analyze the latency of the local sorting of the paths in LVA relative to the global sorting in the list decoding and the trade-off between the sorting latency and the error correction performance. △ Less

Submitted 10 July, 2020; originally announced July 2020.

Large Kernel Polar Codes with efficient Window Decoding

Authors: Fariba Abbasi, Emanuele Viterbo

Abstract: In this paper, we modify polar codes constructed with some 2^t x 2^t polarization kernels to reduce the time complexity of the window decoding. This modification is based on the permutation of the columns of the kernels. This method is applied to some of the kernels constructed in the literature of size 16 and 32, with different error exponents and scaling exponents such as eNBCH kernel. It is sho… ▽ More In this paper, we modify polar codes constructed with some 2^t x 2^t polarization kernels to reduce the time complexity of the window decoding. This modification is based on the permutation of the columns of the kernels. This method is applied to some of the kernels constructed in the literature of size 16 and 32, with different error exponents and scaling exponents such as eNBCH kernel. It is shown that this method reduces the complexity of the window decoding significantly without affecting the performance. △ Less

Submitted 9 October, 2020; v1 submitted 22 May, 2020; originally announced May 2020.

Decoding of NB-LDPC codes over Subfields

Authors: V. B. Wijekoon, Emanuele Viterbo, Yi Hong

Abstract: The non-binary low-density parity-check (NB-LDPC) codes can offer promising performance advantages but suffer from high decoding complexity. To tackle this challenge, in this paper, we consider NB-LDPC codes over finite fields as codes over \textit{subfields} as a means of reducing decoding complexity. In particular, our approach is based on a novel method of expanding a non-binary Tanner graph ov… ▽ More The non-binary low-density parity-check (NB-LDPC) codes can offer promising performance advantages but suffer from high decoding complexity. To tackle this challenge, in this paper, we consider NB-LDPC codes over finite fields as codes over \textit{subfields} as a means of reducing decoding complexity. In particular, our approach is based on a novel method of expanding a non-binary Tanner graph over a finite field into a graph over a subfield. This approach offers several decoding strategies for a single NB-LDPC code, with varying levels of performance-complexity trade-offs. Simulation results demonstrate that in a majority of cases, performance loss is minimal when compared with the complexity gains. △ Less

Submitted 9 July, 2020; v1 submitted 15 May, 2020; originally announced May 2020.

Comments: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

PAC Codes: Sequential Decoding vs List Decoding

Authors: Mohammad Rowshan, Andreas Burg, Emanuele Viterbo

Abstract: In the Shannon lecture at the 2019 International Symposium on Information Theory (ISIT), Arıkan proposed to employ a one-to-one convolutional transform as a pre-coding step before the polar transform. The resulting codes of this concatenation are called polarization-adjusted convolutional (PAC) codes. In this scheme, a pair of polar mapper and demapper as pre- and postprocessing devices are deploy… ▽ More In the Shannon lecture at the 2019 International Symposium on Information Theory (ISIT), Arıkan proposed to employ a one-to-one convolutional transform as a pre-coding step before the polar transform. The resulting codes of this concatenation are called polarization-adjusted convolutional (PAC) codes. In this scheme, a pair of polar mapper and demapper as pre- and postprocessing devices are deployed around a memoryless channel, which provides polarized information to an outer decoder leading to improved error correction performance of the outer code. In this paper, the list decoding and sequential decoding (including Fano decoding and stack decoding) are first adapted for use to decode PAC codes. Then, to reduce the complexity of sequential decoding of PAC/polar codes, we propose (i) an adaptive heuristic metric, (ii) tree search constraints for backtracking to avoid exploration of unlikely sub-paths, and (iii) tree search strategies consistent with the pattern of error occurrence in polar codes. These contribute to the reduction of the average decoding time complexity from 50% to 80%, trading with 0.05 to 0.3 dB degradation in error correction performance within FER=10^-3 range, respectively, relative to not applying the corresponding search strategies. Additionally, as an important ingredient in Fano decoding of PAC/polar codes, an efficient computation method for the intermediate LLRs and partial sums is provided. This method is effective in backtracking and avoids storing the intermediate information or restarting the decoding process. Eventually, all three decoding algorithms are compared in terms of performance, complexity, and resource requirements. △ Less

Submitted 17 January, 2024; v1 submitted 17 February, 2020; originally announced February 2020.

Comments: 14 pages, 12 figures, 1 table, 6 algorithms

Journal ref: IEEE TVT, Vol. 70, No. 2, Feb 2021, Pages 1434-1447

Geometry based Stochastic Channel Modeling using Ambit Processes

Authors: Rakesh R. T., Emanuele Viterbo

Abstract: The simulation of vehicular wireless channels using geometry-based radio channel models is computationally intensive when the number of scatterers is significantly high. In this paper, we propose a new geometry-based stochastic channel model to simulate and analyze the aforementioned channels based on a framework developed from the theory of ambit processes. Under reasonable assumptions, the under… ▽ More The simulation of vehicular wireless channels using geometry-based radio channel models is computationally intensive when the number of scatterers is significantly high. In this paper, we propose a new geometry-based stochastic channel model to simulate and analyze the aforementioned channels based on a framework developed from the theory of ambit processes. Under reasonable assumptions, the underlying mathematical structure of the proposed channel model enables the characterization of high mobility channels in terms of fading statistics, spatio-temporal channel correlation, and Doppler spectrum, besides ensuring tractable analysis. The developed algorithm facilitates fast simulation of high mobility channels and accounts for key features of vehicular channels including appearance and disappearance of multi-path components, spatial consistency, and captures the correlation between time-evolving delay and Doppler associated with multi-path components. Finally, we carry out simulations to obtain crucial insights about the characteristics of typical vehicle-to-infrastructure channels based on the proposed channel model. △ Less

Submitted 30 January, 2020; originally announced January 2020.

Shifted Pruning for List Decoding of Polar Codes

Authors: Mohammad Rowshan, Emanuele Viterbo

Abstract: In successive cancellation list (SCL) decoding, the tree pruning operation retains the L best paths with respect to metric at every decoding step. However, the correct path might be among the L worst paths due to imposed penalties. In this case, the correct path is pruned and the decoding process fails. In this work, we propose a scheme for additional decoding attempts when decoding fails, in whic… ▽ More In successive cancellation list (SCL) decoding, the tree pruning operation retains the L best paths with respect to metric at every decoding step. However, the correct path might be among the L worst paths due to imposed penalties. In this case, the correct path is pruned and the decoding process fails. In this work, we propose a scheme for additional decoding attempts when decoding fails, in which the pruning window does not necessarily select the L best paths, but this window is shifted between positions 1 and 2L in the sorted list. In the simplest form, the L worst paths are selected at the decoding step where the probability of elimination of the correct paths is high. Additionally, we generalize the scheme and propose a number of variants such as constrained shifting, nested shifting and shifting under segmented decoding, aiming to reduce the computational complexity. The numerical results for polar codes of length 512 with code rates 0.5 and 0.8 and list sizes L=2, 8, 32, show that the shifted-pruning scheme can provide 0.25-0.5 dB gain in error correction performance, while the average computational complexity approaches the conventional list decoding complexity at practical FER ranges. △ Less

Submitted 29 January, 2020; originally announced January 2020.

Low Complexity Iterative Rake Detector for Orthogonal Time Frequency Space Modulation

Authors: Tharaj Thaj, Emanuele Viterbo

Abstract: This paper presents a linear complexity iterative rake detector for the recently proposed orthogonal time frequency space (OTFS) modulation scheme. The basic idea is to extract and combine the received multipath components of the transmitted symbols in the delay-Doppler grid using linear diversity combining schemes like maximal ratio combining (MRC), equal gain combining and selection combining to… ▽ More This paper presents a linear complexity iterative rake detector for the recently proposed orthogonal time frequency space (OTFS) modulation scheme. The basic idea is to extract and combine the received multipath components of the transmitted symbols in the delay-Doppler grid using linear diversity combining schemes like maximal ratio combining (MRC), equal gain combining and selection combining to improve the SNR of the combined signal. We reformulate the OTFS input-output relation in the vector form by placing some null symbols in the delay-Doppler grid thereby exploiting the block circulant property of the channel matrix. Using the new input-output relation we propose a low complexity iterative detector based on the MRC scheme. The bit error rate (BER) performance of the proposed detector will be compared with the state of the art message passing detector and orthogonal frequency division multiplexing (OFDM) scheme employing a single tap minimum mean square error (MMSE) equalizer. We also show that the frame error rate (FER) performance of the MRC detector can be improved by employing error correcting codes operating in the form of a turbo decision feedback equalizer (DFE). △ Less

Submitted 29 January, 2020; originally announced January 2020.

Comments: Accepted in IEEE Wireless Communications and Networking Conference (WCNC), 2020

Online Caching and Coding at the WiFi Edge: Gains and Tradeoffs

Authors: Lalhruaizela Chhangte, Emanuele Viterbo, D Manjunath, Nikhil Karamchandani

Abstract: Video content delivery at the wireless edge continues to be challenged by insufficient bandwidth and highly dynamic user behavior which affects both effective throughput and latency. Caching at the network edge and coded transmissions have been found to improve user performance of video content delivery. The cache at the wireless edge stations (BSs, APs) and at the users' end devices can be popula… ▽ More Video content delivery at the wireless edge continues to be challenged by insufficient bandwidth and highly dynamic user behavior which affects both effective throughput and latency. Caching at the network edge and coded transmissions have been found to improve user performance of video content delivery. The cache at the wireless edge stations (BSs, APs) and at the users' end devices can be populated by pre-caching content or by using online caching policies. In this paper, we propose a system where content is cached at the user of a WiFi network via online caching policies, and coded delivery is employed by the WiFi AP to deliver the requested content to the user population. The content of the cache at the user serves as side information for index coding. We also propose the LFU-Index cache replacement policy at the user that demonstrably improves index coding opportunities at the WiFi AP for the proposed system. Through an extensive simulation study, we determine the gains achieved by caching and index by coding. Next, we analyze the tradeoffs between them in terms of data transmitted, latency, and throughput for different content request behaviors from the users. We also show that the proposed cache replacement policy performs better than traditional cache replacement policies like LRU and LFU. △ Less

Submitted 20 January, 2020; originally announced January 2020.

Steepest Gradient-Based Orthogonal Precoder For Integer-Forcing MIMO

Authors: Mohammad Nur Hasan, Brian M. Kurkoski, Amin Sakzad, Emanuele Viterbo

Abstract: In this paper, we develop an orthogonal precoding scheme for integer-forcing (IF) linear receivers using the steepest gradient algorithm. Although this scheme can be viewed as a special case of the unitary precoded integer-forcing (UPIF), it has two major advantages. First, the orthogonal precoding outperforms its unitary counterpart in terms of achievable rate, outage probability, and error rate.… ▽ More In this paper, we develop an orthogonal precoding scheme for integer-forcing (IF) linear receivers using the steepest gradient algorithm. Although this scheme can be viewed as a special case of the unitary precoded integer-forcing (UPIF), it has two major advantages. First, the orthogonal precoding outperforms its unitary counterpart in terms of achievable rate, outage probability, and error rate. We verify this advantage via theoretical and numerical analyses. Second, it exhibits lower complexity as the dimension of orthogonal matrices is half that of unitary matrices in the real-valued domain. For finding ``good'' orthogonal precoder matrices, we propose an efficient algorithm based on the steepest gradient algorithm that exploits the geometrical properties of orthogonal matrices as a Lie group. The proposed algorithm has low complexity and can be easily applied to an arbitrary MIMO configuration. We also confirm numerically that the proposed orthogonal precoding outperforms UPIF type II in some scenarios and the X-precoder in high-order QAM schemes, e.g., $64$- and $256$-QAM. △ Less

Submitted 19 April, 2019; originally announced April 2019.

Orthogonal Time Frequency Space (OTFS) Modulation Based Radar System

Authors: P. Raviteja, Khoa T. Phan, Yi Hong, Emanuele Viterbo

Abstract: Orthogonal time frequency space (OTFS) modulation was proposed to tackle the destructive Doppler effects in wireless communications, with potential applications to many other areas. In this paper, we investigate its application to radar systems, and propose a novel efficient OTFS-based matched filter algorithm for target range and velocity estimation. The proposed algorithm not only exhibits the i… ▽ More Orthogonal time frequency space (OTFS) modulation was proposed to tackle the destructive Doppler effects in wireless communications, with potential applications to many other areas. In this paper, we investigate its application to radar systems, and propose a novel efficient OTFS-based matched filter algorithm for target range and velocity estimation. The proposed algorithm not only exhibits the inherent advantages due to multi-carrier modulation of the existing orthogonal frequency division multiplexing (OFDM-) based radar algorithms but also provides additional benefits to improve radar capability. Similar to OFDM, OTFS spreads the transmitted signal in the entire time--frequency resources to exploit the full diversity gains for radar processing. However, OTFS requires less cyclic prefix, and hence, shorter transmission duration than OFDM, allowing longer range radar and/or faster target tracking rate. Additionally, unlike OFDM, OTFS is inter-carrier interference-free, enabling larger Doppler frequency estimation. We demonstrate the performance of the proposed algorithm using numerical results under different system settings. △ Less

Submitted 26 January, 2019; originally announced January 2019.

Fast Decoding of Low Density Lattice Codes

Authors: Shuiyin Liu, Yi Hong, Emanuele Viterbo, Alessia Marelli, Rino Micheloni

Abstract: Low density lattice codes (LDLC) are a family of lattice codes that can be decoded efficiently using a message-passing algorithm. In the original LDLC decoder, the message exchanged between variable nodes and check nodes are continuous functions, which must be approximated in practice. A promising method is Gaussian approximation (GA), where the messages are approximated by Gaussian functions. How… ▽ More Low density lattice codes (LDLC) are a family of lattice codes that can be decoded efficiently using a message-passing algorithm. In the original LDLC decoder, the message exchanged between variable nodes and check nodes are continuous functions, which must be approximated in practice. A promising method is Gaussian approximation (GA), where the messages are approximated by Gaussian functions. However, current GA-based decoders share two weaknesses: firstly, the convergence of these approximate decoders is unproven; secondly, the best known decoder requires $O(2^d)$ operations at each variable node, where $d$ is the degree of LDLC. It means that existing decoders are very slow for long codes with large $d$. The contribution of this paper is twofold: firstly, we prove that all GA-based LDLC decoders converge sublinearly (or faster) in the high signal-to-noise ratio (SNR) region; secondly, we propose a novel GA-based LDLC decoder which requires only $O(d)$ operations at each variable node. Simulation results confirm that the error correcting performance of proposed decoder is the same as the best known decoder, but with a much lower decoding complexity. △ Less

Submitted 14 June, 2018; originally announced June 2018.

Comments: submitted to IEEE Information Theory Workshop 2018

Interference Cancellation and Iterative Detection for Orthogonal Time Frequency Space Modulation

Authors: P. Raviteja, Khoa T. Phan, Yi Hong, Emanuele Viterbo

Abstract: The recently proposed orthogonal time frequency space (OTFS) modulation technique was shown to provide significant error performance advantages over orthogonal frequency division multiplexing (OFDM) in Doppler channels. In this paper, we derive the explicit input-output relation describing OTFS modulation and demodulation (mod/demod) for delay-Doppler channels. We analyze the interferences and dev… ▽ More The recently proposed orthogonal time frequency space (OTFS) modulation technique was shown to provide significant error performance advantages over orthogonal frequency division multiplexing (OFDM) in Doppler channels. In this paper, we derive the explicit input-output relation describing OTFS modulation and demodulation (mod/demod) for delay-Doppler channels. We analyze the interferences and develop a novel low-complexity yet efficient message passing (MP) algorithm for joint interference cancellation (IC) and symbol detection. The proposed MP algorithm can effectively compensate for a wide range of channel Doppler spreads. △ Less

Submitted 15 February, 2018; v1 submitted 14 February, 2018; originally announced February 2018.

Comments: 30 pages, 7 figures, 1 table

Low-Complexity Iterative Detection for Orthogonal Time Frequency Space Modulation

Authors: P. Raviteja, Khoa T. Phan, Qianyu Jin, Yi Hong, Emanuele Viterbo

Abstract: We elaborate on the recently proposed orthogonal time frequency space (OTFS) modulation technique, which provides significant advantages over orthogonal frequency division multiplexing (OFDM) in Doppler channels. We first derive the input--output relation describing OTFS modulation and demodulation (mod/demod) for delay--Doppler channels with arbitrary number of paths, with given delay and Doppler… ▽ More We elaborate on the recently proposed orthogonal time frequency space (OTFS) modulation technique, which provides significant advantages over orthogonal frequency division multiplexing (OFDM) in Doppler channels. We first derive the input--output relation describing OTFS modulation and demodulation (mod/demod) for delay--Doppler channels with arbitrary number of paths, with given delay and Doppler values. We then propose a low-complexity message passing (MP) detection algorithm, which is suitable for large-scale OTFS taking advantage of the inherent channel sparsity. Since the fractional Doppler paths (i.e., not exactly aligned with the Doppler taps) produce the inter Doppler interference (IDI), we adapt the MP detection algorithm to compensate for the effect of IDI in order to further improve performance. Simulations results illustrate the superior performance gains of OTFS over OFDM under various channel conditions. △ Less

Submitted 27 September, 2017; originally announced September 2017.

Comments: 6 pages, 7 figures

Layered Space-Time Index Coding

Authors: Yu-Chih Huang, Yi Hong, Emanuele Viterbo, Lakshmi Natarajan

Abstract: Multicasting $K$ independent messages via multiple-input multiple-output (MIMO) channels to multiple users where each user already has a subset of messages as side information is studied. A general framework of constructing layered space-time index coding (LSTIC) from a large class of space-time block codes (STBC), including perfect STBC, is proposed. We analyze the proposed LSTIC and show that it… ▽ More Multicasting $K$ independent messages via multiple-input multiple-output (MIMO) channels to multiple users where each user already has a subset of messages as side information is studied. A general framework of constructing layered space-time index coding (LSTIC) from a large class of space-time block codes (STBC), including perfect STBC, is proposed. We analyze the proposed LSTIC and show that it provides minimum determinant gains that are exponential with the amount of information contained in the side information for any possible side information. When constructed over a perfect STBC, the proposed LSTIC is itself a perfect STBC and hence many desired properties are preserved. To illustrate, we construct LSTIC over the following well-known STBCs: Golden code; $3\times 3$, $4\times 4$, $6\times 6$ perfect STBCs; and Alamouti code. Simulation results show that the obtained side information gain can be well predicted by our analysis. △ Less

Submitted 13 September, 2017; originally announced September 2017.

Comments: 27 pages, 5 figures

Optimal Power Allocation Strategies in Full-duplex Relay Networks

Authors: Alessandro Nordio, Carla Fabiana Chiasserini, Emanuele Viterbo

Abstract: In this work, we consider a dual-hop, decode-and-forward network where the relay can operate in full- duplex (FD) or half-duplex (HD) mode. We model the residual self-interference as an additive Gaussian noise with variance proportional to the relay transmit power, and we assume a Gaussian input distribution at the source. Unlike previous work, we assume that the source is only aware of the transm… ▽ More In this work, we consider a dual-hop, decode-and-forward network where the relay can operate in full- duplex (FD) or half-duplex (HD) mode. We model the residual self-interference as an additive Gaussian noise with variance proportional to the relay transmit power, and we assume a Gaussian input distribution at the source. Unlike previous work, we assume that the source is only aware of the transmit power distribution adopted by the relay over a given time horizon, but not of the symbols that the relay is currently transmitting. This assumption better reflects the practical situation where the relay node also forwards signaling traffic, or data originated by other sources. Under these conditions, we identify the optimal power allocation strategy at the source and relay, which in some cases coincides with the half duplex transmission mode. In particular, we prove that such strategy implies either FD transmissions over an entire frame, or FD/HD transmissions over a variable fraction of the frame. We determine the optimal transmit power level at the source and relay for each frame, or fraction thereof. We compare the performance of the proposed scheme against reference FD and HD techniques, which assume that the source is aware of the symbols instantaneously transmitted by the relay. Our results highlight that our scheme closely approaches or outperforms such reference strategies. △ Less

Submitted 4 August, 2017; originally announced August 2017.

Line codes generated by finite Coxeter groups

Authors: Ezio Biglieri, Emanuele Viterbo

Abstract: Using an algebraic approach based on the theory of Coxeter groups, we design, and describe the performance of, a class of line codes for parallel transmission of $b$ bits over $b+1$ wires that admit especially simple encoding and decoding algorithms. A number of designs are exhibited, some of them being novel or improving on previously obtained codes. Using an algebraic approach based on the theory of Coxeter groups, we design, and describe the performance of, a class of line codes for parallel transmission of $b$ bits over $b+1$ wires that admit especially simple encoding and decoding algorithms. A number of designs are exhibited, some of them being novel or improving on previously obtained codes. △ Less

Submitted 27 July, 2017; originally announced July 2017.

Comments: 19 pages, 10 figures

Golden-Coded Index Coding

Authors: Yu-Chih Huang, Yi Hong, Emanuele Viterbo

Abstract: We study the problem of constructing good space-time codes for broadcasting $K$ independent messages over a MIMO network to $L$ users, where each user demands all the messages and already has a subset of messages as side information. As a first attempt, we consider the $2\times 2$ case and propose golden-coded index coding by partitioning the golden codes into $K$ subcodes, one for each message. T… ▽ More We study the problem of constructing good space-time codes for broadcasting $K$ independent messages over a MIMO network to $L$ users, where each user demands all the messages and already has a subset of messages as side information. As a first attempt, we consider the $2\times 2$ case and propose golden-coded index coding by partitioning the golden codes into $K$ subcodes, one for each message. The proposed scheme is shown to have the property that for any side information configuration, the minimum determinant of the code increases exponentially with the amount of information contained in the side information. △ Less

Submitted 23 April, 2017; originally announced April 2017.

Comments: 5 pages, 2 figures. Accepted for publication in 2017 IEEE ISIT

Integer-Forcing Linear Receivers: A Design Criterion for Full-Diversity STBCs

Authors: J. Harshan, Amin Sakzad, Emanuele Viterbo

Abstract: In multiple-input multiple-output (MIMO) fading channels, the design criterion for full-diversity space-time block codes (STBCs) is primarily determined by the decoding method at the receiver. Although constructions of STBCs have predominantly matched the maximum-likelihood (ML) decoder, design criteria and constructions of full-diversity STBCs have also been reported for low-complexity linear rec… ▽ More In multiple-input multiple-output (MIMO) fading channels, the design criterion for full-diversity space-time block codes (STBCs) is primarily determined by the decoding method at the receiver. Although constructions of STBCs have predominantly matched the maximum-likelihood (ML) decoder, design criteria and constructions of full-diversity STBCs have also been reported for low-complexity linear receivers. A new receiver architecture called Integer-Forcing (IF) linear receiver has been proposed to MIMO channels by Zhan et al. which showed promising results for the high-rate V-BLAST encoding scheme. In this work we address the design of full-diversity STBCs for IF linear receivers. We derive an upper bound on the probability of decoding error, and show that STBCs that satisfy the non-vanishing singular value (NVS) property provide full-diversity for the IF receiver. We also present simulation results to demonstrate that linear designs with NVS property provide full diversity for IF receiver. As a special case of our analysis on STBCs, we present an upper bound on the error probability for the V-BLAST architecture presented by Zhan \emph{et al.}, and demonstrate that the IF linear receivers provide full receive diversity. Our results supplement the existing outage probability based results for the IF receiver. △ Less

Submitted 13 January, 2017; originally announced January 2017.

Comments: To appear in the Proc. of IEEE WCNC 2017. Substantial text overlap with arXiv:1308.4201v1

The Two-Modular Fourier Transform of Binary Functions

Authors: Yi Hong, Emanuele Viterbo, Jean-Claude Belfiore

Abstract: In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over $n$-bit vectors taking $m$-bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function $f:G\rightarrow {\cal R}$, where $G = (\mathbb{F}_2^n,+)$ is the group of $n$ bit vectors with bitwise modulo two addition $+$, and… ▽ More In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over $n$-bit vectors taking $m$-bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function $f:G\rightarrow {\cal R}$, where $G = (\mathbb{F}_2^n,+)$ is the group of $n$ bit vectors with bitwise modulo two addition $+$, and ${\cal R}$ is a finite commutative ring of characteristic $2$. Using the specific group structure of $G$ and a sequence of nested subgroups of $G$, we define the fast TMFT and its inverse. Since the image ${\cal R}$ of the binary functions is a ring, we can define the convolution between two functions $f:G\rightarrow {\cal R}$. We then provide the TMFT properties, including the convolution theorem, which can be used to efficiently compute convolutions. Finally, we derive the complexity of the fast TMFT and the inverse fast TMFT. △ Less

Submitted 30 March, 2016; v1 submitted 19 March, 2016; originally announced March 2016.

Comments: to appear in IEEE Trans. on Information Theory

New Error Correcting Codes for Informed Receivers

Authors: Lakshmi Natarajan, Yi Hong, Emanuele Viterbo

Abstract: We construct error correcting codes for jointly transmitting a finite set of independent messages to an 'informed receiver' which has prior knowledge of the values of some subset of the messages as side information. The transmitter is oblivious to the message subset already known to the receiver and performs encoding in such a way that any possible side information can be used efficiently at the d… ▽ More We construct error correcting codes for jointly transmitting a finite set of independent messages to an 'informed receiver' which has prior knowledge of the values of some subset of the messages as side information. The transmitter is oblivious to the message subset already known to the receiver and performs encoding in such a way that any possible side information can be used efficiently at the decoder. We construct and identify several families of algebraic error correcting codes for this problem using cyclic and maximum distance separable (MDS) codes. The proposed codes are of short block length, many of them provide optimum or near-optimum error correction capabilities and guarantee larger minimum distances than known codes of similar parameters for informed receivers. The constructed codes are also useful as error correcting codes for index coding when the transmitter does not know the side information available at the receivers. △ Less

Submitted 7 April, 2016; v1 submitted 24 January, 2016; originally announced January 2016.

Comments: Accepted for publication in 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona. Keywords: Cyclic codes, index coding, informed receivers, maximum distance separable codes, side information

Lattice Codes Achieve the Capacity of Common Message Gaussian Broadcast Channels with Coded Side Information

Authors: Lakshmi Natarajan, Yi Hong, Emanuele Viterbo

Abstract: Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios, including coding for the additive white Gaussian noise (AWGN) channel, dirty-paper channel, Wyner-Ziv coding, coding for relay networks and so forth. We consider the family of single-transmitter multiple-receiver… ▽ More Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios, including coding for the additive white Gaussian noise (AWGN) channel, dirty-paper channel, Wyner-Ziv coding, coding for relay networks and so forth. We consider the family of single-transmitter multiple-receiver Gaussian channels where the source transmits a set of common messages to all the receivers (multicast scenario), and each receiver has 'coded side information', i.e., prior information in the form of linear combinations of the messages. This channel model is motivated by applications to multi-terminal networks where the nodes may have access to coded versions of the messages from previous signal hops or through orthogonal channels. The capacity of this channel is known and follows from the work of Tuncel (2006), which is based on random coding arguments. In this paper, following the approach of Erez and Zamir, we design lattice codes for this family of channels when the source messages are symbols from a finite field 'Fp' of prime size. Our coding scheme utilizes Construction A lattices designed over the same prime field 'Fp', and uses algebraic binning at the decoders to expurgate the channel code and obtain good lattice subcodes, for every possible set of linear combinations available as side information. The achievable rate of our coding scheme is a function of the size 'p' of underlying prime field, and approaches the capacity as 'p' tends to infinity. △ Less

Submitted 17 December, 2017; v1 submitted 3 September, 2015; originally announced September 2015.

Comments: Accepted for publication in the IEEE Transactions on Information Theory

Oblivious Transfer over Wireless Channels

Authors: Jithin Ravi, Bikash Kumar Dey, Emanuele Viterbo

Abstract: We consider the problem of oblivious transfer (OT) over OFDM and MIMO wireless communication systems where only the receiver knows the channel state information. The sender and receiver also have unlimited access to a noise-free real channel. Using a physical layer approach, based on the properties of the noisy fading channel, we propose a scheme that enables the transmitter to send obliviously on… ▽ More We consider the problem of oblivious transfer (OT) over OFDM and MIMO wireless communication systems where only the receiver knows the channel state information. The sender and receiver also have unlimited access to a noise-free real channel. Using a physical layer approach, based on the properties of the noisy fading channel, we propose a scheme that enables the transmitter to send obliviously one-of-two files, i.e., without knowing which one has been actually requested by the receiver, while also ensuring that the receiver does not get any information about the other file. △ Less

Submitted 4 August, 2015; originally announced August 2015.

Comments: Submitted to Transactions on Communications

Capacity of Coded Index Modulation

Authors: Lakshmi Natarajan, Yi Hong, Emanuele Viterbo

Abstract: We consider the special case of index coding over the Gaussian broadcast channel where each receiver has prior knowledge of a subset of messages at the transmitter and demands all the messages from the source. We propose a concatenated coding scheme for this problem, using an index code for the Gaussian channel as an inner code/modulation to exploit side information at the receivers, and an outer… ▽ More We consider the special case of index coding over the Gaussian broadcast channel where each receiver has prior knowledge of a subset of messages at the transmitter and demands all the messages from the source. We propose a concatenated coding scheme for this problem, using an index code for the Gaussian channel as an inner code/modulation to exploit side information at the receivers, and an outer code to attain coding gain against the channel noise. We derive the capacity region of this scheme by viewing the resulting channel as a multiple-access channel with many receivers, and relate it to the 'side information gain' -- which is a measure of the advantage of a code in utilizing receiver side information -- of the inner index code/modulation. We demonstrate the utility of the proposed architecture by simulating the performance of an index code/modulation concatenated with an off-the-shelf convolutional code through bit-interleaved coded-modulation. △ Less

Submitted 30 June, 2015; originally announced July 2015.

Comments: To appear in Proc. IEEE Int. Symp. Inf. Theory (ISIT) 2015, Hong Kong, Jun. 2015. 5 pages, 4 figures

Index Codes for the Gaussian Broadcast Channel using Quadrature Amplitude Modulation

Authors: Lakshmi Natarajan, Yi Hong, Emanuele Viterbo

Abstract: We propose index codes, based on multidimensional QAM constellations, for the Gaussian broadcast channel, where every receiver demands all the messages from the source. The efficiency with which an index code exploits receiver side information in this broadcast channel is characterised by a code design metric called "side information gain". The known index codes for this broadcast channel enjoy la… ▽ More We propose index codes, based on multidimensional QAM constellations, for the Gaussian broadcast channel, where every receiver demands all the messages from the source. The efficiency with which an index code exploits receiver side information in this broadcast channel is characterised by a code design metric called "side information gain". The known index codes for this broadcast channel enjoy large side information gains, but do not encode all the source messages at the same rate, and do not admit message sizes that are powers of two. The index codes proposed in this letter, which are based on linear codes over integer rings, overcome both these drawbacks and yet provide large values of side information gain. With the aid of a computer search, we obtain QAM index codes for encoding up to 5 messages with message sizes 2^m, m <= 6. We also present the simulated performance of a new 16-QAM index code, concatenated with an off-the-shelf LDPC code, which is observed to operate within 4.3 dB of the broadcast channel capacity. △ Less

Submitted 27 May, 2015; originally announced May 2015.

Comments: Accepted for publication in IEEE Communications Letters. 4 pages, 2 figures, 1 table

Line of Sight 2 x nr MIMO with Random Antenna Orientations

Authors: Lakshmi Natarajan, Yi Hong, Emanuele Viterbo

Abstract: Line-of-sight (LoS) multiple-input multiple-output (MIMO) gives full spatial-multiplexing gain when the antenna array geometry and orientation are designed based on the inter-terminal distance. These known design methodologies, that hold for antenna arrays with fixed orientation, do not provide full MIMO gains for arbitrary array orientations. In this paper, we study LoS MIMO channels with random… ▽ More Line-of-sight (LoS) multiple-input multiple-output (MIMO) gives full spatial-multiplexing gain when the antenna array geometry and orientation are designed based on the inter-terminal distance. These known design methodologies, that hold for antenna arrays with fixed orientation, do not provide full MIMO gains for arbitrary array orientations. In this paper, we study LoS MIMO channels with random array orientations when the number of transmit antennas used for signalling is 2. We study the impact of common array geometries on error probability, and identify the code design parameter that describes the high signal-to-noise ratio (SNR) error performance of an arbitrary coding scheme. For planar receive arrays, the error rate is shown to decay only as fast as that of a rank 1 channel, and no better than 1/SNR^3 for a class of coding schemes that includes spatial multiplexing. We then show that for the tetrahedral receive array, which uses the smallest number of antennas among non-planar arrays, the error rate decays faster than that of rank 1 channels and is exponential in SNR for every coding scheme. Finally, we design a LoS MIMO system that guarantees a good error performance for all transmit/receive array orientations and over a range of inter-terminal distances. △ Less

Submitted 9 November, 2016; v1 submitted 22 May, 2015; originally announced May 2015.

Comments: Accepted for publication in IEEE Transactions on Vehicular Technology. Keywords: Antenna array, array geometry, coding scheme, line-of-sight (LoS), multiple-input multiple-output (MIMO), probability of error

A Comparative Study of Polar Code Constructions for the AWGN Channel

Authors: Harish Vangala, Emanuele Viterbo, Yi Hong

Abstract: We present a comparative study of the performance of various polar code constructions in an additive white Gaussian noise (AWGN) channel. A polar code construction is any algorithm that selects $K$ best among $N$ possible polar bit-channels at the design signal-to-noise-ratio (design-SNR) in terms of bit error rate (BER). Optimal polar code construction is hard and therefore many suboptimal polar… ▽ More We present a comparative study of the performance of various polar code constructions in an additive white Gaussian noise (AWGN) channel. A polar code construction is any algorithm that selects $K$ best among $N$ possible polar bit-channels at the design signal-to-noise-ratio (design-SNR) in terms of bit error rate (BER). Optimal polar code construction is hard and therefore many suboptimal polar code constructions have been proposed at different computational complexities. Polar codes are also non-universal meaning the code changes significantly with the design-SNR. However, it is not known which construction algorithm at what design-SNR constructs the best polar codes. We first present a comprehensive survey of all the well-known polar code constructions along with their full implementations. We then propose a heuristic algorithm to find the best design-SNR for constructing best possible polar codes from a given construction algorithm. The proposed algorithm involves a search among several possible design-SNRs. We finally use our algorithm to perform a comparison of different construction algorithms using extensive simulations. We find that all polar code construction algorithms generate equally good polar codes in an AWGN channel, if the design-SNR is optimized. △ Less

Submitted 11 January, 2015; originally announced January 2015.

Comments: 9 pages, submitted, under revision of an IEEE journal