CRC-Aided Short Convolutional Codes and RCU
Bounds for Orthogonal Signaling
Jacob King∗†, William Ryan†, and Richard D. Wesel∗
∗Department of Electrical and Computer Engineering, University of California, Los Angeles, Los Angeles, CA 90095, USA
†Zeta Associates, Aurora, Denver, CO 80011, USA
Email: jacob.king@ucla.edu, ryan-william@zai.com, wesel@ucla.edu,
Abstract—We extend earlier work on the design of convo-
lutional code-specific CRC codes to Q-ary alphabets, with an
eye toward Q-ary orthogonal signaling. Starting with distance-
spectrum optimal, zero-terminated, Q-ary convolutional codes,
we design Q-ary CRC codes so that the CRC/convolutional
concatenation is distance-spectrum optimal. The Q-ary code
symbols are mapped to a Q-ary orthogonal signal set and
sent over an AWGN channel with noncoherent reception. We
focus on Q= 4, rate-1/2 convolutional codes in our designs.
The random coding union bound and normal approximation
are used in earlier works as benchmarks for performance
for distance-spectrum-optimal convolutional codes. We derive
a saddlepoint approximation of the random coding union bound
for the coded noncoherent signaling channel, as well as a normal
approximation for this channel, and compare the performance
of our codes to these limits. Our best design is within 0.6dB of
the RCU bound at a frame error rate of 10−4.
I. INTRODUCTION
A. Background
Phase coherency between transmitter and receiver is nec-
essary for optimal reception. However, phase coherency can
be difficult to achieve in practice, so orthogonal signaling
with noncoherent reception is often used. The most common
examples of orthogonal signal sets are Q-ary Hadamard
sequences and Q-ary frequency shift keying (QFSK) [1]. We
will assume the latter throughout this paper. Non-coherent
FSK signaling is of practical importance. It is currently used
in Bluetooth [2]. More recently the LoRa standard has adopted
noncoherent QFSK signaling [3] [4].
For values of Qgreater than 8, noncoherent QFSK loss
is small compared to coherent QFSK. In addition, for large
values of Q, noncoherent QFSK performs nearly as well as
BPSK signaling, at the expense of bandwidth. With these facts
in mind, developing good codes for noncoherent QFSK is very
important for contexts in which phase coherency is difficult or
impossible. This occurs when there is a high relative velocity
between the transmitter and the receiver or when the receiver
must be very simple or inexpensive. A natural code choice
for QFSK is a code based on a Q-ary alphabet so that code
symbols are directly mapped to modulation symbols.
This research is supported by Zeta Associates Inc. and National Science
Foundation (NSF) grant CCF-2008918. Any opinions, findings, and conclu-
sions or recommendations expressed in this material are those of the author(s)
and do not necessarily reflect views of Zeta Associates Inc. or NSF.
Binary convolutional codes concatenated with binary CRC
codes have been shown to perform very well on BPSK/QPSK
channels [5] [6] [7]. Following [5], we design Q-ary cyclic
redundancy check (CRC) codes to be concatenated with
optimal, Q-ary, zero-state-terminated convolutional codes
(ZTCC), where zeros are appended to the end of the CRC
word to force the convolutional encoder to terminate in the
zero state. We denote this concatenated code by CRC-ZTCC.
The Q-ary CRC code design criterion is optimization of
the distance spectrum of the concatenation of the CRC code
represented by g(x)and the convolutional code represented
by [g1(x)g2(x)], where each polynomial has Q-ary coeffi-
cients. With all operations over GF(Q), this concatenation is
equivalent to a Q-ary convolutional code with polynomials
[g(x)g1(x)g(x)g2(x)], which is ostensibly a catastrophic
convolutional code. However, rather than applying a Viterbi
decoder to this resultant code, we employ the list Viterbi
algorithm (LVA) [8]. The LVA produces a list of candidate
trellis paths in the original convolutional code trellis, ordered
by their likelihoods, and then chooses as its decision the most
likely path to pass the CRC check.
Design of codes for noncoherent orthogonal signaling has
been done for long messages in [9]–[12]. Here, we analyze
Q-ary CRC-ZTCC codes for short messages. Optimal Q-ary
convolutional codes for orthogonal signaling were described
by Ryan and Wilson [13]. We design distance-spectrum
optimal (DSO) CRCs for two of the codes in [13].
Since the pioneering work of Polyanskiy et al. [14], the
random coding union (RCU) bound has been used as a
measure of the performance quality of short-message binary
codes. The RCU bound is very difficult to calculate, but Font-
Segura et al. [15] derived a saddlepoint approximation for the
RCU bound that is more practical to calculate. In this paper
we extend their work to the noncoherent QFSK channel. We
also include here the normal approximation to the RCU bound
for its simplicity. A converse sphere packing bound was also
presented by Shannon [16] as a lower bound on error rate for
finite blocklength codes, and revisited by [17].
B. Contributions
This paper designs DSO Q-ary CRC codes for two 4-ary
ZTCCs selected from [13] and we apply their concatenation
to the noncoherent 4-FSK channel with list Viterbi decoding.
We also derive a saddlepoint approximation of the RCU
arXiv:2210.00026v1 [cs.IT] 30 Sep 2022