Steven J. Franke, K9AN and Joseph H. Taylor, K1JT
Address: 3314 E Anthony Dr., Urbana, IL 61802; s-franke@illiniois.edu; 272 Hartley Ave, Princeton, NJ 08540; k1jt@arrl.org

Open Source Soft-Decision
Decoder for the JT65 (63,12)
Reed-Solomon Code
Under-the-hood description of the JT65 decoding procedure, including awholly new algorithm for its powerful error-correcting code.

1 — Background and Motivation
The JT65 protocol has revolutionizedamateur-radio weak-signal communication
by enabling operators with small orcompromise antennas and relatively lowpower transmitters to communicate overpropagation paths not usable with traditional
technologies. The protocol was developedin 2003 for Earth-Moon-Earth (EME, or“moonbounce”) communication, where thescattered return signals are always weak.1
It was soon found that JT65 also enables
worldwide communication on the HF
bands with low power, modest antennas,
and efficient spectral usage. Thousands ofamateurs now use JT65 on a regular basis,making contacts on all bands from 160
meters through microwaves.
JT65 uses timed transmitting andreceiving sequences one minute long.
Messages are short and structured so as tostreamline minimal exchanges between two
amateur operators over potentially difficult
radio paths. Most messages contain two
callsigns and a grid locator, signal report,
acknowledgment, or sign-off; one of thetokens CQ, QRZ, or DE may be substituted
for the first callsign. Alternatively, a message
may contain up to 13 characters of arbitrary
text. All messages are efficiently compressed
into exactly 72 bits of digital information. Itshould be obvious that the JT65 protocol isintended for the basic purpose of completing
legitimate, documented two-way contacts,

8 QEX May/June 2016

but not for extended conversations. Fulldetails of the message structure and encoding
procedure were presented in an earlier
publication.1 For a concise description of theoverall process of transmitting and receivinga JT65 message, see the accompanying
sidebar JT65 Message Processing.
A major reason for the success andpopularity of JT65 is its use of a strong
error-correction code. Before transmission,
each 72-bit message is divided into 12
six-bit symbols and augmented with 51
additional symbols of error-correcting
information. These 51 parity symbols arecomputed according to information-theory
rules that maximize the probability ofcorrectly decoding the message, even if
many symbols are received incorrectly. The
JT65 code is properly described as a short
block-length, low-rate Reed-Solomon code
based on a 64-symbol alphabet. Charactersin this alphabet are mapped onto 64 different
frequencies for transmission.
Reed Solomon codes are widely used
to ensure reliability in data transmission
and storage. In hardware implementations,decoding is generally accomplished with aprocedure such as the Berlekamp-Massey(BM) algorithm, based on hard decisions
for each of the symbol values received. Soft1

Notes appear on page 17

Reprinted with permission © ARRL

decisions are potentially more powerful,
however. For each received JT65 symbol we
can estimate not only the value most likely
to be correct, but also the second, third, etc.,
most likely. Most importantly, we can also
estimate the probability that each of thosepossible values is the correct one. Decoders
that make use of such information are calledsoft-decision decoders.
Until now, nearly all programs
implementing JT65 have used the patented
Kötter-Vardy (KV) algebraic soft-decision
decoder, licensed to and implemented by
K1JT as a closed-source executable for use
only in amateur radio applications.2 Since
2001 the KV decoder has been considered
the best known soft-decision decoder for
Reed Solomon codes.
We describe here a new open-source
alternative called the Franke-Taylor (FT,or K9AN-K1JT) soft-decision decoding
algorithm. It is conceptually simple, built on
top of the BM hard-decision decoder, andin this application it performs even better
than the KV decoder. The FT algorithm
is implemented in the popular programs
WSJT, MAP65, and WSJT‑X, widely used
for amateur weak-signal communication
using JT65 and other specialized digital
protocols. These programs are open-source,
freely available, and licensed under the GNU
General Public License.3
The JT65 protocol specifies transmissions

that start one second into a UTC minute andlast for 46.8 seconds. Receiving software
therefore has more than ten seconds to decodea message before the start of the next minute,when the operator will send a reply. With
today’s personal computers, this relatively
long time encourages experimentation withdecoders of high computational complexity.
With time to spare, the FT algorithm lowers
the decoding threshold on a typical fading
channel by many decibels over the harddecision BM decoder, and by a meaningfulamount over the KV decoder. In addition toits excellent performance, the new algorithm
has other desirable properties, not least ofwhich is its conceptual simplicity. Decoding
performance and computational complexity
scale in a convenient way, providing steadily
increasing soft-decision decoding gain as
a tunable parameter is increased over morethan five orders of magnitude. Appreciable
gain is available from our decoder even onvery simple (and relatively slow) computers.
On the other hand, because the algorithm
benefits from a large number of independent
decoding trials, further performance gains
should be achievable through parallelization
on high-performance computers.
The remainder of this paper is organized
as follows. Section 2 presents a brief
overview of the nature of Reed Solomon
codes and their error-correcting capabilities.
Section 3 provides statistical motivation for
the FT algorithm, and Section 4 describes thealgorithm in full detail. Material in these two
sections is important because it documents
our approach and underlines its fundamental
technical contributions. These sections areheavier in formal mathematics than common
in QEX; for this reason, some readers may
choose to skip or skim them and proceed
more quickly to the results. Most readers will
benefit by reviewing the original paper on
the JT65 protocol.1 A procedure for hinted
decoding — determining which one, if any,of a list of likely messages matches the onethat was received — is outlined in Section 5.
Finally, in Section 6 we present performancemeasurements of the FT and hinted decoding
algorithms and make explicit comparisons to
the BM and KV decoders familiar to usersof older versions of WSJT, MAP65 and
WSJT‑X. Section 7 summarizes some on-theair experiences with the new decoder. Referto the sidebar Glossary of Specialized Terms
for brief definitions of some potentially
unfamiliar language.
2 — JT65 Messages and Reed
Solomon Codes
The JT65 message frame consists of ashort, compressed 72-bit message encoded
for transmission with a Reed-Solomoncode. Reed-Solomon codes are block

codes characterized by n, the length oftheir codewords; k, the number of message
symbols conveyed by the codeword; and thetransmission alphabet, or number of possible
values for each symbol in a codeword. The
codeword length and the number of message
symbols are specified with the notation(n, k). JT65 uses a (63,12) Reed-Solomoncode with an alphabet of 64 possible values
for each symbol. Each of the 12 message
symbols represents log264 = 6 message bits.
The source-encoded message conveyed
by a 63-symbol JT65 frame thus consistsof 72 information bits. The JT65 code issystematic, which means that the 12 message
symbols are embedded in the codeword
without modification and another 51 parity
symbols derived from the message symbols
are added to form a codeword of 63 symbols.
In coding theory the concept of Hamming
distance is used as a measure of disagreement
between different codewords, or between a
received word and a codeword. Hamming
distance is the number of code symbols thatdiffer in two words being compared. ReedSolomon codes have guaranteed minimum
Hamming distance d, whered = n − k + 1.

(1)

With n = 63 and k = 12 the minimum
Hamming distance of the JT65 code is
d = 52. With 72 information bits in eachmessage, JT65 can transmit any one of272 ≈ 4.7 ×1021 possible messages. The
codeword for any message differs fromevery other codeword in at least 52 of the 63
symbol positions.
A received word containing some errors(incorrect symbols) can be decoded into
the correct codeword using a deterministic,
algebraic algorithm provided that no morethan t symbols were received incorrectly,wheren − k  .
t= 2 

(2)

For the JT65 code t = 25, so it is always
possible to decode a received word having
25 or fewer symbol errors. Any one ofseveral well-known algebraic algorithms,
such as the BM algorithm, can carry out
this hard-decision decoding. Two steps arenecessarily involved in this process. We must
(1) determine which symbols were received
incorrectly, and (2) find the correct valueof the incorrect symbols. If we somehow
know that certain symbols are incorrect,
that information can be used to reduce thework involved in step (1) and allow step(2) to correct more than t errors. In theunlikely event that the location of every
error is known, and if no correct symbols
are accidentally labeled as errors, the BM
Reprinted with permission © ARRL

algorithm can correct up to d − 1 = n − kerrors.
The FT algorithm creates lists of symbols
suspected of being incorrect and sends themto the BM decoder. Symbols flagged in thisway are called erasures. With perfect erasure
information up to n − k =51 incorrect
symbols can be corrected for the JT65 code.
Imperfect erasure information means thatsome erased symbols may be correct, andsome other symbols in error. If s symbols are
erased and the remaining n − s symbols
contain e errors, the BM algorithm can findthe correct codeword as long as

s + 2e ≤ d − 1 .

(3)

If s = 0, the decoder is said to be an errorsonly decoder. If 0 < s ≤ d − 1 , the decoder
is called an errors-and-erasures decoder.
The possibility of doing errors-and-erasures
decoding lies at the heart of the FT algorithm.
On that foundation we have built a capability
for using soft information on the reliability of
individual symbol values, thereby producing
a soft-decision decoder.
3 — Statistical Framework
The FT algorithm uses the estimatedquality of received symbols to generate listsof symbols considered likely to be in error,
thus enabling decoding of received words
with more than 25 errors. Algorithms of thistype are generally called reliability-basedor probabilistic decoding methods.4 Suchalgorithms involve some amount of educatedguessing about which received symbols
are in error or, alternatively, about which
received symbols are correct. The guesses are
informed by quality metrics associated withthe received symbols. To illustrate why it isabsolutely essential to use such soft-symbol
information in these algorithms it helps toconsider what would happen if we tried touse completely random guesses, ignoring
any available soft-symbol information.
As a specific example, consider a received
JT65 word with 23 correct symbols and 40
errors. We do not know which symbols arein error. Suppose that the decoder randomly
selects s = 40 symbols for erasure, leaving
23 unerased symbols. According to Eq. (3),the BM decoder can successfully decode thisword as long as e, the number of errors present
in the 23 unerased symbols, is 5 or less. The
number of errors captured in the set of 40
erased symbols must therefore be at least 35.
The probability of selecting someparticular number of incorrect symbols
in a randomly selected subset of received
symbols is governed by the hypergeometricprobability distribution. Let us define N as
the number of symbols from which erasures
will be selected, X as the number of incorrect

QEX May/June 20169

Steven J. Franke, K9AN, 3314 E. Anthony Dr., Urbana, IL 61802: sQEX-5/16
Franke – Taylor
Page 1
franke@illinois.edu
over(63,12)
all possibleReedvalues up erased symbols is then submitted to the BM
symbolsin theset of N symbols,Decoderand x as exhaustive
Open theSourceSoft-Decision
for= 51,
theitsearch
JT65
to s Princeton,
turnsNJ
out 08540:
that for Xk1jt@arrl.org= 40 the best decoder, which produces either a codeword
numbererrors inK1JT,
the symbols
actually Ave.
JosephH.ofTaylor,272 Hartleyerased. In an ensemble of many received strategy is to erase s = 45 symbols. According or a flag indicating failure to decode.
The process of selecting the list ofwordsCodeX and x will be random variables, to Eq. (3), with s = 45 and d = 52 then e
Solomonbut for this example we will assume that must be 3 or less. Decoding will be assured symbols to erase and calling the BM decoder
X is known and that only x is random. The if the set of erased symbols contains at least comprises one cycle of the FT algorithm.
errors.
With sN = 63, X = 40, and The next cycle proceeds with a new selection
massE.function
forDr.,40
−3 =
37 IL
Steven conditional
J. Franke,probability
K9AN, 3314
Anthony
Urbana,61802:
x with stated values of N, X, and s may be s = 45, the probability of successful decode of erased symbols. At this stage we must
NOTE:asthe  symbol in 3 places
in a single try is P( x ≥ 37)  1.9 ×10−6 . This treat any codeword obtained by errorswritten
franke@illinois.edu
probability is about 8 times higher than the and-erasures decoding as no more than aprobability of success when only 40 symbols candidate. Our next task is to find a metric X  N  X 
Joseph H. Taylor, K1JT, 272
Hartley Ave. Princeton,
NJ 08540:
k1jt@arrl.org
 
were erased.
Nevertheless,the odds of that can reliably select one of many profferedε  s  ε P  x ε| N, X , s(4) successfully decoding on the first try are still candidates as the codeword that was actuallyN
only about 1 in 500,000.
transmitted.
 
The FT algorithm uses quality indicess
Example 3:
madeavailable by a noncoherent 64‑FSK
Examples 1 and 2 show that a random
demodulator (see the sidebar JT65 Message
strategyforselectingsymbolstoerase
isEquation
here it is again n(5)
 got mangled,n!
NOTE: the  symbol
unlikely to be successful unless we are Processing). The demodulator computes  = in 3 places
where  k  k !( n − k ) ! is the binomial prepared to wait a long time for an answer. binned power spectra for each signalingcoefficient. The binomial coefficient So let’s modify the strategy to tip the odds interval; the result is a two-dimensional array X  the function
 X  Nusing
S (i, j ) , where the frequency index i assumes
can be calculatedsthe numerical in our favor. Let the received word contain values 0 to 63 and the symbol index j has
n c h o o s e k (εn , ks) inεsymbols, as before, but ε| 
 P((4)

N, X,s=) x
N, X,s )X. = 40 incorrect(5)
P  x ε| N , X , sP( xlanguage
computingGNU
Octave,orj |withsuppose we know that 10 received symbols values 1 to 63. The most likely value for
j ε
N


one of many free online calculators. The are significantly more reliable than the other each symbol is taken as the frequency bin 
hypergeometric probability
mass function 53. We might therefore protect the 10 most with largest signal-plus-noise power over all s  in the
The
rest
of
the
edits
defined in Eq. (4) isare
availablePDF.
in GNU reliable symbols and select erasures from values of i. The fractions of total power in the
Octave as function hygepdf(x,N,X,s). the smaller set of N = 53 less reliable ones. two bins containing the largest and secondEquation (5) got mangled, here it is again
The cumulative probability that at least e If s = 45 symbols are chosen randomly largest powers, denoted respectively by p1 anderrors are captured in a subset of s erased for erasure in this way, it is still necessary p2, are computed for each symbol and passed
symbols selected from a group of N symbols for the erased symbols to include at least from demodulator to decoder as soft-symbol
containing X errors is
37 errors, as in Example 2. However, the information. The FT decoder derives twosprobabilities
are now much more favorable: metrics from p1 and p2, namely p1‑rank (theP( x  ε| N, X,s=)P( x 
j | N, X,s ) .
(5)		with N = 53, X = 40, and s = 45, Eq. (5) rank {1,2, …,63} of the symbol’s fractionalj εpower p1, j in a sorted list of p1 values) and the(5) yields
P( x ≥ 37)  0.016 . Even betterodds are obtained by choosing s = 47, which ratio p2/p1. High ranking symbols have larger
Example1:
The rest of the edits arein the PDF.
Suppose a received word contains X = 40 requires x ≥ 38 . With N = 53, X = 40, and signal-to-noise ratio than those with lower
incorrect symbols. In an attempt to decode s = 47, P ( x ≥ 38)  0.027 . The odds for rank. When p2/p1 is close to 1, the most likely
using an errors-and-erasures decoder, s = 40 producing a codeword on the first try are now symbol value is only slightly more reliable
symbols are randomly selected for erasure about 1 in 38. A few hundred independently than the second most likely one.
We use 3-bit quantization of the metrics
from the full set of N = n = 63 symbols. The randomized tries would be enough to all-butp
1‑rank and p2/p1 to index the entries in anprobability that x = 35 of the erased symbols guarantee production of a valid codeword by
8 × 8 table of symbol error probabilities. The
the BM decoder.
are actually incorrect is thenprobabilities were derived empirically froma large data set of received words that were 40   63 − 40 
4 — The Franke-Taylor Decoding
successfully decoded. The table provides
  35   40 − 35   2.4 ×10−7
Algorithm
an estimate of the a priori probability of
35
=
P=
x
(
)
.
 63 
Example 3 shows how statistical symbol error based on the metrics p1‑rank information about symbol quality should and p2/p1. This table is a key element of the 40 
make it possible to decode received frames
Similarly, the probability that x = 36 having a large number of errors. In practice algorithm, as it determines which symbolsof the erased symbols are incorrect is the number of errors in the received word is are effectively protected from erasure. Thea priori symbol error probabilities are close=P( x 36)  8.6 ×10−9 . S i n c e t h e unknown, so our algorithm simply assigns
probability of erasing 36 errors is so much a high erasure probability to low-quality to 1 for low-quality symbols and close tosmaller than that for erasing 35 errors, we symbols and relatively low probability 0 for high-quality symbols. Recall frommay safely conclude that the probability of to high-quality symbols. As illustrated Examples 2 and 3 that candidate codewords
randomly choosing an erasure vector that can by Example 3, a good choice of erasure are produced with higher probability when
decode the received word is approximately probabilities can increase the chance of the number of erased symbols is larger
than the number of incorrect symbols.
=P( x 35)  2.4 ×10−7 . T h e o d d s o f producing a codeword by many orders of
producing a valid codeword on the first try magnitude. Once erasure probabilities have Correspondingly, the FT algorithm works
best when the probability of erasing a symbol
are very poor, about 1 in 4 million.
been assigned to each of the 63 received is somewhat larger than the probability that
Example 2:
symbols, the FT algorithm uses a random the symbol is incorrect. For the JT65 code
How might we best choose the number number generator to decide whether or we found empirically that good decodingof symbols to erase, in order to maximize not to erase each symbol, according to its performance is obtained when the symbol
the probability of successful decoding? By assigned erasure probability. The list of erasure probability is about 1.3 times the

10 QEX May/June 2016

Reprinted with permission © ARRL

symbol error probability.
The FT algorithm tries successively to
decode the received word using independent
educated guesses to select symbols forerasure. For each iteration a stochastic
erasure vector is generated based on thesymbol erasure probabilities. The erasurevector is sent to the BM decoder alongwith the full set of 63 hard-decision symbol
values. When the BM decoder finds a
candidate codeword it is assigned a quality
metric ds, the soft distance between thereceived word and the codeword:

=
ds

n

∑ α (1 + p )
j =1

j

1, j

.

(6)

Here α j = 0 if received symbol j is thesame as the corresponding symbol in thecodeword, α j = 1 if the received symbol
and codeword symbol are different, and p1, j is
the fractional power associated with received
symbol j. Think of the soft distance as madeup of two terms: the first is the Hamming
distance between the received word andthe codeword, and the second ensures that
if two candidate codewords have the same
Hamming distance from the received word,a smaller soft distance will be assigned to theone where differences occur in symbols of
lower estimated reliability.
In practice we find that ds can reliably
identify the correct codeword if the signal-tonoise ratio for individual symbols is greaterthan about 4 in linear power units. We alsofind that significantly weaker signals can be
decoded by using soft-symbol information
beyond that contained in p1 and p2. To
this end we define an additional metric u,
the average signal-plus-noise power in allreceived symbols according to a candidate
codeword’s symbol values:u=

1 n∑ S (c j , j ) .
n j =1(7)

Here the cj’s are the symbol values for the
candidate codeword being tested.
The correct JT65 codeword produces avalue for u equal to the average of n = 63
bins containing both signal and noise power.
Incorrect codewords have at most k − 1 =11such bins and at least n − k + 1 =52 bins
containing noise only. Thus, if the spectral
array S (i, j ) has been normalized so thatthe average value of the noise-only bins
is unity, u for the correct codeword has
expectation value (average over many
random realizations) given by

uc = 1 + y ,(8)where y is the signal-to-noise ratio in linear
power units. If we assume Gaussian statistics

and a large number of trials, the standard
deviation of measured values of u is12

 1+ 2 y  .
(9)

 n 
In contrast, the expected value and standard
deviation of the u‑metric for an incorrect
codeword (randomly selected from a
population of all “worst case” codewords,
i.e., those with k ‑ 1 symbols identical tocorresponding ones in the correct word) are
given byσc = 

 k −1  ,ui = 1 + 
y
 n 

(10)

12
1
σ i =  n + 2 y ( k − 1)  ,

(11)

n

where the subscript i is an abbreviation for“incorrect”.
If u is evaluated for a large number ofdistinct candidate codewords, one of which iscorrect, we should expect the largest value u1
to be drawn from a population with statistics
described by uc and σ c . If no tested
codeword is correct, u1 is likely to come fromthe ( ui , σ i ) population and to be several
standard deviations above the mean. In eithercase the second-largest value, u2, will likely
come from the ( ui , σ i ) population, again
several standard deviations above the mean.
If the signal-to-noise ratio y is too small
for decoding to be possible or the correct
codeword is never presented as a candidate,
the ratio r = u2 u1 will likely be close to
1. On the other hand, correctly identified
codewords will produce u1 significantly
larger than u2 and thus smaller values of r.
We therefore apply a ratio threshold test,
say r < R 1 , to identify codewords with highprobability of being correct. As describedin Section 6, we use simulations to set an
empirical acceptance threshold R 1 thatmaximizes the probability of correct decodes
while ensuring a low rate of false positives.
As with all decoding algorithms thatgenerate a list of possible codewords, a
stopping criterion is necessary. FT accepts acodeword unconditionally if the Hamming
distance X and soft distance ds obey specified
criteria X < X 0 and d s < D0 . Secondary
acceptance criteria d s < D1 and r < R1 areused to validate additional codewords thatfail the first test. A timeout is used to limit
execution time if no acceptable codeword
is found in a reasonable number of trials, T.
Today’s personal computers are fast enoughthat T can be set as large as 105, or evenhigher. Pseudo-code for the FT algorithm
is presented in an accompanying box,
Algorithm 1.
Inspiration for the FT decoding algorithm
came from a number of sources.4,5,6 Afterdeveloping this algorithm, we became aware
Reprinted with permission © ARRL

that our approach is conceptually similar
to a stochastic, erasures-only list decoding
algorithm described in another reference.7
That algorithm is applied to higher-rate
Reed-Solomon codes on a symmetricchannel using binary phase-shift keying(BPSK). Our 64‑ary input channel with
64‑FSK modulation required us to develop
unique methods for assigning erasureprobabilities and for defining acceptancecriteria to select the best codeword from thelist of tested candidates.
5 — Hinted Decoding
The FT algorithm is completely general.
With equal sensitivity it can recover any oneof the 272 ≈ 4.7 ×1021 different messages
that can be transmitted with the JT65
protocol. In some circumstances it’s easy
to imagine a much smaller list of messages(say, a few thousand messages or less) thatwould be among the most likely ones to bereceived. One such favorable situation exists
when making short Amateur Radio contacts
that exchange minimal information including
callsigns, signal reports, perhaps Maidenhead
locators, and acknowledgments. On the EME
path or a VHF or UHF band with limited
geographical coverage, the most common
received messages frequently originate fromcallsigns that have been decoded before.
Saving a list of previously decoded callsigns
and associated locators makes it easy togenerate a list of hypothetical messages
and their corresponding codewords at very
little computational expense. The resulting
candidate codewords can be tested in almost
the same way as those generated by theprobabilistic method described in Section 4.
We call this approach “hinted decoding;” itis sometimes referred to as the Deep Searchalgorithm. In certain limited situations it can
provide enhanced sensitivity for the principal
task of any decoder, namely to determine
precisely what message was sent.
For hinted decoding we again invoke a
ratio threshold test, but in this case we use
it to answer a more limited question. Overthe full list of messages considered likely,
we want to know whether a suitable metriccan distinguish with confidence between the
one correct codeword and all others in thegenerated list — or, alternatively, to determinethat the correct codeword is not contained in
the list. We again find that the most effective
metric involves a comparison of u1 and u2,
the largest and second-largest values of total
signal-plus-noise power among all the tested
codewords. The criterion for comparison ischosen empirically to maximize the numberof correct decodes while ensuring that false
decodes are rare. Because tested candidate
codewords are drawn from a list typicallyno longer than a few thousand entries, rather
QEX May/June 201611

Eb /N0
Figure 1 — Word error rates as a function of Eb / N0, the signal-to-noise ratio per information bit. The curve labeled ‘Theory’ shows atheoretical prediction for the hard-decision BM decoder. Remaining curves represent simulation results on an AWGN channel for theBM, KV, and FT decoders. The KV algorithm was executed with complexity coefficient l = 15, the most aggressive setting historicallyused in the WSJT programs. The FT algorithm used timeout setting T = 105.

103

102

104
105

Figure 2 — Percent of JT65 messages copied as a function of SNR2500, assuming additive white Gaussian noise and no fading. Numbers
adjacent to curves specify values of timeout parameter for the FT decoder. Open circles and dotted line show results for the KV decoderwith complexity coefficient l = 15. Results for the BM algorithm are plotted with crosses and dashed line.

12 QEX May/June 2016

Reprinted with permission © ARRL

than 272, the limit can be more relaxed thanthat used in the FT algorithm. Thus, forthe limited subset of messages suggested
by previous experience to be likely, hinted
decodes can be obtained at lower signal
levels than required for the full universe of
272 possible messages. Pseudo-code for thehinted-decoding algorithm is presented as
Algorithm 2.
6 — Decoder Performance
Evaluation
Comparisons of decoding performance
are usually presented in the professional
literature as plots of word error rate versus
Eb / N 0 , the ratio of the energy collected
per information bit to the one-sided noise
power spectral density. For weak-signal
Amateur Radio work, performance ismore usefully presented as the probabilityof successfully decoding a received wordplotted against SNR 2500, the signal-to-noise
ratio in a 2500 Hz reference bandwidth. The
relationship between Eb / N 0 and SNR 2500 is
described in Appendix A. Examples of bothtypes of plot are included in the following
discussion, where we describe simulations
carried out to compare performance of the
FT algorithm and hinted decoding with otheralgorithms and with theoretical expectations.
We have also used simulations to establish
suitable default values for the acceptanceparameters X0, D0, D1, R1, and R2.
6.1 — Simulated results on the AWGN
channelResults of simulations using the BM, KV,
and FT decoding algorithms on the JT65
code are presented in terms of word error rateversus Eb / N 0 in Figure 1. For these tests
we generated at least 1000 signals at eachsignal-to-noise ratio, assuming the additive
white Gaussian noise (AWGN) channel, andwe processed the data using each algorithm.
For word error rates less than 0.1 it wasnecessary to process 10,000 or even 100,000
simulated signals in order to capture enougherrors to make the measurements statisticallymeaningful. As a test of the fidelity of
our numerical simulations, Figure 1 also
shows results calculated from theoreticalprobability distributions for comparison with
the BM results. The simulated BM results
agree with theory to within about 0.1 dB. The
differences are caused by small errors in theestimates of time and frequency offset of thereceived signal in the simulated data. Such“sync losses” are not accounted for in theidealized theoretical results.
As expected, on the AWGN channel thesoft-decision algorithms FT and KV areabout 2 dB better than the hard-decision
BM algorithm. In addition, FT has an edge
over KV that increases from about 0.2 dB athigher SNRs to nearly 0.5 dB at low SNR.
With timeout parameter T = 105 execution
time for FT is longer than that for the KV
algorithm, but still small enough to be fully
practical on today’s home computers.
Error-free transmission is important incommercial applications, so plots like Figure
1 are often extended downward to error ratesof 10‑6 or even less. The circumstances forminimal Amateur Radio contacts are very
different, however. Decoding failure ratesof order 0.1 or higher may be perfectly
acceptable: they simply require repeat
transmissions. In such circumstances theessential information is more usefully
presented in a plot showing the percentage oftransmissions copied correctly as a functionof signal-to-noise ratio. Figure 2 shows theFT and KV results from Figure 1 in thisformat, along with additional FT results for
T = 104, 103, 102 and 10. It’s easy to see that
the FT decoder produces more decodes than
KV when T is greater than about 3000. As
already noted in connection with Figure 1, FTwith T = 105 has approximately 0.5 dB gain
over KV at low SNR. It also provides verysignificant gains over the hard-decision BM
decoder, even when limited to very small T.
Parameter T in the FT algorithm is the
maximum number of symbol-erasure trials
allowed for a particular attempt at decodinga received word. Most successful decodes
take only a small fraction of the maximum
allowed number of trials. Figure 3 shows
the number of stochastic erasure trials
required to find the correct codeword plotted
as a function of X, the number of harddecision errors in the received word. This
test run used 1000 simulated transmissions
at SNR 2500 = −24 dB , just slightly above thedecoding threshold, with timeout parameter
T = 105. No points are shown for X ≤ 25
because all such words are successfully
decoded by a single run of the errors-only
BM algorithm. Figure 3 shows that the FT
algorithm decodes received words with as
many as X = 43 symbol errors. It also showsthat the average number of trials increases
with the number of errors in the received
word. The variability of decoding time also
increases dramatically with the number of
errors in the received word. These results
provide insight into the mean and varianceof execution time for the FT algorithm, since
execution time is roughly proportional to thenumber of required erasure trials.
6.2 — Simulated results for Rayleighfading and hinted decoding
Figure 4 presents the results of simulations
for signal-to-noise ratios ranging from −18 to−30 dB , again using 1000 simulated signals
for each plotted point. We include three
curves for each decoding algorithm: one for
the AWGN channel and no fading, and two
Reprinted with permission © ARRL

more for simulated Doppler spreads of 0.2
and 1.0 Hz. These simulated Doppler spreads
are comparable to those encountered on HF
ionospheric paths and also for EME at VHF
and the lower UHF bands. For comparison
we note that the JT65 symbol rate is about
2.7 Hz. It is interesting to note that while
Rayleigh fading severely degrades the
success rate of the BM decoder, the penalties
are much smaller with both FT and Deep
Search (DS) decoding. Simulated Doppler
spreads of 0.2 Hz actually increased the FT
decoding rate slightly at SNRs close to thedecoding threshold, presumably because withthe low-rate JT65 code, signal peaks provide
the information needed for good copy.
7 — On-the-air Experience
The JT65 protocol has proven remarkably
versatile. Today the mode is used bythousands of amateurs around the world,
communicating over terrestrial paths on the
MF and HF bands and over terrestrial aswell as EME paths from 50 MHz through10 GHz. Three submodes are in use,
together accommodating a wide range of
Doppler spreads and potential instrumental
instabilities. All three submodes transmit
the 63 data symbols interspersed with 63
synchronization symbols at keying rate
11025 / 4096 = 2.69 b a u d . S u b m o d e
JT65A uses tone spacing equal to thesymbol rate; its total occupied bandwidth is
66 × 2.69 =177.6 Hz . Submodes B and C
have tone spacings and occupied bandwidths
2 and 4 times larger. In practice JT65A is
generally used at 50 MHz and below, JT65B
on 144 through 432 MHz, and JT65C at
1296 MHz and above.
Figure 5 shows portions of the main
window and spectrogram displays fromprogram WSJT‑X, illustrating replies to a
CQ from K1JT on 144.118 MHz using
submode JT65B on the EME path. Speckled
vertical lines on the waterfall at 1494 and1515 Hz are the synchronizing tones ofsignals from DL7UAE and SP6GWB. Other
visible speckles (barely above the noise)
up to about 1870 Hz are some of the data
tones from these two stations. Two lines of
decoded text show that the estimated average
signal strengths were SNR 2500 = −23
and −24 dB , respectively, just one or twodB above decoding threshold for the FT
decoder. Note that the two signals overlap
throughout more than 90% of their occupied
bandwidths, yet both are decoded cleanly
and without errors. Such behavior is typicalof the JT65 protocol.
As another example, Figure 6 shows
activity in submode JT65A during a single
minute on the 20 m amateur band. At thistime the band was crowded with overlapping
signals. With care you can count at least 19
QEX May/June 2016

13

X
Figure 3 — Number of trials needed to decode a received word vs. Hamming distance X between received word and decoded codeword. We
used 1000 simulated transmissions on an AWGN channel with no fading. The signal-to-noise ratio was SNR2500 = –24 dB, or Eb / N0 = 5.1 dB.

100

80Percent copy

0
60

DS

0.2

40

20

0
-30

BM

FT
0.2

1.0

0

1.0

0.2

0
1.0

-28

-26

-24

-22

-20

-18

SNR in 2500 Hz Bandwidth (dB)Figure 4 — Percentage of JT65 messages successfully decoded as a function of SNR2500. Results are shown for the hard-decision BerlekampMassey (BM) and soft-decision Franke-Taylor (FT) decoding algorithms. Curves labeled ‘DS’ correspond to the hinted-decode (Deep Search)algorithm with a codeword list of length L = 5850. Numbers adjacent to the curves are simulated Doppler spreads in Hz. In the current version
of WSJT‑X the performance of the DS algorithm is limited by synchronization failures when SNR is less than about 28 dB.

14 QEX May/June 2016

Reprinted with permission © ARRL

distinct synchronizing tones (the speckled
vertical lines in the Figure), and can see
as many as four signals overlapping insome places. After signal processing todemodulate the signals and produce softsymbol data for the FT decoder, program
WSJT‑X extracts and decodes 21 error-freemessages from this recorded data segment.
This result is achieved with a relatively
small timeout parameter, T = 1000 . For
these results the decoder uses two successive
sweeps over the spectrum. The strongest
signals (12 in this example) are sequentiallydecoded and subtracted from the raw data
after the first pass. Another 9 signals are
decoded in the second pass. For comparison,
the hard-decision BM decoder decodes only
12 messages from this recording (9 in the firstpass and 3 more in a second).
Our implementation of the FT decoder,written in a combination of FORTRAN
and C, is freely available as open-sourcecode.8 For the Berlekamp-Massey part of thealgorithm we use routines written by Phil
Karn, KA9Q, modified slightly so that theReed-Solomon syndromes are computed only
once in our most time-consuming loop (Steps
2 through 8, Algorithm 1).9 The FT algorithm
has become an integral part of programs
WSJT, MAP65, and WSJT‑X. Improvement
in sensitivity over the Kötter-Vardy decoder issmall, only a few tenths of a dB, but especiallyon the EME path such small advantages are
sometimes very important. Perhaps evenmore essential, programs in the WSJT family
are now entirely open source. We no longer
need to use the patented KV algorithm or
the specially licensed executable program
kvasd[.exe].
8 — Acknowledgments
We thank Charlie Suckling, G3WDG;
Bill Somerville, G4WJS; Casey Smith,
KD9DSW; Edson Pereira, PY2SDR;
Leif Asbrink, SM5BSZ; Rex Moncur,

VK7MO and Roger Rehr, W3SZ, for helpfulcomments on an earlier version of this paper.
A — Appendix: Signal to Noise
Ratios
The signal to noise ratio in a
bandwidth B, that is at least as large as
the bandwidth occupied by the signal is:

SNR B =

Ps
N0 B

(12)

where Ps is the average signal power (W),
N0 is one-sided noise power spectral density(W/Hz), and B is the bandwidth in Hz. In
Amateur Radio applications, digital modes
are often compared based on the SNR
defined in a 2.5 kHz reference bandwidth,
SNR 2500 .
In the professional literature, decoder
performance is characterized in terms of
Eb / N 0 , the ratio of the energy collected
per information bit, Eb, to the one-sided
noise power spectral density, N0. Denote theduration of a channel symbol by τ s (for JT65,
τ s = 0.3715 s ). JT65 signals have constantenvelope, so the average signal power isrelated to the energy per symbol, Es, by

Ps = Es / τ s .

(13)

The total energy in a received JT65
message consisting of n = 63 channel
symbols is 63Es. The energy collected foreach of the 72 bits of information conveyed
by the message is then

63Es
(14)
= 0.875 Es . 		
72
Using equations (12) – (14), SNR 2500 can be
written in terms of Eb / N 0 :

=
Eb

Eb
(15)
N0
If all quantities are expressed in dB, then:		= 1.23 ×10−3
SNR 2500

Figure 5 — Examples of JT65B EME signals recorded at K1JT. Numbers above thespectrogram are audio frequencies in Hz, and the spectrogram’s vertical span is one minuteof time. The horizontal green bar on the frequency axis indicates the bandwidth occupied by
the second decoded signal, a reply from SP6GWB. See text for additional details.

( Eb N 0 )dB − 29.1 dB= ( Es N 0 )dB − 29.7 dB=
SNR 2500(16)

Figure 6 — Spectrogram from WSJT‑X showing one minute of data collected under crowded band conditions on the 20 m band. Numbers on
the scale are frequencies (in Hz) above 14.076 MHz.

Reprinted with permission © ARRLQEX May/June 201615

JT65 Message Processing

Algorithm 2

1. User A enters or selects message consistent with formatting
rules of JT65.
2. Transmitting software at A: compress message into 12 sixbit symbols, then add 51 six-bit parity symbols.
3. Intersperse 63 synchronizing symbols among the 63
information-carrying symbols.
4. Start transmission 1 s into a UTC minute. Transmit eachsymbol value at a distinct frequency.
5. Signal propagates from A to B, arriving much weaker andcorrupted by noise, fading, and Doppler spread.
6. Receiving software at B: remove impulsive noise; detect
synchronizing signal, measure its frequency and time offset.
7. Shift spectrum to put sync tone at zero frequency, correcting
for any measured drift.
8. Compute binned power spectra S (i, j ) for all information
symbols. (Index i runs over 64 possible symbol values, index
j over 63 symbol numbers.)
9. Remove any possible spurs (signal appearing at same i forall j).
10. Apply Algorithm 1, the FT algorithm.
11. Optional: if FT decoding was unsuccessful apply Algorithm
2, hinted decoding.
12. Display decoded message for User B.

Pseudo-code for hinted decoding

1. Generate a list of L codewords considered likely to bereceived. Set a pointer to the start of this list.
2. Fetch the next candidate codeword and calculate its metricu.
3. If u is the largest metric encountered so far, preserve any
previous value of u1 by setting u2 = u1 . Then set u1 = u andsave the codeword.
4. If the number of tested codewords is less than L , go to step2.
5. =If r u2 / u1 < R 2 , go to step 7.
6. Otherwise, declare decoding failure and exit.
7. An acceptable codeword has been found. Declare a
successful result and return the codeword and the value=
q 100 ( u1 − bu2 ) as a confidence indicator. (By default we
use the value b = 1.12 for submode JT65A.)

Glossary of Specialized Terms
Alphabet

Block code

Algorithm 1

Codeword

Pseudo-code for the FT algorithm.

1. For each received symbol, define the erasure probability as
1.3 times the a priori symbol-error probability determinedfrom soft-symbol information { p1 − rank , p2 p1} .
2. Make independent stochastic decisions about whether toerase each symbol by using the symbol’s erasure probability,
allowing a maximum of 51 erasures.
3. Attempt errors-and-erasures decoding using the BM
algorithm and the set of erasures determined in step 2. If the
BM decoder produces a candidate codeword, go to step 5.
4. If BM decoding was not successful, go to step 2.
5. Calculate the hard-decision Hamming distance X between
the candidate codeword and the received symbols, alongwith the corresponding soft distance d s and the quality
metric u .
6. If u is the largest one encountered so far, preserve any
previous value of u1 by setting u2 = u1 . Then set u1 = u ,d1 = d s , X 1 = X , and save the codeword.
7. If X 1 < X 0 and d1 < D0 , go to step 11.
8. If the number of trials is less than the timeout limit T , go tostep 2.
9. If d1 < D 1 and=r u2 u1 < R1 , go to step 11.
10. Otherwise, declare decoding failure and exit.
11. An acceptable codeword has been found. Declare a
successful decode and return the saved codeword.

Deterministic algorithm
ErasureHamming distanceHard decision
Received word
Soft decision

Soft distanceSource encoding

Stochastic algorithm
Symbol16 QEX May/June 2016

Reprinted with permission © ARRL

A sequence of possible symbol
values used for signaling. JT65 uses
a 64‑character alphabet, values in
the range 0 to 63.
An error-correcting code that treats
data in blocks of fixed size.
For the JT65 code, a vector of 63
symbol values each in the range 0
to 63.
A series of computational steps thatfor the same input always produces
the same output.
A received symbol may be “erased”
when confidence in its value isso low that it is unlikely to provide
useful information.
The Hamming distance between two
codewords, or between a received
word and a codeword, is equal to
the number of symbol positions inwhich they differ.
Received symbols are assigned
definite values by the demodulator.
A vector of symbol values, possibly
accompanied by soft information on
individual reliabilities.
Received symbols are assigned
tentative values (most probable,second most probable, etc.) andquality indicators.
The soft distance between a
received word and a codeword is ameasure of how greatly they differ,taking into account available soft
information on symbol values.
Compression of a message to use
a minimum number or bits. JT65
source-encodes all messages to 72
bits.
An algorithm involving chance orprobability in determining the seriesof computational steps to be taken.
The information carried in one
signaling interval, usually an integral
number of bits. JT65 uses 6-bit
symbols.

Steve Franke, K9AN, holds an Amateur
Extra class license. He was first licensed
in 1971 and has previously held call signs
WN9IIQ and WB9IIQ. An early and abiding
fascination with radio science led to hiscurrent position as Professor of Electricaland Computer Engineering at the University
of Illinois in Urbana-Champaign. Steve is amember of ARRL and a Fellow of the IEEE.
Joe Taylor was first licensed as KN2ITP
in 1954, and has since held call signs K2ITP,WA1LXQ, W1HFV, VK2BJX and K1JT. He
was Professor of Astronomy at the Universityof Massachusetts from 1969 to 1981 andsince then Professor of Physics at Princeton
University, serving there also as Dean of theFaculty for six years. He was awarded theNobel Prize in Physics in 1993 for discoveryof the first orbiting pulsar, leading toobservations that established the existence ofgravitational waves. After retirement he has
been busy developing and enhancing digital
protocols for weak-signal communication by
Amateur Radio, including JT65 and WSPR.
He chases DX from 160 meters through themicrowave bands.

References
J. Taylor, K1JT, “The JT65 Communications
Protocol”, QEX, Sep-Oct 2005, pp 3-12.
Available also available at physics.princeton.edu/pulsar/K1JT/JT65.pdf.
2
R. Kötter and A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes”,
IEEE Transactions on Information Theory,
Vol. 49, pp 2809-2825, 2003.
3
WSJT Home Page: www.physics.princeton.edu/pulsar/K1JT/.
4
Shu Lin and Daniel J. Costello, Error
Control Coding, 2nd Edition, PearsonPrentice Hall, 2004.
5
Camille Leroux, Saied Hemati, Shie Mannor,
Warren J. Gross, “Stochastic Chase
Decoding of Reed-Solomon Codes,” IEEE
Communications Letters, Vol. 14, No. 9, pp.
863-865, 2010.
6
Soo-Woong Lee and B. V. K. Vijaya Kumar,“Soft-Decision Decoding of Reed-Solomon
Codes Using Successive Error-andErasure Decoding,” IEEE “GLOBECOM”
Proceedings, 2008.
7
Chang-Ming Lee and Yu T. Su, “Stochastic
Erasure-Only List Decoding Algorithms
for Reed-Solomon Codes,” IEEE Signal
Processing Letters, Vol. 16, pp 691-694,
2009.
8
Source code for all programs in the WSJT
project is stored in a Subversion repository
at Sourceforge: https://sourceforge.net/
projects/wsjt/.
9Errors-and erasures decoder for theBerlekamp-Massey algorithm written by Phil
Karn, KA9Q, www.ka9q.net/code/fec/.
1

Reprinted with permission © ARRLQEX May/June 201617