WSJT - yoshimi.'s Diary

　JT65プロトコルは、従来の技術では利用できない伝搬経路での通信を可能にすることで、小型または妥協したアンテナや比較的低消費電力の送信機を使用するオペレータを可能にし、アマチュア無線の弱信号通信に革命をもたらしました。このプロトコルは2003年に、散乱された帰還信号が常に微弱である地球-月-地球(EME、または「ムーンバウンス」)通信のために開発されました。現在では数千人のアマチュアがJT65を定期的に使用しており、160mからマイクロ波までの全バンドでコンタクトを取っています。メッセージは短く、潜在的に困難な無線パス上の2つのアマチュアオペレータ間の最小限の交換を合理化するように構成されています。ほとんどのメッセージは、2つのコールサインとグリッドロケータ、シグナルレポート、確認応答、サインオフを含む。また、メッセージには最大 13 文字の任意のテキストを含めることもできます。すべてのメッセージは、正確に72ビットのデジタル情報に効率的に圧縮される。JT65プロトコルは、文書化された合法的な双方向の連絡を完了するための基本的な目的のために意図されていることは明らかであるが、拡張された会話のために意図されているわけではないことは明らかである。メッセージ構造と符号化手順の詳細については、以前の出版物で紹介した1 。JT65メッセージの送受信の全体的なプロセスの簡潔な説明については、添付のサイドバーJT65メッセージ処理を参照のこと。送信前に、各72ビットのメッセージは12の6ビットのシンボルに分割され、51の誤り訂正情報の追加シンボルで補強されています。これら51個のパリティシンボルは、たとえ多くのシンボルが誤って受信されたとしても、メッセージが正しく復号される確率を最大にする情報理論の規則に従って計算される。 JT65コードは、64シンボルのアルファベットに基づいた短いブロック長の低レートのリード・ソロモンコードとして適切に記述される。リードソロモン符号は、データの伝送や保存の信頼性を確保するために広く使われています。ハードウェア実装では、一般的には、受信した各シンボル値のハード判定に基づいて、ベルカンプ・マッセイ(BM)アルゴリズムのような手順で復号化が行われています。しかし、ソフト決定はより強力である可能性がある。受信した各JT65シンボルについて、最も正しい可能性の高い値だけでなく、２番目、３番目などの最も可能性の高い値を推定することができる。最も重要なことは、これらの可能性のある値がそれぞれ正しい値である確率を推定することもできるということである。これまで、JT65を実装するほぼすべてのプログラムは、特許を取得したKötter-Vardy(KV)代数的なソフトデコーダを使用してきました。 2001年以降、KVデコーダはリードソロモン符号のための最もよく知られたソフトデシジョンデコーダと考えられてきましたが、ここではFranke-Taylor (FT、またはK9AN-K1JT)と呼ばれる新しいオープンソースの代替ソフトデシジョンアルゴリズムについて説明します。これは概念的に単純で、BMハードデコーダの上に構築されており、このアプリケーションではKVデコーダよりも優れた性能を発揮します。 FTアルゴリズムは、JT65をはじめとする特殊なデジタルプロトコルを用いたアマチュア弱信号通信で広く利用されているWSJT, MAP65, WSJT-Xに実装されています。これらのプログラムはオープンソースで自由に利用可能であり、GNU General Public Licenseの下でライセンスされています。

JT65 プロトコルでは、UTC 1 分の 1 秒後に開始し、46.8 秒間続く送信を規定しています。したがって、受信側のソフトウェアは、オペレータが応答を送信する次の分が始まる前にメッセージをデコードするために10秒以上の時間を持つことになります。今日のパーソナル・コンピュータでは、この比較的長い時間は、高い計算複雑度のデコーダを使った実験を奨励しています。時間に余裕があれば、FTアルゴリズムは、典型的なフェージング・チャンネルのデコード閾値を、ハードディシジョンBMデコーダよりも数デシベル、KVデコーダよりも有意義な量だけ下げることができます。その優れた性能に加えて、新しいアルゴリズムには他の望ましい特性があり、特に概念的に単純であることが挙げられる。デコーディング性能と計算複雑度は便利な方法でスケーリングされ、調整可能なパラメータが5桁以上に増加するにつれて着実に増加するソフトデコーディング利得を提供します。非常に単純な（そして比較的遅い）コンピュータであっても、我々のデコーダから価値ある利得を得ることができる。一方、このアルゴリズムは多数の独立した復号試行から利益を得ることができるため、高性能コンピュータ上での並列化により、さらなる性能向上を達成できるはずである。第2節では、リードソロモン符号の性質とその誤り訂正能力の概要を紹介する。第3節ではFTアルゴリズムの統計的動機を示し、第4節ではアルゴリズムの詳細を述べる。これら2つのセクションの資料は、我々のアプローチを文書化し、その基本的な技術的貢献を強調するために重要である。これらのセクションは、QEXで一般的なものよりも形式的な数学が重くなっています。1 ヒント付き復号化の手順(受信したメッセージのリストの中で、もしあればどれが受信したメッセージと一致するかを決定する)については、第5節で概説しています。最後に、セクション6では、FTとヒンテッドデコーディングアルゴリズムの性能測定を行い、WSJT, MAP65, WSJT-Xの古いバージョンのユーザに馴染みのあるBMとKVデコーダとの明確な比較を行う。セクション7では、新しいデコーダを使用したオンザエアでの経験をまとめています。サイドバーの専門用語集を参照してください。

2 - JT65メッセージとリードソロモンコーデ
JT65メッセージフレームは、リード・ソロモン符号で伝送するために符号化された72ビットの短い圧縮されたメッセージから構成される。リード・ソロモン符号は、n,符号長、k,コードワードによって伝達されるメッセージシンボルの数、送信アルファベット、またはコードワード内の各シンボルの可能な値の数によって特徴づけられるブロック符号である。コードワードの長さとメッセージシンボルの数は、(n, k)という表記法で指定される。ＪＴ６５は、各シンボルに対して６４の値が可能なアルファベットを持つ（６３，１２）リード・ソロモン符号を使用する。 12個のメッセージシンボルのそれぞれは、log264 = 6個のメッセージビットを表す。従って、63シンボルのJT65フレームで伝達されるソースコード化されたメッセージは、72ビットの情報ビットで構成される。符号化理論では、ハミング距離という概念を、異なる符号語間の不一致、あるいは受信した語と符号語との間の不一致の尺度として用いている。ハミング距離は、比較されている2つの単語で異なるコードシンボルの数です。リード-ソロモン符号は、最小ハミング距離dが保証されており、ここでは1.
d=n-k+1 (1)
n = 63、k = 12の場合、JT65コードの最小ハミング距離はd = 52である。各メッセージに含まれる72の情報ビットで、JT65は2^72≒4.7✕10^21の可能なメッセージのいずれかを送信することができます。いくつかのエラー(不正確なシンボル)を含む受信ワードは、t個以上のシンボルが不正確に受信されなかったことを条件に、決定論的な代数的アルゴリズムを用いて正しいコードワードにデコードすることができます。
t= (n-k)/2(2)
JT65コードでは、t=25であるから、25個以下のシンボルエラーを持つ受信ワードを常に復号することが可能である。この難決定復号化は、BMアルゴリズムのようなよく知られた代数的アルゴリズムのうちのどれでも行うことができる。この処理には、必然的に２つのステップが必要である。(1)どのシンボルが正しく受信されなかったかを判断し、(2)正しく受信されなかったシンボルの正しい値を見つけなければならない。もし、あるシンボルが間違っていることが分かれば、その情報を利用して(1)の作業を減らし、(2)の作業でt個以上の誤りを修正することができるようになる。万が一、すべてのエラーの位置が既知であり、正しいシンボルが誤ってエラーとしてラベル付けされていない場合、BMアルゴリズムは最大でd-1=n-kのエラーを修正することができる。
FT アルゴリズムは、不正確であると疑われるシンボルのリストを作成し、BM デコーダに送信する。このようにしてフラグが立てられたシンボルは消去情報と呼ばれます。完全な消去情報では、n-k=51個までの不正確なシンボルをJT65コードに対して修正することができる。不完全な消去情報は、消去されたシンボルの一部が正しく、他の一部のシンボルが誤りであることを意味する。ｓ個のシンボルが消去され、残りのn -ｓ個のシンボルにｅ個の誤りが含まれている場合、ＢＭアルゴリズムは
s+2e ≦ d-1 . (3)
s = 0の場合、デコーダはerror only デコーダと言われています。 0<s≤d-1 の場合、デコーダはerrors-and-erasuresデコーダと呼ばれます。誤差消去デコーダの可能性は、FTアルゴリズムの中心にあります。その上で、個々のシンボル値の信頼性に関するソフトな情報を使用する能力を構築し、それによってソフト決定デコーダを生成しています。

FT アルゴリズムは、受信したシンボルの推定品質を使用して、エラーである可能性が高いと考えられるシンボルのリストを生成することで、25 個以上のエラーを持つ受信ワードの復号化を可能にします。このタイプのアルゴリズムは、一般に信頼性ベースまたは確率的復号法と呼ばれている。このようなアルゴリズムでは、受信したシンボルが誤りであるか、あるいは、受信したシンボルが正しいかについて、ある程度の教育された推測が必要となる。このようなアルゴリズムでは、受信したシンボルが誤りであるか、あるいは受信したシンボルが正しいかをある程度推測する必要があります。このようなアルゴリズムでソフトシンボル情報を使用することが不可欠である理由を説明するために、利用可能なソフトシンボル情報を無視して完全にランダムな推測を使用しようとした場合に何が起こるかを考えるのに役立ちます。具体的な例として、受信したJT65の単語を考えてみましょう。デコーダが、消去のためにs=40個のシンボルをランダムに選択し、23個の消去されていないシンボルを残したとすると、次の式(3)が成り立つ。式(3)によれば、BMデコーダは、23個の消去されていないシンボルに存在する誤りの数eが5以下であれば、この単語を解読することができる。したがって、４０個の消去されたシンボルの集合に捕捉された誤りの数は、少なくとも３５個でなければならない。受信したシンボルのランダムに選択されたサブセットの中から特定の数の誤りのシンボルを選択する確率は、超幾何学的確率分布によって支配される。ここで、Nを消去が選択されるシンボルの数、XをN個のシンボルの集合に含まれる不正確なシンボルの数、xを実際に消去されたシンボルの誤りの数と定義する。多数の受信語のアンサンブルでは、Xとxはランダムな変数となるが、この例ではxが既知であり、xのみがランダムであると仮定する。N, X, s の値を指定したxの条件付き確率質量関数は、次のように書くことができる
P(x=ε|N,X,s)=()/() (4)
ここで (n k) = n!/k! 二項係数は，数値計算言語GNU Octaveの関数nchoosek(n,k)を用いて，あるいは多くの自由なオンライン計算機のうちの1つを用いて計算することができます． (4)で定義された超幾何学的確率質量関数は，GNU Octaveで関数hygepdf(x,N,X,s)として利用可能である．X個のエラーを含むN個のシンボルのグループから選択されたs個の消去されたシンボルのサブセットに少なくともエラーが取り込まれる累積確率は
P(x≧ε|N,X,s)=ΣP(x=j|N,X,s)　(5)

受信した単語に x = 40 個の不正確なシンボルが含まれているとする。誤消去復号器を用いて復号しようとすると、N = n = 63 個のシンボルの完全集合から s = 40 個のシンボルが無作為に選択されて消去される。消去されたシンボルのうち x = 35 個が実際に不正確である確率は
P(x=35)=()/()≒2.4✕10^(-7)
同様に、消去されたシンボルのうち x = 36 が不正解である確率は、P(x=36)≒8.6×10＾(-9)である。 36個の誤りを消去する確率は、35個の誤りを消去する確率よりもはるかに小さいので、受信した単語を解読できる消去ベクトルをランダムに選択する確率は、約P(x=35)2.4×10＾(-7)であると安全に結論づけることができる。最初の試行で有効なコードワードが生成される確率は、約 400 万分の 1 と非常に低いです。
例 2.
暗号解読に成功する確率を最大化するために，消去する記号の数をどのように選ぶのがよいでしょうか？ s = 51までのすべての可能な値を徹底的に探索した結果、X = 40の場合、s = 45のシンボルを消去するのが最良の戦略であることがわかった。(3)式によれば、s = 45, d = 52の場合、eは3以下である。消去されたシンボルの集合に少なくとも40-3=37の誤差が含まれていれば復号化は確実である。Ｎ＝６３、Ｘ＝４０、ｓ＝４５の場合、１回の試行でデコードに成功する確率はＰ（ｘ≧３７）≒1.9×１０＾（-６）である。この確率は、40個のシンボルのみを消去した場合の成功確率の約8倍である。それでも、1回目の試行で解読に成功する確率は50万分の1程度である。
例3.
例1と2では、消去するシンボルを選択するランダムな戦略は、答えが出るまで長い時間待つ覚悟がない限り、成功する可能性は低いことが示されている。そこで，オッズが有利になるように戦略を変更してみましょう．先ほどと同じように、受信した単語にX = 40個の不正確なシンボルが含まれているとしますが、受信した10個のシンボルが他の53個のシンボルよりもかなり信頼性が高いことがわかっているとします。そのため、最も信頼性の高い10個のシンボルを保護し、信頼性の低いN = 53個のシンボルの中から消去を選択することができるかもしれない。このようにして消去のために s = 45 のシンボルがランダムに選ばれた場合、消去されたシンボルには例２のように少なくとも 37 個のエラーが含まれている必要がある。 N = 53、X = 40、s = 45 の場合、(5)式は(37)式となります。 (5) は P(x≧37)≒0.016 をもたらします。 s = 47を選択すると、さらに良い確率が得られますが、これはx≥38を必要とします。N = 53、X = 40、s = 47の場合、P(x≧38)≒0.027となります。最初の試行でコードワードが生成される確率は，38分の1になりました．独立してランダム化された数百回の試行で，BMデコーダが有効なコードワードを生成することができる。

4 - フランク・テイラー復号アルゴリズム
例３は、シンボルの品質に関する統計情報により、多数のエラーを有する受信フレームを復号化することが可能になるはずであることを示している。実際には、受信したワードのエラー数は不明なので、我々のアルゴリズムでは、低品質のシンボルには高い消去確率を、高品質のシンボルには比較的低い確率を単純に割り当てています。例 3 で示されているように、消去確率を適切に選択することで、コードワードが生成される可能性を何桁も高めることができます。受信した 63 個のシンボルのそれぞれに消去確率が割り当てられると、FT アルゴリズムは乱数発生器を使用して、割り当てられた消去確率に従って、各シンボルを消去するかどうかを決定する。消去されたシンボルのリストは、次に BM デコーダに送信され、デコードに失敗したことを示すコードワードまたはフラグが生成される。次のサイクルでは、消去されたシンボルの新しい選択が行われる。この段階では、エラーと消去のデコードによって得られたコードワードは、ただの候補として扱わなければならない。 FTアルゴリズムは、非コヒーレント64-FSK復調器（サイドバーJT65メッセージ処理参照）によって利用可能な品質指標を使用しています。復調器は、各シグナリング間隔のためにビニングされたパワースペクトルを計算し、その結果は二次元配列S(i,j)となります。各シンボルについて最も可能性の高い値は、i のすべての値の中で最大の信号プラスノイズパワーを持つ周波数ビンとして取られます。 FTデコーダは、p1とp2から2つのメトリック、すなわちp1-rank（ソートされたp1値のリストにおけるシンボルの分数電力p1,jのランク{1,2, ....,63}）と比p2/p1を導出する。ランクの高いシンボルは、ランクの低いシンボルよりも信号対雑音比が大きい。p2/p1が1に近い場合、最も可能性の高いシンボルの値は、2番目に可能性の高いシンボルの値よりもわずかに信頼性が高いだけです。この確率は、正常に復号化された受信単語の大規模なデータセットから経験的に導き出されたものです。この表は、p1-rankとp2/p1というメトリクスに基づいたシンボルエラーの先験的確率の推定値を提供します。このテーブルは、どのシンボルが消去から効果的に保護されているかを決定するため、アルゴリズムの重要な要素です。先験的なシンボルエラー確率は、低品質のシンボルでは 1 に近く、高品質のシンボルでは 0 に近くなります。例２および３から、消去されたシンボルの数が不正確なシンボルの数よりも多い場合に、より高い確率でコードワード候補が生成されることを思い出してください。これに対応して、FTアルゴリズムは、シンボルを消去する確率がシンボルが不正確である確率よりもやや大きい場合に最もよく機能する。 JT65においては、シンボル消去確率がシンボル誤り確率の約1.3倍のときに良好な復号性能が得られることを経験的に明らかにした。
FTアルゴリズムは、消去するシンボルを選択するために、独立した教育を受けた推測を用いて、受信した単語を連続的にデコードしようとする。各イテレーションでは、シンボル消去確率に基づいて確率的な消去ベクトルが生成されます。消去ベクトルは、63 個のハードデシジョンシンボル値のフルセットとともに BM デコーダに送られる。 BM 復号器がコードワード候補を見つけると、品質メトリック ds、つまり受信したワードとコードワードの間のソフト距離が割り当てられます。
ds = ∑αj(1+p1,j). (6)

ここで、受信シンボルｊがコードワードの対応するシンボルと同じであればαj=0、受信シンボルとコードワードのシンボルが異なる場合はαj=1、p1,jは受信シンボルｊに関連付けられた分数乗である。ソフト距離は2つの用語で構成されていると考えてください：1つ目は受信した単語とコードワードの間のハミング距離であり、2つ目は2つの候補コードワードが受信した単語から同じハミング距離を持っている場合、より小さいソフト距離が、より低い推定信頼性のシンボルで違いが発生する方に割り当てられることを保証します。また、p1とp2に含まれる情報以上のソフトシンボル情報を用いることで、かなり弱い信号も解読できることがわかりました。このため，我々は追加のメトリックuを定義した．これは，候補コードワードのシンボル値に応じた全受信シンボルの平均信号プラスノイズパワーである．
u = 1/n∑S(cj, j) 　(7)
正しいJT65コードワードは、信号パワーとノイズパワーの両方を含むn=63ビンの平均値に等しいuの値を生成する。正しくないコードワードは、最大でもk - 1 = 11個のビンと、少なくともn - k + 1 = 52個のビンを持ち、ノイズのみを含んでいる。したがって，スペクトル配列 S(i, j) がノイズのみのビンの平均値が 1 になるように正規化されている場合，正しいコードワードの u は，次式で与えられる期待値（多くのランダムな実現の平均値）を持っています．
uc = 1 + y (8)
ここで y は線形電力単位での信号対雑音比である。ガウス統計量と多数の試行を仮定すると，u の測定値の標準偏差は
σc = ((1+2y)/n)^0． (9)
対照的に、不正確なコードワード（すべての「最悪の場合」コードワードの母集団からランダムに選択されたもの、すなわち、正しい単語の対応するシンボルと同一のk - 1シンボルを持つもの）のu-メトリックの期待値と標準偏差は、次のように与えられます。
ui = 1 + ((k-1)/n)y 　(10)
σi = 1/n[n + 2y(k - 1)]^1/2。 (11)
ここで、添え字iは "不正解 "の略語である。
uが多数の異なる候補コードワードに対して評価され、そのうちの1つが正しい場合、最大値u1はcuとcσで記述された統計量を持つ母集団から得られると予想されます。テストされたコードワードが1つも正解でない場合、u1は(),iuσの母集団から来ている可能性が高く、平均値よりも数標準偏差が高いと考えられます。いずれの場合も、2番目に大きい値であるu2は、(ui,σi)の母集団から来ている可能性が高く、平均値よりも数個の標準偏差が高くなります。信号対雑音比 y が小さすぎて解読できない場合、または正しいコードワードが候補として提示されない場合、比 r = u2/u1 は 1 に近い値になる可能性が高いです。その一方で、正しく識別されたコードワードは、u1 が u2 よりも有意に大きく、したがって r の値が小さくなります。セクション６で説明したように、我々はシミュレーションを使用して、低い偽陽性率を確保しながら、正しいデコードの確率を最大化する経験的な受入れ閾値Ｒ１を設定する。
可能なコードワードのリストを生成するすべてのデコードアルゴリズムと同様に、停止基準が必要である。FTは、ハミング距離Xおよびソフト距離dsが指定された基準X<Xoおよびds<Doに従う場合、無条件にコードワードを受け入れる。二次受け入れ基準 ds<D1 と r<R1 は、最初のテストに失敗した追加のコードワードを検証するために使用されます。タイムアウトは、妥当な試行回数Tで許容できるコードワードが見つからない場合、実行時間を制限するために使用されます。今日のパーソナル・コンピュータは、Tを10^5、あるいはそれ以上に大きく設定できるほど高速です。 FTアルゴリズムの疑似コードが付属のボックスに示されています。

4,5,6 このアルゴリズムを開発した後、我々のアプローチが別の文献で説明されている確率的な消去のみのリスト復号アルゴリズムに概念的に類似していることに気づくようになりました。　このアルゴリズムは、二値位相シフトキーイング(BPSK)を使用した対称チャネル上のより高レートのリード・ソロモン符号に適用されます。 64-FSK変調を用いた64ary入力チャネルでは、消去確率を割り当てるための独自の方法と、テストされた候補のリストから最良のコードワードを選択するための受入れ基準を定義するための方法を開発する必要がありました。

5 - ヒント付きデコード
FTアルゴリズムは完全に一般的です。同じ感度で、JT65プロトコルで送信される722124.7 10≈×異なるメッセージのうちのどれかを回復することができます。いくつかの状況では、最も受信される可能性の高いメッセージの中にあるであろう、はるかに小さいメッセージのリスト(例えば、数千以下のメッセージ)を想像するのは簡単です。そのような好ましい状況の一つは、コールサイン、シグナルレポート、おそらくメイデンヘッドのロケータ、および謝辞を含む最小限の情報を交換する短いアマチュア無線の連絡先を作るときに存在します。EME経路や地理的にカバー範囲が限られたVHFやUHF帯では、最も一般的に受信されるメッセージは、以前にデコードされたコールサインから発信されることがよくあります。以前にデコードされたコールサインと関連するロケータのリストを保存しておくことで、仮想的なメッセージとそれに対応するコードワードのリストを、わずかな計算コストで簡単に生成することができます。結果として得られたコードワード候補は、セクション4で説明した確率論的手法で生成されたものとほぼ同じ方法でテストすることができる。私たちはこのアプローチを「ヒント付きデコーディング」と呼んでいます。特定の限定された状況では、それはあらゆるデコーダの主要なタスク、すなわち、どのメッセージが送信されたかを正確に判断するための感度を高めることができます。ヒント付きデコーディングのために、我々は再び比率閾値テストを呼び出しますが、この場合は、より限定的な質問に答えるためにそれを使用します。可能性が高いと考えられるメッセージの完全なリストについて、適切なメトリックが、生成されたリストの中の1つの正しいコードワードと他のすべてのコードワードを確信を持って区別できるかどうかを知りたいと思います。最も効果的な指標は、テストされたすべてのコードワードの中で、シグナルとノイズの合計パワーの最大値と2番目に大きい値であるu1とu2を比較することであることが再びわかりました。比較の基準は、誤デコードが稀であることを保証しながら、正しいデコード数を最大化するために経験的に選択されています。テストされた候補コードワードは、272個ではなく、通常は数千個を超えないリストから選ばれるので、制限はFTアルゴリズムで使用されたものよりも緩和されます。したがって、以前の経験によって可能性が高いと示唆されたメッセージの限られたサブセットのために、ヒント付きデコードは、272の可能性のあるメッセージの完全な宇宙に必要とされるよりも低い信号レベルで得ることができる。ヒント付きデコードアルゴリズムのための擬似コードは、アルゴリズム 2 として提示されます。

6 - デコーダ性能評価
デコード性能の比較は、通常、ワード・エラー・レート対Eb/N0（片側ノイズ・パワー・スペクトル密度に対する情報ビットごとに収集されたエネルギーの比率）のプロットとして専門的な文献で紹介されています。弱信号のアマチュア無線では、受信したワードのデコードに成功する確率をSNR2500（2500 Hzの基準帯域幅での信号対雑音比）に対してプロットしたものがより効果的です。Eb/N0 と SNR2500 の関係は付録 A に記載されています。両方のタイプのプロットの例は、以下の議論に含まれており、ここでは、ＦＴアルゴリズムおよびhinted デコーディングの性能を他のアルゴリズムおよび理論的な期待値と比較するために実施されたシミュレーションについて説明する。また、我々は、受け入れパラメータX0、D0、D1、R1、およびR2のための適切なデフォルト値を確立するためにシミュレーションを使用した。
6.1 - AWGNチャネルでのシミュレーション結果
JT65コード上でのBM,KV,FT復号アルゴリズムを用いたシミュレーションの結果を、ワードエラー率対Eb/Noの観点から図1に示す。これらのテストでは、加法白色ガウスノイズ(AWGN)チャネルを仮定して、各信号対雑音比で少なくとも1000個の信号を生成し、各アルゴリズムを用いてデータを処理した。ワードエラー率が0.1未満の場合、測定値を統計的に意味のあるものにするのに十分なエラーを捕捉するために、10,000または100,000のシミュレートされた信号を処理する必要がありました。数値シミュレーションの忠実性をテストするために、図1はBMの結果と比較するために理論的な確率分布から計算された結果も示しています。シミュレーションされたBMの結果は、約0.1 dBの範囲内で理論と一致しています。この違いは、シミュレーションされたデータの受信信号の時間オフセットと周波数オフセットの推定値の小さな誤差に起因しています。予想通り、AWGNチャネルでは、FTとKVのソフト決定アルゴリズムはハード決定BMアルゴリズムよりも約2dB優れています。また、FTはKVよりもエッジがあり、高SNRでは約0.2dBから低SNRではほぼ0.5dBまで増加します。タイムアウト・パラメータ T = 10^5 の場合、FT の実行時間は KV アルゴリズムよりも長くなりますが、今日の家庭用コンピュータで完全に実用化できる程度にはまだ十分に小さいです。しかし、最小のアマチュア無線コンタクトの状況は非常に異なっています。オーダー0.1以上のデコード失敗率は完全に許容できるかもしれません。このような状況では、重要な情報は、信号対雑音比の関数として正しくコピーされた送信の割合を示すプロットで示された方が有益です。図 2 は、図 1 の FT と KV の結果をこの形式で示しており、T = 10^4、10^3、10^2、および 10 の追加 FT の結果を示しています。Ｔが約３００００より大きい場合、ＦＴデコーダの方がＫＶよりも多くのデコードを生成することが容易に分かる。図 1 に関連して既に指摘したように、T = 10^5 の FT は、低 SNR で KV よりも約 0.5 dB の利得があります。 FTアルゴリズムのパラメータTは、受信した単語をデコードする特定の試みに対して許容されるシンボル消去試行の最大数である。ほとんどのデコードが成功するのは、許容される最大試行回数のごく一部だけである。図3は、正しいコードワードを見つけるのに必要な確率的消去試行回数を、受信したワードのハードディシジョンエラーの数であるXの関数としてプロットしたものです。このテストでは、タイムアウト・パラメータ T = 10^5 で、SNR2500 = -24dB、デコードしきい値のわずかに上の値で、1000 回の模擬送信を使用しました。このようなワードはすべて、エラーのみのＢＭアルゴリズムの１回の実行によって正常にデコードされているため、Ｘ≦２５についてはポイントは示されていない。図３は、ＦＴアルゴリズムが、Ｘ＝４３個ものシンボルエラーで受信した単語をデコードすることを示している。また、平均試行回数は、受信した単語のエラーの数に応じて増加することを示している。デコード時間のばらつきもまた、受信した単語のエラーの数に応じて劇的に増加する。これらの結果は、FT アルゴリズムの実行時間の平均と分散についての洞察を提供します。

6.2 - レイリーフェージングとヒンテッド復号のシミュレーション結果
図4は、プロットされた各点について1000個のシミュレーション信号を使用して、S/N比が18～-30dBの範囲でシミュレーションした結果を示しています。各復号アルゴリズムについて3つの曲線を示しています：1つはAWGNチャネルとフェージングなしの場合、もう2つは0.2と1.0Hzのドップラースプレッドをシミュレートした場合です。これらのドップラースプレッドは、HF帯の電離圏経路や、VHF帯とそれより低いUHF帯のEMEの経路で発生したものと同等のものである。比較のために、JT65のシンボルレートは約2.7Hzであることに注意してください。レイリーフェージングはBMデコーダの成功率を著しく低下させますが、FTとディープサーチ（DS）デコーダではそのペナルティははるかに小さくなっています。 0.2Hzのドップラースプレッドをシミュレートすると、実際にはデコード閾値に近いSNRでFTデコード率がわずかに増加したが、これはおそらく低レートのJT65コードでは、信号のピークが良好なコピーに必要な情報を提供するためである。
7 - オンザエアの経験
JT65プロトコルは、非常に汎用性が高いことが証明されています。今日、JT65プロトコルは、世界中の何千人ものアマチュアによって使用されており、MFバンドとHFバンドの地上波パスと50MHzから10GHzまでのEMEパスで通信しています。 3つのサブモードが使用されており、広い範囲のドップラースプレッドと潜在的な機器の不安定性に対応しています。 3つのサブモードは全て、キーイングレート11025 / 4096 = 2.69ボーで、63個の同期シンボルと63個のデータシンボルが混在して送信されます。サブモードJT65Aは、シンボルレートに等しいトーンスペーシングを使用し、その占有帯域幅は66×2.69＝177.6Hzである。サブモード B と C は、トーン間隔と占有帯域幅が 2 倍と 4 倍になります。実際には、JT65A は 50MHz 以下、JT65B は 144～432MHz、JT65C は 1296MHz 以上で使用されるのが一般的である。図 5 は、WSJT-X プログラムのメインウィンドウとスペクトログラム表示の一部であり、サブモード JT65B を EME パスで使用して 144.118MHz の K1JT からの CQ への応答を示している。ウォーターフォール上の1494と1515Hzの点線は、DL7UAEとSP6GWBからの信号の同期トーンである。約1870 Hzまでの他の目に見える斑点（ノイズの上にかろうじてある）は、これら2つの局からのデータトーンの一部です。デコードされたテキストの2行は、推定平均信号強度がそれぞれSNR2500 = -23と-24 dBであり、FTデコーダのデコードしきい値より1、2 dBだけ上にあることを示しています。 2つの信号は、それらの占有帯域幅の90%以上にわたってオーバーラップしているが、両方ともエラーなくクリーンにデコードされていることに注意してください。別の例として、図６は、２０ｍのアマチュアバンドにおける１分間のサブモードJT65Aのアクティビティを示している。この時、バンドは信号の重複で混雑していました。注意を払えば、少なくとも19個の異なる同期音（図中の斑点状の縦線）を数えることができ、いくつかの場所で4つの信号が重なっているのを見ることができます。信号を復調して FT デコーダ用のソフトシンボルデータを生成した後、WSJT-X プログラムはこの記録されたデータセグメントから 21 個のエラーのないメッセージを抽出してデコードします。この結果は、比較的小さなタイムアウト・パラメータT=1000で達成されました。これらの結果を得るために、デコーダはスペクトル上で２回の連続したスイープを使用しています。最も強い信号（この例では１２個）は、最初のパスの後、順次デコードされ、生データから減算されます。別の9つの信号が2回目のパスでデコードされます。比較のために、ハードデシジョンBMデコーダは、この記録から12のメッセージのみをデコードします（最初のパスで9つ、2番目のパスでさらに3つ）。アルゴリズムの Berlekamp-Massey 部分のために、我々は Phil Karn, KA9Q によって書かれたルーチンを使用し、リード・ソロモン症候群が最も時間のかかるループ（ステップ 2 から 8、アルゴリズム 1）で 1 回だけ計算されるように少し修正しました。FT アルゴリズムは、WSJT, MAP65, WSJT-X プログラムの不可欠な部分となっています。 Kötter-Vardy デコーダよりも感度が向上しているのは数十分の一 dB と小さいですが、特に EME パスでは、このような小さな利点が非常に重要になることがあります。さらに重要なことは、WSJTファミリーのプログラムが完全にオープンソース化されたことです。特許を取得した KV アルゴリズムや、特別にライセンスされた実行プログラム kvasd[.exe] を使用する必要はありません。

8 - 謝辞
我々は、Charlie Suckling, G3WDG; Bill Somerville, G4WJS; Casey Smith, KD9DSW; Edson Pereira, PY2SDR; Leif Asbrink, SM5BSZ; Rex Moncur, VK7MO, Roger Rehr, W3SZに感謝する。信号対雑音比帯域幅Bにおける信号対雑音比は、少なくとも信号が占有する帯域幅と同じくらいの大きさである。
SNRB=Ps/NoB (12)
ここで Ps は平均信号電力 (W)、No は片側雑音電力スペクトル密度 (W/Hz)、B は Hz での帯域幅です。アマチュア無線アプリケーションでは、デジタルモードは、2.5 kHz の基準帯域幅、SNR2500 で定義された SNR に基づいて比較されることが多い。
専門的な文献では、デコーダの性能は、片側ノイズパワースペクトル密度N0に対する情報ビットあたりに収集されるエネルギーEbの比であるEb/Noで特徴づけられています。チャンネルシンボルの継続時間をsτで表す（JT65の場合は0.3715 s=sτ）。 JT65の信号は一定のエンベロープを持っているので、平均信号パワーは、次のようにして、シンボルあたりのエネルギーEsに関係している。
Ps＝Es/τsである。 (13)
n=63個のチャネルシンボルからなるJT65メッセージの総エネルギーは63Eである。メッセージによって伝達される７２ビットの情報のそれぞれについて収集されたエネルギーは、次に
Eb=63Es/72=0.875Esである。 (14)
式（１２）〜（１４）を用いて、ＳＮＲ２５００はＥｂ／Ｎｏ．
SNR2500 = (1.23 × 10^-3)Eb/No (15)
すべての量をdBで表すと
SNR2500=(Eb/No)dB -29.1dB
=(Es/No)dB -29.7dB (16)

JT65 メッセージ処理
1. ユーザAは、JT65の書式規則に沿ったメッセージを入力または選択する。
2. Aの送信ソフトウェア：メッセージを12の6ビットシンボルに圧縮し、51の6ビットパリティシンボルを追加する。
3. 3. 情報伝達シンボル63個の中に同期シンボル63個を散りばめておく。
4. 4. 送信をUTC分に1秒後に開始する。各シンボル値は異なる周波数で送信する。
5. 信号はAからBへと伝搬し、ノイズ、フェージング、ドップラーの広がりにより、はるかに弱く、破損した状態で到着します。
6. 6. Bでの受信ソフトウェア：インパルスノイズを除去し、同期信号を検出し、その周波数と時間オフセットを測定します。
7. 7. スペクトルをシフトして同期音をゼロ周波数にし、測定されたドリフトを補正する。
8. 8. すべての情報シンボルについてビニングされたパワースペクトルS(i, j)を計算する。(インデックスiは64の可能なシンボル値、インデックスjは63のシンボル番号に対応しています)
9. 9.任意の可能なスパー（すべてのjのために同じiに現れる信号）を削除します。
10.アルゴリズム1、FTアルゴリズムを適用する。
11.Optional: FT デコーディングが失敗した場合は、アルゴリズム 2、ヒント付きデコーディングを適用してください。
12.ユーザー B のために復号化されたメッセージを表示します。
アルゴリズム 1
FTアルゴリズムの擬似コード。
1.受信した各シンボルについて、ソフトシンボル情報{p1rank, p2/p1}から決定される先験的なシンボルエラー確率の1.3倍の消去確率を定義する。
2. 2.シンボルの消去確率を用いて、各シンボルを消去するかどうかを独立した確率的決定を行い、最大51回の消去を可能にする。
3. 3. BM アルゴリズムとステップ 2 で決定された消去のセットを使用して、エラーと消去のデコードを試みる。BM デコーダがコードワード候補を生成した場合、ステップ 5 に進む。
4. 4. BM デコーディングが成功しなかった場合、ステップ 2 に進む。
5. 5. コードワード候補と受信したシンボルとの間のハード決定ハミング距離Ｘを、対応するソフト距離ｄｓと品質メトリックｕとともに計算する。
6. 6. u がこれまでに遭遇した中で最大のものであれば，u2=u1 とすることで，u1 の以前の値を保存する．その後、u1=u、d1=ds、X1=Xとし、コードコードを保存する。
7. 7. X1<XXo、d1<Doの場合、ステップ11に進みます。
8. 8. 試行回数がタイムアウト制限T以下の場合は、ステップ2に進みます。
9. 9. d1<D1で、r=u2/u1<R1の場合、ステップ11に進む。
10. それ以外の場合は、デコード失敗を宣言して終了する。
11. 許容可能なコードワードが見つかりました。デコード成功を宣言し、保存されたコードワードを返します。
アルゴリズム 2
ヒント付き復号のための擬似コード
1. 受信される可能性が高いと考えられる L 個のコードワードのリストを生成します。このリストの先頭へのポインタを設定する。
2. 2. 次の候補のコードワードを取得し、そのメトリック u を計算する。
3. 3. uがこれまでに遭遇した中で最大のメトリックである場合、u1=u2とすることでu1の前の値を保存します。次に u1=u を設定して、コードワードを保存します。
4. 4. テストされたコードワードの数がLよりも少ない場合は、ステップ2に進みます。
5. 5. r=u2/u1< R2の場合、ステップ7に進む。
6. 6. それ以外の場合は、デコード失敗を宣言して終了する。
7. 7. 許容可能なコードワードが見つかりました。成功を宣言し、コードワードと値q=100(u1-bu2)を信頼度の指標として返す。(デフォルトでは、サブモードJT65Aでは値1.12=bを使用しています。)
専門用語集
アルファベット
シグナリングに使用される可能性のあるシンボル値のシーケンス。JT65では64文字のアルファベットを使用し、値は0から63の範囲である。
ブロックコード
固定サイズのブロックでデータを扱う誤り訂正符号。
コードワード a
JT65 コードでは、0 から 63 までの範囲の 63 個のシンボル値のベクトル。
決定論的アルゴリズム同じ入力に対して常に同じ出力を生成する一連の計算手順。
消去受信したシンボルは、その値に対する信頼度が非常に低く、有用な情報を提供する可能性が低い場合、「消去」されることがあります。
ハミング距離 2 つのコードウォード間、または受信した単語とコードウォード間のハミング距離は、それらが異なる記号位置の数に等しくなります。
ハードディシジョン受信シンボルは復調器によって確定値が割り当てられます。
シンボル値のベクトルで，個々の信頼性に関するソフトな情報を伴う場合もある。
ソフト決定受信したシンボルには、暫定的な値（最確度、2 番目に最確度など）と品質指標が割り当てられる。
ソフト距離受信した単語とコードワードの間のソフト距離は、シンボル値に関する利用可能なソフト情報を考慮に入れて、それらがどれだけ大きく異なるかを示す尺度である。
ソースエンコーディング最小の数またはビットを使用するようにメッセージを圧縮すること。JT65では、すべてのメッセージを72ビットにソースエンコードする。
確率的アルゴリズム(stochastic algorithm) 一連の計算ステップを決定する際に、偶然性や確率を含むアルゴリズム。
シンボル 1 つのシグナリング間隔で運ばれる情報で、通常は整数のビット数。JT65では6ビットのシンボルを使用する。

フェージングチャネルの概要 ... レイリーおよびライス フェージングチャネルは、無線通信における実際の現象の有効なモデルです。これらの現象には、マルチパス散乱効果、時間分散、送信側と受信側の間の相対的な運動が原因で起こるドップラーシフトが含まれます。

超幾何分布（ちょうきかぶんぷ、英: hypergeometric distribution）とは、成功状態をもつ母集団から非復元抽出したときに成功状態がいくつあるかという確率を与える離散確率分布の一種である。男女・合否などのように2種の排他的属性に分割できる有限母集団からの非復元抽出に適用される。

The JT65 protocol specifies transmissions that start one second into a UTC minute and last for 46.8 seconds. Receiving software therefore has more than ten seconds to decode a 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 with decoders 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 hard-decision BM decoder, and by a meaningful amount over the KV decoder. In addition to its excellent performance, the new algorithm has other desirable properties, not least of which 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 more than five orders of magnitude. Appreciable gain is available from our decoder even on very 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 the algorithm in full detail. 2 — JT65 Messages and Reed Solomon Codes
The JT65 message frame consists of a short, compressed 72-bit message encoded for transmission with a Reed-Solomon code. Reed-Solomon codes are block codes characterized by n, the length of their codewords; k, the number of message symbols conveyed by the codeword; and the transmission 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-Solomon code 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 consists of 72 information bits. The JT65 code is systematic, 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 that differ in two words being compared. Reed-Solomon codes have guaranteed minimum Hamming distance d, where1.
d=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 each message, JT65 can transmit any one of 2^72 ≈4.7✕10^21 possible messages. The codeword for any message differs from every 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 more than t symbols were received incorrectly, where
t= (n-k)/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 of several well-known algebraic algorithms, such as the BM algorithm, can carry out this hard-decision decoding. Two steps are necessarily involved in this process. We must (1)determine which symbols were received incorrectly, and (2) find the correct value of the incorrect symbols. If we somehow know that certain symbols are incorrect, that information can be used to reduce the work involved in step (1) and allow step (2) to correct more than t errors. In the unlikely event that the location of every error is known, and if no correct symbols are accidentally labeled as errors, the BM algorithm can correct up to d-1=n-k errors.
The FT algorithm creates lists of symbols suspected of being incorrect and sends them to the BM decoder. Symbols flagged in this way 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 that some erased symbols may be correct, and some other symbols in error. If s symbols are erased and the remaining −ns symbols contain e errors, the BM algorithm can find the correct codeword as long as
s+2e ≦ d-1 . (3)
If s = 0, the decoder is said to be an errors-only 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.Material in these two sections is important because it documents our approach and underlines its fundamental technical contributions. These sections are heavier 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 one that was received — is outlined in Section 5. Finally, in Section 6 we present performance measurements of the FT and hinted decoding algorithms and make explicit comparisons to the BM and KV decoders familiar to users of older versions of WSJT, MAP65 and WSJT-X. Section 7 summarizes some on-the-air experiences with the new decoder. Refer to the sidebar Glossary of Specialized Termsfor brief definitions of some potentially unfamiliar language.

The FT algorithm uses the estimated quality of received symbols to generate lists of symbols considered likely to be in error, thus enabling decoding of received words with more than 25 errors. Algorithms of this type are generally called reliability-based or probabilistic decoding methods. Such algorithms involve some amount of educated guessing about which received symbols are in error or, alternatively, about which received symbols are correct. The guesses are informed by quality metrics associated with the received symbols. To illustrate why it is absolutely essential to use such soft-symbol information in these algorithms it helps to consider what would happen if we tried to use 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 are in 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 this word 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 some particular number of incorrect symbols in a randomly selected subset of received symbols is governed by the hypergeometric probability distribution. Let us define N as the number of symbols from which erasures will be selected, X as the number of incorrect symbols in the set of N symbols, and x as the number of errors in the symbols actually erased. In an ensemble of many received words X and x will be random variables, but for this example we will assume that X is known and that only x is random. The conditional probability mass function for x with stated values of N, X, and s may be written as
P(x=ε|N,X,s)=()()/()　(4)
where (n k) = n!/k!(n-k)! is the binomial coefficient. The binomial coefficient can be calculated using the function nchoosek(n,k) in the numerical computing language GNU Octave, or with one of many free online calculators. The hypergeometric probability mass function defined in Eq. (4) is available in GNU Octave as function hygepdf(x,N,X,s). The cumulative probability that at least eerrors are captured in a subset of s erased symbols selected from a group of N symbols containing X errors is
P(x≧ε|N,X,s)=ΣP(x=j|N,X,s)　(5)

Suppose a received word contains X = 40 incorrect symbols. In an attempt to decode using an errors-and-erasures decoder, s = 40 symbols are randomly selected for erasure from the full set of N = n = 63 symbols. The probability that x = 35 of the erased symbols are actually incorrect is then
P(x=35)= ()()/()≒2.4✕10^(-7)
Similarly, the probability that x = 36 of the erased symbols are incorrect is P(x=36)≒8.6×10＾(-9). Since the probability of erasing 36 errors is so much smaller than that for erasing 35 errors, we may safely conclude that the probability of randomly choosing an erasure vector that can decode the received word is approximately P(x=35)2.4×10＾(-7). The odds of producing a valid codeword on the first try are very poor, about 1 in 4 million.
Example 2:
How might we best choose the number of symbols to erase, in order to maximize the probability of successful decoding? By exhaustive search over all possible values up to s = 51, it turns out that for X = 40 the best strategy is to erase s = 45 symbols. According to Eq. (3), with s = 45 and d = 52 then e must be 3 or less. Decoding will be assured if the set of erased symbols contains at least 40-3 =37 errors. With N = 63, X = 40, and s = 45, the probability of successful decode in a single try is P(x≧37)≒1.9×10＾(-6). This probability is about 8 times higher than the probability of success when only 40 symbols were erased. Nevertheless, the odds of successfully decoding on the first try are still only about 1 in 500,000.
Example 3:
Examples 1 and 2 show that a random strategy for selecting symbols to erase is unlikely to be successful unless we are prepared to wait a long time for an answer. So let’s modify the strategy to tip the odds in our favor. Let the received word contain X = 40 incorrect symbols, as before, but suppose we know that 10 received symbols are significantly more reliable than the other 53. We might therefore protect the 10 most reliable symbols and select erasures from the smaller set of N = 53 less reliable ones. If s = 45 symbols are chosen randomly for erasure in this way, it is still necessary for the erased symbols to include at least 37 errors, as in Example 2. However, the probabilities are now much more favorable: with N = 53, X = 40, and s = 45, Eq. (5) yields P(x≧37)0.016. Even better odds are obtained by choosing s = 47, which requires 38≥x. With N = 53, X = 40, and s = 47, P(x≧38)≒0.027. The odds for producing a codeword on the first try are now about 1 in 38. A few hundred independently randomized tries would be enough to all-but-guarantee production of a valid codeword by the BM decoder.

4 — The Franke-Taylor Decoding Algorithm
Example 3 shows how statistical information about symbol quality should make it possible to decode received frames having a large number of errors. In practice the number of errors in the received word is unknown, so our algorithm simply assigns a high erasure probability to low-quality symbols and relatively low probability to high-quality symbols. As illustrated by Example 3, a good choice of erasure probabilities can increase the chance of producing a codeword by many orders of magnitude. Once erasure probabilities have been assigned to each of the 63 received symbols, the FT algorithm uses a random number generator to decide whether or not to erase each symbol, according to its assigned erasure probability. The list of erased symbols is then submitted to the BM decoder, which produces either a codeword or a flag indicating failure to decode.The process of selecting the list of symbols to erase and calling the BM decoder comprises one cycle of the FT algorithm. The next cycle proceeds with a new selection of erased symbols. At this stage we must treat any codeword obtained by errors-and-erasures decoding as no more than a candidate. Our next task is to find a metric that can reliably select one of many proffered candidates as the codeword that was actually transmitted.The FT algorithm uses quality indices made available by a noncoherent 64-FSK demodulator (see the sidebar JT65 Message Processing). The demodulator computes binned power spectra for each signaling interval; the result is a two-dimensional array S(i,j), where the frequency index i assumes values 0 to 63 and the symbol index j has values 1 to 63. The most likely value for each symbol is taken as the frequency bin with largest signal-plus-noise power over all values of i. The fractions of total power in the two bins containing the largest and second-largest powers, denoted respectively by p1 and p2, are computed for each symbol and passed from demodulator to decoder as soft-symbol information. The FT decoder derives two metrics from p1 and p2, namely p1-rank (the rank {1,2, ...,63} of the symbol’s fractional power p1,j in a sorted list of p1 values) and the ratio p2/p1. High ranking symbols have larger signal-to-noise ratio than those with lower rank. When p2/p1 is close to 1, the most likely symbol value is only slightly more reliable than the second most likely one.We use 3-bit quantization of the metrics p1-rank and p2/p1 to index the entries in an 8 × 8 table of symbol error probabilities. The probabilities were derived empirically from a large data set of received words that were successfully decoded. The table provides an estimate of the a priori probability of symbol error based on the metrics p1-rank and p2/p1. This table is a key element of the algorithm, as it determines which symbols are effectively protected from erasure. The a priori symbol error probabilities are close to 1 for low-quality symbols and close to 0 for high-quality symbols. Recall from Examples 2 and 3 that candidate codewords are produced with higher probability when the number of erased symbols is larger than the number of incorrect symbols. Correspondingly, the FT algorithm works best when the probability of erasing a symbol is somewhat larger than the probability that the symbol is incorrect. For the JT65 code we found empirically that good decoding performance is obtained when the symbol erasure probability is about 1.3 times the symbol error probability.
The FT algorithm tries successively to decode the received word using independent educated guesses to select symbols for erasure. For each iteration a stochastic erasure vector is generated based on the symbol erasure probabilities. The erasure vector is sent to the BM decoder along with 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 the received word and the codeword:
ds = ∑αj(1+p1,j). (6)

Here αj=0 if received symbol j is the same as the corresponding symbol in the codeword, α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 made up of two terms: the first is the Hamming distance between the received word and the 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 the one where differences occur in symbols of lower estimated reliability.In practice we find that ds can reliably identify the correct codeword if the signal-to-noise ratio for individual symbols is greater than about 4 in linear power units. We also find 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 all received symbols according to a candidate codeword’s symbol values:
u = 1/n∑S(cj, j) (7)
Here the cj’s are the symbol values for the candidate codeword being tested.The correct JT65 codeword produces a value for u equal to the average of n = 63 bins containing both signal and noise power. Incorrect codewords have at most k - 1 = 11 such bins and at least n - k + 1 = 52 bins co ntaining noise only. Thus, if the spectral array S(i, j) has been normalized so that the 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 is
σc = ((1+2y)/n)^0.5. (9)
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 to corresponding ones in the correct word) are given by
ui = 1 + ((k-1)/n)y (10)
σi = 1/n[n + 2y(k - 1)]^1/2, (11)
where the subscript i is an abbreviation for “incorrect”.
If u is evaluated for a large number of distinct candidate codewords, one of which is correct, we should expect the largest value u1 to be drawn from a population with statistics described by cu and cσ. If no tested codeword is correct, u1 is likely to come from the (),iiuσ population and to be several standard deviations above the mean. In either case 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<R1, to identify codewords with high probability of being correct. As described in Section 6, we use simulations to set an empirical acceptance threshold R1 that maximizes the probability of correct decodes while ensuring a low rate of false positives.
As with all decoding algorithms that generate a list of possible codewords, a stopping criterion is necessary. FT accepts a codeword unconditionally if the Hamming distance X and soft distance ds obey specified criteria X<Xo and ds<Do. Secondary acceptance criteria ds<D1 and r<R1 are used to validate additional codewords that fail 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 enough that T can be set as large as 10^5, or even higher. 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 After developing this algorithm, we became aware that our approach is conceptually similar to a stochastic, erasures-only list decoding algorithm described in another reference. That algorithm is applied to higher-rate Reed-Solomon codes on a symmetric channel using binary phase-shift keying (BPSK). Our 64-ary input channel with 64-FSK modulation required us to develop unique methods for assigning erasure probabilities and for defining acceptance criteria to select the best codeword from the list of tested candidates.

5 — Hinted Decoding
The FT algorithm is completely general. With equal sensitivity it can recover any one of the 722124.7 10≈× 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) that would be among the most likely ones to be received. 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 from callsigns that have been decoded before. Saving a list of previously decoded callsigns and associated locators makes it easy to generate 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 the probabilistic method described in Section 4. We call this approach “hinted decoding;” it is 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. Over the full list of messages considered likely, we want to know whether a suitable metric can distinguish with confidence between the one correct codeword and all others in the generated list — or, alternatively, to determine that 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 is chosen empirically to maximize the number of correct decodes while ensuring that false decodes are rare. Because tested candidate codewords are drawn from a list typically no longer than a few thousand entries, rather than 272, the limit can be more relaxed than that used in the FT algorithm. Thus, for the 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 the hinted-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/N0, the ratio of the energy collected per information bit to the one-sided noise power spectral density. For weak-signal Amateur Radio work, performance is more usefully presented as the probability of successfully decoding a received word plotted against SNR2500, the signal-to-noise ratio in a 2500 Hz reference bandwidth. The relationship between Eb/N0 and SNR2500 is described in Appendix A. Examples of both types 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 other algorithms and with theoretical expectations. We have also used simulations to establish suitable default values for the acceptance parameters X0, D0, D1, R1, and R2.
6.1 — Simulated results on the AWGN channel
Results of simulations using the BM, KV, and FT decoding algorithms on the JT65 code are presented in terms of word error rate versus Eb/No in Figure 1. For these tests we generated at least 1000 signals at each signal-to-noise ratio, assuming the additive white Gaussian noise (AWGN) channel, and we processed the data using each algorithm. For word error rates less than 0.1 it was necessary to process 10,000 or even 100,000 simulated signals in order to capture enough errors to make the measurements statistically meaningful. As a test of the fidelity of our numerical simulations, Figure 1 also shows results calculated from theoretical probability 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 the estimates of time and frequency offset of the received signal in the simulated data. Such “sync losses” are not accounted for in the idealized theoretical results.As expected, on the AWGN channel the soft-decision algorithms FT and KV are about 2 dB better than the hard-decision BM algorithm. In addition, FT has an edge over KV that increases from about 0.2 dB at higher SNRs to nearly 0.5 dB at low SNR. With timeout parameter T = 10^5 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 in commercial applications, so plots like Figure 1 are often extended downward to error rates of 10^-6 or even less. The circumstances for minimal Amateur Radio contacts are very different, however. Decoding failure rates of order 0.1 or higher may be perfectly acceptable: they simply require repeat transmissions. In such circumstances the essential information is more usefully presented in a plot showing the percentage of transmissions copied correctly as a function of signal-to-noise ratio. Figure 2 shows the FT and KV results from Figure 1 in this format, along with additional FT results for T = 10^4, 10^3, 10^2 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, FT with T = 10^5 has approximately 0.5 dB gain over KV at low SNR. It also provides very significant 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 decoding a 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 hard-decision errors in the received word. This test run used 1000 simulated transmissions at SNR2500 = -24dB, just slightly above the decoding threshold, with timeout parameter T = 10^5. 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 shows that 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 variance of execution time for the FT algorithm, since execution time is roughly proportional to the number of required erasure trials.

6.2 — Simulated results for Rayleigh fading 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 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 the decoding threshold, presumably because with the 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 by thousands of amateurs around the world, communicating over terrestrial paths on the MF and HF bands and over terrestrial as well as EME paths from 50 MHz through 10 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 baud. Submode JT65A uses tone spacing equal to the symbol 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 from program 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 and 1515 Hz are the synchronizing tones of signals 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 SNR2500 = −23 and -24 dB, respectively, just one or two dB 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 typical of the JT65 protocol.As another example, Figure 6 shows activity in submode JT65A during a single minute on the 20 m amateur band. At this time the band was crowded with overlapping signals. With care you can count at least 19 distinct synchronizing tones (the speckled vertical lines in the Figure), and can see as many as four signals overlapping in some places. After signal processing to demodulate the signals and produce soft-symbol data for the FT decoder, program WSJT-X extracts and decodes 21 error-free messages 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 sequentially decoded 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 first pass 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-source code. For the Berlekamp-Massey part of the algorithm we use routines written by Phil Karn, KA9Q, modified slightly so that the Reed-Solomon syndromes are computed only once in our most time-consuming loop (Steps 2 through 8, Algorithm 1). The FT algorithm has become an integral part of programs WSJT, MAP65, and WSJT-X. Improvement in sensitivity over the Kötter-Vardy decoder is small, only a few tenths of a dB, but especially on the EME path such small advantages are sometimes very important. Perhaps even more 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 helpful comments on an earlier version of this paper.A — Appendix: Signal to Noise RatiosThe signal to noise ratio in a bandwidth B, that is at least as large as the bandwidth occupied by the signal is:
SNRB=Ps/NoB (12)
where Ps is the average signal power (W), No 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, SNR2500.
In the professional literature, decoder performance is characterized in terms of Eb/No, the ratio of the energy collected per information bit, Eb, to the one-sided noise power spectral density, N0. Denote the duration of a channel symbol by sτ (for JT65, 0.3715 s=sτ). JT65 signals have constant envelope, so the average signal power is related 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 for each of the 72 bits of information conveyed by the message is then
Eb=63Es/72=0.875Es. (14)
Using equations (12) – (14), SNR2500 can be written in terms of Eb/No:
SNR2500 = (1.23 × 10^-3)Eb/No (15)
If all quantities are expressed in dB, then:
SNR2500=(Eb/No)dB -29.1 dB
=(Es/No)dB -29.7 dB (16)

JT65 Message Processing
1. User A enters or selects message consistent with formatting rules of JT65.
2. Transmitting software at A: compress message into 12 six-bit 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 each symbol value at a distinct frequency.
5. Signal propagates from A to B, arriving much weaker and corrupted 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 (, )Si 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 for all 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.
Algorithm 1
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 determined from soft-symbol information {p1rank, p2/p1}.
2. Make independent stochastic decisions about whether to erase 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, along with the corresponding soft distance ds 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=ds, X1=X, and save the codeword.
7. If X1<XXo and d1<Do, go to step 11.
8. If the number of trials is less than the timeout limit T, go to step 2.
9. If d1<D1 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.
Algorithm 2
Pseudo‑code for hinted decoding
1. Generate a list of L codewords considered likely to be received. Set a pointer to the start of this list.
2. Fetch the next candidate codeword and calculate its metric u.
3. If u is the largest metric encountered so far, preserve any previous value of u1 by setting u1=u2. Then set u1=u and save the codeword.
4. If the number of tested codewords is less than L, go to step 2.
5. If r=u2/u1< R2, 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 1.12=b for submode JT65A.)
Glossary of Specialized Terms
Alphabet
A sequence of possible symbol values used for signaling. JT65 uses a 64-character alphabet, values in the range 0 to 63.
Block code
An error-correcting code that treats data in blocks of fixed size.
Codeword
For the JT65 code, a vector of 63 symbol values each in the range 0 to 63.
Deterministic algorithm A series of computational steps that for the same input always produces the same output.
Erasure A received symbol may be “erased” when confidence in its value is so low that it is unlikely to provide useful information.
Hamming distance The Hamming distance between two codewords, or between a received word and a codeword, is equal to the number of symbol positions in which they differ.
Hard decision Received symbols are assigned definite values by the demodulator.
Received word A vector of symbol values, possibly accompanied by soft information on individual reliabilities.
Soft decision Received symbols are assigned tentative values (most probable, second most probable, etc.) and quality indicators.
Soft distance The soft distance between a received word and a codeword is a measure of how greatly they differ, taking into account available soft information on symbol values.
Source encoding Compression of a message to use a minimum number or bits. JT65 source-encodes all messages to 72 bits.
Stochastic algorithm An algorithm involving chance or probability in determining the series of computational steps to be taken.
Symbol The information carried in one signaling interval, usually an integral number of bits. JT65 uses 6-bit symbols.