タイムリーで無くなってしまったんですけど、ＰＡＲＴＥＣＨ’９３でＫＡ９Ｑが行った講演を振り返りながら、tamaのミーティングで復習をした成果です。

パケット通信における新しいリンク・レイヤ・プロトコルについて

ＫＡ９Ｑ フィル・カーン

karn@unix.ka9q.ampr.org

　AX.25 は10年以上も前の1982年に開発されたプロトコルで、HDLCとSDLCに

基づいて作られたCCITT X.25 LAPB をベースにしています。

　このため、データグラム形式な定型のヘッダーが定義されています。

　しかし衝突，ノイズ，輻輳，隠れ端末など無線特有の問題に関しては、何

も考えられていませんでした。

　AX.25 開発から１１年が経ち、コンピュータの性能も大きく向上しました

（100-1000倍のCPU, RAM, ディスク）。また、1982年に無かった、各種のRF

モデム，上位層のプロトコル（TCP/IP, ROSE, NET/ROM, TexNet ），多くの

ユーザー，そして10年の経験が、今の我々にはあります。

　また、電線でつながったネットワークを考えて設計されたプロトコルでは、

無線（特に PTT制御で行うもの）にうまく適応できないこと、実際のネット

ワークでは、有効なチャンネル・アクセスが大きな問題であること、70cm帯

のように軍用レーダーからの妨害がある中では、純粋なARQ はうまく動作し

ないこと、リンクレイヤプロトコルを実行することは、それを行わないのと

同じように重要である（例えば「コネクト」はリンク・レイヤにとっては不

必要）ことを学びました。

　また、我々は色々な伝送路（有線、HF、VHF/UHF、衛星）を利用しており、

それぞれに適したプロトコルが必要であり、それらはTCP/IPのような一定の

インターネットワークを介して、相互に接続されなくてはならないことも学

びました。

　ＦＥＣ(Forward Error Correction)はエラーが生じた時に、再送しなくて

も誤りを訂正できるよう、冗長な情報を流すものです。これはシャノンの方

程式でいう帯域を広げることにより、S/N 比を向上させることに相当します。

　　　シャノンの式　：　C = B log2(1+S/N)

　これは我々が受けているレーダーからの混信・妨害を解決する、たった１

つの実際的な方法でしょう。

　なぜ FEC を使うかのかと言うと、 FEC 方式では受信したものを全て使っ

てエラーのないパケットを作る（かもしれない）のに対し、ARQ 方式では

「悪い」パケットは捨ててしまうこと、ARQ は再送が希であれば、損失はお

おまかに言ってパケットの損失は１％以下と最小であるが、実際の多く接続

においては、これよりはるかに悪い状況であること、パケットを小さくする

ことも有効であるが、効率が悪いこと、送信機のパワーをあげたり、アンテ

ナのゲインを上げるという方法はいつも実際的，経済的とは限らないことな

どが考えられます。（これ以上は脳味噌オーバーヒート！）

　そして、逆にFEC をなぜ使わないかと言うと、必要の有無に関らず常にコ

ストがひつようなこと、またデコードする処理が面倒であるといったためで

しょう。

　FEC の実際の例として、ブロック符号ではをFMセルラー・ホンコントロー

ル・メッセージに使われているBCH-AMPS，コンパクトディスクに使われてい

るリード・ソロモン，マイクロサットのコンピュータに使われているハミン

グ符号があります。また、たたみこみ符号の使用例では、CDMA（ディジタル

・セルラー），宇宙通信（VSAT、惑星間通信など），V.32/V.32bisの電話用

モデム（トレリス・コーディング）があります。

たたみこみ符号の例

                           1                           ↓                          XOR →            Symbol#1               ↑      ↑  ↑      ↑  ↑                -----------------------------   Data in → | 0 | 1 | 2 | 3 | 4 | 5 | 6 |              -----------------------------               ↓  ↓  ↓  ↓          ↓                            XOR →            Symbol#2

k=7（拘束長），r=1/2（情報速度）

NASA 標準プラネタリー・コード

　たたみこみ符号のデコード方法による特長は、パラレル(Viterbi) 方式の

場合、デコード時間は一定であるが、2^k で複雑になるため拘束長を余り長

く取れないこと、ハード的に実現しやすいこともあり、専用ＩＣも市販され

ていること、サーマルノイズや、それに似たようなノイズによって回線品質

が劣化してる場合に適しているので、衛星通信やスペクトラム拡散通信に向

いてることです。これに対し、シーケンシャル(Fano,Stack)方式では、誤り

率によりデコード時間が変化するため、処理時間はViterbi よりも早いわけ

でも遅いわけでもないこと、かなり長い拘束長（通常k=32）にでき、長くす

ると間違ってデコードすることは無くなるが、タイムアウトが発生する可能

性があること、誤り率が低い時には、ソフト的に実現しやすいといった特長

があります。

シーケンシャルデコード

                           ----                           | 11                     ------|                     |     | 00                     | 00  ----               ------|          (etc)               |     | 11  ----               |     |     | 10               |     ------|                   | 01        | 01 1↑           |           ---      start  --| 0↓           |           ----               | 10        | 00               |     ------|               |     |     | 11               |     | 01  ----               ------|          (etc)                     | 10  ---                     |     | 01                     ------|                           | 10                           ----

　シーケンシャルデコードでは、デコーダはエンコーダと同じシンボルを持

つようになっており、実際に受信したシンボルと自分で再生したシンボルを

比較します。そして、インテリジェントな試行錯誤によって、デコーダは再

生しているシンボルと実際に受信したシンボルが最もマッチしたようなデー

タシーケンスを見つけます。

　またデコーダはシンボルの基準を作るので、それを元に受信したシンボル

の品質を評価し、Ｓメータのような目安を示します。

　そしてシーケンシャルデコードでは、ほとんどエラーがないときは、たく

さん訂正する必要がないからとても速いが、誤り率が高いときには多くの試

行錯誤を行うため、かなり遅くなるという特徴があります。

　このようなシーケンシャルデコードを行う１つとして、硬判定の Fano デ

コーダをＣで作成してみました。これは、いくつかあるr=1/2,k=32の多項式

のから１つを選択（例えば NASA 標準）したものであり、33MHz の486 マシ

ンなら入力シンボルの誤り率が２％以下の場合、平均 56kシンボル(28kバイ

ト）のデコードが可能です。これによって、現在の我々が持っている機材を

使って、シーケンシャル・デコードを実現できることが立証できます。

　FEC を使うのに必要な要素として、フレーム同期があります。このフレー

ム同期では、FEC よりもマージンをもち10％程度のエラーがあるなかで、パ

ケットの先頭を検出できる確実性が必要であり、８ビット長のHLDCフラグで

は長さが短すぎて適当でありません。そこでPN符号のような自己相互特性が

高い、疑似ランダム符号を使用する必要があります。この符号が長くなるほ

ど、ずれたフレームやノイズによって誤って検出することに対するマージン

が大きくなります。32ビットCPU のソフトウェアにインプリメントする容易

も考慮すると、この長さは64くらいが良いだろうと考えています。

　また信頼できるフレーム同期により、デコードを助けるために、誤り訂正

用の追加情報をリクエストするために送るNAK の使用が可能になります。

フレーム同期検出

　　　　　　　　　　　　　　−−−−−−−−−　　受信シンボル列　　→　　｜シフトレジスタ｜　　　　　　　　　　　　　　−−−−−−−−−　　　　　　　　　　　　　　　　　　↓　　　　　　　　　　　　　　　　−−−−−　　　　　　　　マスク　　→　　｜ EXOR ｜　　　　　　　　パターン　　　　−−−−−　　　　　　　　　　　　　　　　　　↓　　　　　　　　　　　　　　−−−−−−−−−　　　　　　　　　　　　　　｜０をカウント　｜　　　　　　　　　　　　　　−−−−−−−−−　　　　　　　　　　　　　　　　　　↓

　　　　　　　　　　　　　　カウント結果の判定

　もう一つの問題である隠れ端末については、1990年 ARRL のコンピュータ

ネットワークコンファレンスで提案された解決法の衝突回避マルチアクセス

(MACA)を使います。これは、見えない端末を防ぐために、実際のデータを送

る前にRTS/CTS(Request-to-Send/Clear-to-Send)によるハンドシェイクを行

うものです。このハンドシェイクによりオーバーヘッドが生じますが、これ

はデータパケット長くすることで軽減できます。そしてこのパケットが長く

なることはFEC を使うことにより問題ありません。

フレームレイアウトの例

  --------------------------------------------------------------  |  sync  | header | h-tail | data(coded or uncoded) | d-tail |  --------------------------------------------------------------

　　　　　　　　　　　　　　　　　　　　　　　　　　　FEC を不使用

　　　　　　　　　　　　　　　　　　　　　　　　　　　の場合はCRC

　ヘッダーの内容には、送信側のアドレス（コールサイン），受信側のアド

レス，パケットのタイプ（RTS、CTS、データ、ACK、NAK），データ長，デー

タフォーマット（データのみ、パリティのみ、その両方、そのどちらでもな

い、FEC の有無），前の受信パケットの品質情報が含まれており、これらは

常にFEC のための符号化が行われます。

　また、ARQ/FEC の長所を取り合わせて使い、必要な時だけFEC 用のシンボ

ルを送信するため、r=1/2 であるシンボルの中の特定のコードを使用します。

プロトコルシーケンスの例

　　送り側　　　　　　　　　　　　　　　　　　受け側

　　　｜　　　　　　　　　　　　　　　　　　　　｜　　　｜　　　　　　ＲＴＳ(length)　　　　　　　｜　　　｜−−−−−−−−−−−−−−−−−−−＞｜　　　｜　　　　　　　　　　　　　　　　　　　　｜　　　｜　　　　　　ＣＴＳ(length)　　　　　　　｜　　　｜＜−−−−−−−−−−−−−−−−−−−｜隠れ端末の　　　｜　　　　　　　　　　　　　　　　　　　　｜送信を停止　　　｜　　　　　　　Ｄａｔａ　　　　　　　　　｜　　　｜−−−−−−−−−−−−−−−−−−−＞｜ＣＲＣ不一致　　　｜　　　　　　　　　　　　　　　　　　　　｜　　　｜　　　　　　　ＮＡＫ　　　　　　　　　　｜　　　｜＜−−−−−−−−−−−−−−−−−−−｜訂正用データ　　　｜　　　　　　　　　　　　　　　　　　　　｜送信要求　　　｜　　　　　　Ｐａｒｉｔｙ　　　　　　　　｜　　　｜−−−−−−−−−−−−−−−−−−−＞｜誤り訂正　　　｜　　　　　　　　　　　　　　　　　　　　｜　　　｜　　　　　　ＡＣＫ(metric)　　　　　　　｜　　　｜＜−−−−−−−−−−−−−−−−−−−｜誤り数返送　　　｜　　　　　　　　　　　　　　　　　　　　｜

結び

　誤り訂正（FEC） の技術は、以前から商用，軍用，科学などの分野では使

われていました。今このFEC が、一般的なアマチュア無線家のもつ高性能に

なったパーソナルコンピュータを利用することで、我々に劇的な進歩をもた

らしてくれます。その今だからこそ、新しいアマチュアのパケット通信のプ

ロトコルに対して目を向け、我々はFECを実験すべきであると考えています。

上記レターはPartech'93にてKA9Qが行った講演のＯＨＰを訳したものです。

訳は”恵美☆”と私”ｉｎａ”が行いましたが、誤訳なども多いと思います

が、なにかの役に立てば幸いです。

訳者１： / Emi Yasuda / emily＠nsx．tama．prug．or．jp /

訳者２： / Hidekazu Inaba / ina＠jk1mly．tama．prug．or．jp /

戻る