Search

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_{[\mu,\lambda,\omega]}(\rho)$ parameterized by integers $\rho \geq 2$, $\omega \geq 1$, $\lambda \geq 2$, and $\mu$ a multiple of $\lambda$. In this topology, the code has $\mu$ local codes with $\rho$ parity-check (p-c) constraints and a total of $\mu\rho$ p-c equations fully define the code. Next, we construct a class of block circulant (BC) codes ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ with blocklength $n=\mu(\rho+\omega)$, dimension $k=\mu\omega$ that instantiate $T_{[\mu,\lambda,\omega]}(\rho)$. Every local code of ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ is a $[\rho+\lambda\omega,\lambda\omega,\rho+1]$ generalized Reed-Solomon (RS) code. The overlap between supports of local codes helps to enhance the minimum distance $\rho+1$ to $2\rho+1$, without compromising much on the rate. We provide an efficient, parallelizable decoding algorithm to correct $2\rho$ erasures when $\lambda=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.

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.

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., Comment: To appear in the Proceedings of the 2024 IEEE International Symposium on Information Theory (ISIT)

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., Comment: 12 pages, TKDE format

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).

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$., Comment: Submitted to Designs, Codes and Cryptography

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., Comment: 22 pages, 11 figures

The Ponzi scheme, an old-fashioned fraud, is now popular on the Ethereum 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. This contract-code-based approach, while achieving very high accuracy, is not robust because a Ponzi developer can fool a detection model by obfuscating the opcode or inventing a new profit distribution logic that cannot be detected. On the contrary, 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. In this paper, we aim to improve the accuracy of the transaction-based models by employing time-series features, which turn out to be crucial in capturing the life-time behaviour a Ponzi application but were completely overlooked in previous works. We propose a new set of 85 features (22 known account-based and 63 new time-series features), which allows off-the-shelf machine learning algorithms to achieve up to 30% higher F1-scores compared to existing works., Comment: 17 pages, 9 figures, 4 tables

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\"{o}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.

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., Comment: Accepted at ESORICS 2023

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., Comment: 25 pages

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., Comment: 6 pages. 4 figures. To appear in the Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT)

This paper presents a low complexity detector for multiple-input multiple-output (MIMO) systems based on the recently proposed orthogonal time frequency space (OTFS) modulation. In the proposed detector, the copies of the transmitted symbol-vectors received through the different diversity branches (propagation paths and receive antennas) are linearly combined using the maximum ratio combining (MRC) technique to iteratively improve the signal to interference plus noise ratio (SINR) at the output of the combiner. To alleviate the performance degradation due to spatial correlation at the receiver antennas, we present a sample-based method to estimate such correlation and find the optimized combining weights for MRC from the estimated correlation matrix. The detector performance and complexity improve over the linear minimum mean square error (LMMSE) and message passing (MP) detectors proposed in the literature for MIMO-OTFS., Comment: Published in IEEE Wireless Communications Letters

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., Comment: Accepted for publication in IEEE Wireless Communications and Networking Conference, 10-13 April 2022, Austin, TX, USA

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}$., Comment: Accepted in IEEE Trans. Inf. Theory, 23 pages, 13 figures, 6 tables, 3 listings

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.

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.

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.

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.

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.

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., Comment: 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

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).

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., Comment: 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)

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., Comment: International Conference on Signal Processing and Communications (SPCOM 2020)

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.

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.

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., Comment: 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

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 coherently combine the received multipath components of the transmitted symbols in the delay-Doppler grid using maximal ratio combining (MRC) to improve the SNR of the combined signal. We reformulate the OTFS input-output relation in simple vector form by placing guard null symbols or zero padding (ZP) in the delay-Doppler grid and exploiting the resulting circulant property of the blocks of the channel matrix. Using this vector input-output relation we propose a low complexity iterative decision feedback equalizer (DFE) based on MRC. The performance and complexity of the proposed detector favorably compares with the state of the art message passing detector. An alternative time domain MRC based detector is also proposed for even faster detection. We further propose a Gauss-Seidel based over-relaxation parameter in the rake detector to improve the performance and the convergence speed of the iterative detection. We also show how the MRC detector can be combined with outer error-correcting codes to operate as a turbo DFE scheme to further improve the error performance. All results are compared with a baseline orthogonal frequency division multiplexing (OFDM) scheme employing a single tap minimum mean square error (MMSE) equalizer., Comment: arXiv admin note: text overlap with arXiv:2001.10703 Accepted for publication in IEEE Transactions on Vehicular Technology

In the Shannon lecture at the 2019 International Symposium on Information Theory (ISIT), Ar{\i}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., Comment: 14 pages, 12 figures, 1 table, 6 algorithms

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.

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.

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)., Comment: Accepted in IEEE Wireless Communications and Networking Conference (WCNC), 2020

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.

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.

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.

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., Comment: submitted to IEEE Information Theory Workshop 2018

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., Comment: 30 pages, 7 figures, 1 table

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., Comment: 6 pages, 7 figures

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., Comment: 27 pages, 5 figures

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.

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., Comment: 19 pages, 10 figures

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., Comment: 5 pages, 2 figures. Accepted for publication in 2017 IEEE ISIT

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., Comment: To appear in the Proc. of IEEE WCNC 2017. Substantial text overlap with arXiv:1308.4201v1