アルゴリズム遅延のソースを表示

'''アルゴリズム遅延'''（{{lang-en-short|Algorithmic delay}}）は[[アルゴリズム]]に内在する[[レイテンシ|待ち時間]]である<ref>"The 'Algorithmic delay' is a best-case value including only delay sources introduced by the algorithm itself" M. Lutzky, et al. (2004). ''A guideline to audio codec delay''. AES 116.</ref>。

== 概要 ==
プログラムは[[アルゴリズム]]からなり、アルゴリズムが計算機によって処理されることで実行される。計算処理には当然時間がかかるため、プログラムの開始から実行完了には[[レイテンシ|遅延（レイテンシ）]]が発生する。しかし無限の能力をもつ計算機（=処理遅延0秒）を仮定してもレイテンシが発生する、すなわちアルゴリズムそのものに由来してレイテンシが発生する場合がある<ref>"This would be equal to a hardware implementation where unlimited processing power and transmission speed is available." M. Lutzky, et al. (2004). ''A guideline to audio codec delay''. AES 116.</ref>。このアルゴリズムに内在する遅延をアルゴリズム遅延という。

例えば2つの音声加工アルゴリズム「A: 音量倍増」と「B: ノイズ除去」を考える。Aの音量倍増では時刻 <math>t</math> の入力信号を2倍にして即返せばよいので、無限の計算能力があれば即座に出力できる。Bのノイズ除去の場合、時刻 <math>t</math> の入力信号が <math>x_t = 0.5</math> のとき、この1点だけを見てもどの程度ノイズが乗っているかは判別できない。ノイズ検出にはある程度の'''時間区間'''（ブロック）を見る必要があり、そのために信号を一定時間'''貯める'''必要がある。つまりBでは処理そのものに追加してアルゴリズムのための信号蓄積が必要であり、たとえ無限の処理能力があっても信号が貯まるまでの待ち時間がかかる。ゆえにBのアルゴリズムはブロック長分の遅延を必ずもつ、すなわちアルゴリズム遅延をもつことになる。

アルゴリズム遅延はリアルタイム情報処理において重要である。例えば[[インターネット電話#ボイスチャット|ボイスチャット]]ではリアルタイムに自分の音声を圧縮、ネットワーク転送し、相手方で伸展して音を届ける。経験的に知られているように、遅いマシンやネットワークを利用すると相手の声が遅れて聞こえ、コミュニケーションを阻害してしまう。しかし超高性能のマシンとネットワークを利用したとしても、圧縮伸展アルゴリズムが大きなアルゴリズム遅延をもっていると音が遅れて聞こえてしまう。なぜならアルゴリズム遅延は処理能力に依存しない、それ以上下げることのできない遅延だからである。音声圧縮伸展アルゴリズムすなわち[[音声コーデック]]の分野ではこのような低遅延リアルタイム用途を意識してアルゴリズム遅延を最小化できるコーデックが多数発表されている（例: [[Opus (音声圧縮)|Opus]]<ref>" Opus Codec Overview ... The Opus codec scales ... with algorithmic delays ranging from 5 ms to 65.2 ms." JM. Valin, et al. (2012). ''[https://datatracker.ietf.org/doc/html/rfc6716 Definition of the Opus Audio Codec]''. IETF RFC6716.</ref>）。

アルゴリズム遅延はアルゴリズムが規定する入力形式に強く依存する。入力形式には時間に依存するストリームや時間に依存しないバッチなどがある。例えば上記アルゴリズムBはリアルタイム処理用のストリーム入力を前提としているため、ストリームからブロック長分貯めるためのアルゴリズム遅延が発生している。一方、ブロック単位のノイズ除去をオフライン用のバッチ入力に適用するとする。その場合、全ての入力が既に揃っている、すなわち全ての信号が「既に貯まっている」状態で処理を開始できる。ゆえに信号蓄積にかかる遅延が0になってアルゴリズム遅延が0になる。このような背景から、通話などのリアルタイム用途ではアルゴリズム遅延が重視され、保存用圧縮などの非リアルタイム用途では相対的に重視されない傾向がある。

アルゴリズムの実処理（実行）にかかる遅延は'''処理遅延'''と呼ばれる。処理遅延は計算機の性能や実装の質により左右される<ref>"処理遅延； 圧縮・伸張処理自体に要する時間。 具体的な実装方法次第でその時間を短くすることが可能。" 渡邊晃. (2007). ''[http://www.wata-lab.meijo-u.ac.jp/file/document_of_prof/7WIPTEL.pdf IP電話のしくみについて]''. 名城大学.</ref>。

== 要因 ==
アルゴリズム遅延は様々な要因（手法）により決定される。以下はその一例である。

=== 先読み ===
アルゴリズム遅延の要因の1つが'''先読み'''/'''前方参照'''（{{lang-en-short|Look ahead}}）である<ref>"The algorithm must have some knowledge of what is in block N+1 in order to accurately reproduce sample block N. This look ahead" CISCO (2006). ''[https://www.cisco.com/c/en/us/support/docs/voice/voice-quality/5125-delay-details.html Understanding Delay in Packet Voice Networks]''. CISCO Technology White Paper.</ref>。時刻 <math>t</math> の入力信号 <math>x_t</math> を処理する際、時刻 <math>t+N</math> の情報を利用することでより良い <math>x_t</math> の処理をできる場合がある。この先データアクセスが先読みである。先読みをおこなう場合、<math>x_t</math> を処理するために <math>x_{t+N}</math> までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、<math>N</math> サンプルの先読みは '''<math>N</math> のアルゴリズム遅延'''をもたらすことになる。アルゴリズムを設計する際には、先読みで得られる出力の質向上と遅延増大のトレードオフを理解する必要がある。

時刻 <math>t-N</math> すなわち過去の信号を後読み（{{lang-en-short|Look behind}}）することは一般にアルゴリズム遅延へは影響しない。なぜならストリーム入力であっても過去の入力は既に手元にあるからである。<math>N</math> を大きくすることはむしろ処理量の増大による処理遅延と質の兼ね合いになる。

=== ブロック処理 ===
アルゴリズム遅延の要因の1つが'''ブロック処理'''である<ref>"圧縮符号化としては, 波形の逐次処理, ブロック処理, ボコーダの3種類に大別できる．" 守谷. (1998). ''[https://www.ieice.org/jpn/books/HB/text/3gun/gaiyo3-7.htm 音声・オーディオ符号化]''. 電子情報通信学会 電子情報通信ハンドブック.</ref>。ブロック処理では時刻 <math>t</math> の入力信号 <math>x_t</math> を逐次処理するのではなく、<math>x_t</math> ~ <math>x_{t+N}</math> を1かたまりとしこの単位で一括処理する。次の処理では時刻を <math>h</math> 進めた <math>x_{t+h}</math> ~ <math>x_{t+h+N}</math> を同様に一括処理する。処理単位はブロック、''フレーム''、ウィンドウなどと、間隔 <math>h</math> はホップ長（{{lang-en-short|Hop length}}）やストライド（{{lang-en-short|Stride}}）と呼ばれる。ブロック長 <math>N</math> とホップ長 <math>h</math> は必ずしも一致しない。

<math>N=h</math> のブロック処理では、ブロック先頭 <math>x_t</math> を処理するためにブロック末端 <math>x_{t+h}</math> までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、ホップ長 <math>h</math> のブロック処理は入力 <math>x_{t+a}</math> に「最大で」 <math>h</math> のアルゴリズム遅延をもたらす。「最大」なのはサンプル位置によりアルゴリズム遅延が異なるからである。ブロック末端 <math>x_{t+h}</math> の視点でみると取り込まれた瞬間に処理されるためブロック処理のアルゴリズム遅延は0である。ブロック単位でみた遅延は最大値たる <math>h</math> になる。

<math>N > h</math> の場合、ブロック処理を出力の視点でみると、ホップ長 <math>h</math> 分の出力を一括で出力している。<math>N > h</math> で出力長以上の入力を取りこんでいるということは、ブロック内での先読み/後読みをおこなっていることになる。つまり <math>t</math> ~ <math>(t+h)</math> を出力するために <math>(t-b)</math> ~ <math>(t+h+a)</math> を入力している（<math>N := b + h + a</math>） 。アルゴリズム遅延に影響するのは先読みであるため、ブロック単位でみた'''アルゴリズム遅延は <math>h + a</math>''' になる。

またブロック処理と先読みを組み合わせ、ブロック <math>k</math> の処理にブロック <math>k + M</math> を必要とさせることもできる。その場合は <math>h</math> 単位で必要な入力が増えていくため、アルゴリズム遅延が '''<math>h + a + M*h</math>''' になる。

== 関連項目 ==

* [[レイテンシ]]
* [[アルゴリズム]]
* [[計算機科学]]

== 出典 ==
{{Reflist}}

{{Normdaten}}
{{DEFAULTSORT:あるごりずむちえん}}
[[Category:アルゴリズムとデータ構造]]
[[Category:コンピュータと時間]]