We introduce and investigate the opportunities of multiantenna communication schemes whose
training and feedback stages are interleaved and mutually interacting. Specifically, unlike the traditional
schemes where the transmitter first trains all of its antennas at once and then receives a single feedback
message, we consider a scenario where the transmitter instead trains its antennas one by one and receives
feedback information immediately after training each one of its antennas. The feedback message may
ask the transmitter to train another antenna; or, it may terminate the feedback/training phase and provide
the quantized codeword (e.g., a beamforming vector) to be utilized for data transmission. As a specific
application, we consider a multipleinput singleoutput system with t transmit antennas, a shortterm
power constraint P, and target data rate ρ. We show that for any t, the same outage probability as a
system with perfect transmitter and receiver channel state information can be achieved with a feedback
rate of R1 bits per channel state and via training R2 transmit antennas on average, where R1 and R2
are independent of t, and depend only on ρ and P. In addition, we design variablerate quantizers for
channel coefficients to further minimize the feedback rate of our scheme.
more »
« less
Polar Codes for the Deletion Channel: Weak and Strong Polarization
This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hiddenMarkov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polardecoding operations on this trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. Using this approach, we obtain a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cuberoot of the block length.
more »
« less
 NSFPAR ID:
 10173122
 Date Published:
 Journal Name:
 2019 IEEE International Symposium on Information Theory (ISIT)
 Page Range / eLocation ID:
 1362 to 1366
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is threefold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for reallife applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code. In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke MoriTanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almostoneparameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first nonbinary matrix whose scaling exponent is upperbounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization.more » « less

This paper applies probabilistic amplitude shaping (PAS) to cyclic redundancy check (CRC)aided tailbiting trelliscoded modulation (TCM). CRCTCMPAS produces practical codes for short block lengths on the additive white Gaussian noise (AWGN) channel. In the transmitter, equally likely message bits are encoded by a distribution matcher (DM) generating amplitude symbols with a desired distribution. A CRC is appended to the sequence of amplitude symbols, and this sequence is then encoded and modulated by TCM to produce realvalued channel input signals. This paper proves that the sign values produced by the TCM are asymptotically equally likely to be positive or negative. The CRCTCMPAS scheme can thus generate channel input symbols with a symmetric capacityapproaching probability mass function. The paper provides an analytical upper bound on the frame error rate of the CRCTCMPAS system over the AWGN channel. This FER upper bound is the objective function used for jointly optimizing the CRC and convolutional code. Additionally, this paper proposes a multicomposition DM, which is a collection of multiple constantcomposition DMs. The optimized CRCTCMPAS systems achieve frame error rates below the random coding union (RCU) bound in AWGN and outperform the shortblocklength PAS systems with various other forward error correction codes studied in [2].more » « less

Trellis based detection with pattern dependent noise prediction (PDNP) has become standard practice in the HDD industry. In a typical singletrack signal processing scheme, the received samples from the read head are first filtered by a linear equalizer with a 1D partial response (PR). The linear filter output flows into a trellisbased (e.g. BCJR) detector that employs a supertrellis based on the PR mask ISI channel and a 1D pattern dependent noise prediction (1D PDNP) algorithm. The effective channel model has a media noise term which models signal dependent noise due to, e.g., magnetic grains intersected by bit boundaries. The media noise can influence two or more bit readback values. The trellis detector sends soft estimates of the coded bits to a channel decoder, which outputs estimates of the user information bits. There are two problems with traditional PDNP. First, when the number of tracks Nt simultaneously processed is greater than one, e.g. in twodimensional magnetic recording (TDMR), the number of trellis states can become impractically large; this is the state explosion problem. Second, the relatively simple autoregressive noise model and linear prediction used in PDNP is somewhat restrictive and may not accurately represent the media noise, especially at high storage densities; this is the modeling problem. To address the state explosion problem, we separate the ISI detection and media noise prediction into two separate detectors and use the turboprinciple to exchange information between them, thus avoiding use of a supertrellis. To address the modeling problem, we design and train deep neural network (DNN) based media noise predictors. As DNN models are much more general than autoregressive models, they give a more accurate model of magnetic media noise than PDNP; this more accurate modeling results in reduced detector BERs compared to PDNP.more » « less

In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the wellestablished channel polarization to design capacityachieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a lowcomplexity decoding algorithm. We first show that given a binaryinput memoryless symmetric (BMS) channel $W$ and a constant $s \in (0, 1]$ , there exists a polarization kernel such that the corresponding polar code is capacityachieving with the rate of polarization $s/2$ , and the GM column weights being bounded from above by $N^{s}$ . To improve the sparsity versus error rate tradeoff, we devise a columnsplitting algorithm and two coding schemes for BEC and then for general BMS channels. The polarbased codes generated by the two schemes inherit several fundamental properties of polar codes with the original $2 \times 2$ kernel including the decay in error probability, decoding complexity, and the capacityachieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in $N$ , while the original polar codes have some column weights that are linear in $N$ . In particular, for any BEC and $\beta < 0.5$ , the existence of a sequence of capacityachieving polarbased codes where all the GM column weights are bounded from above by $N^{\lambda} $ with $\lambda \approx 0.585$ , and with the error probability bounded by ${\mathcal {O}}(2^{N^{\beta }})$ under a decoder with complexity ${\mathcal {O}}(N\log N)$ , is shown. The existence of similar capacityachieving polarbased codes with the same decoding complexity is shown for any BMS channel and $\beta < 0.5$ with $\lambda \approx 0.631$ .more » « less