(57)【要約】  メモリのインプレース状態で、メモリ位置のセットに記憶されているインタリーブ化データのシーケンスを第１順序から第２順序へ線形時間的にデインタリーブする方法である。２つのデータ要素がシーケンスの中央から取り出されると、そこにホールが生成される。取り出されたデータ要素の宛先位置が判定される。宛先位置にデータ要素が含んでいるかが判定される。そうである場合、宛先位置のデータ要素が取り出されたデータ要素に置き換えられ、第１宛先位置から取り出されたデータ要素に対する第２宛先位置が判定される。そうでない場合、第１データ要素は、宛先位置に直接挿入される。シーケンスが適切にデインタリーブされる前に、データ要素がシーケンスのホールに挿入される場合、間違って配置されたデータ要素であると判定され、再配置される。再配置シーケンスは、データ要素が正しく配置されるまで繰り返される。
2007507933.tif 000002
【特許請求の範囲】
【請求項１】
第１順序から第２順序へデータ要素のシーケンスをソートすることを含む、データを処理するためのデインタリーブ方法であって、
前記シーケンスから、第１位置の少なくとも第１データ要素を取り出す工程と、
前記シーケンス内の前記取り出したデータ要素に対する宛先位置を判定する工程と、
前記判定された宛先位置にデータ要素が含んでいるかを判定し、そうである場合には、前記判定された宛先位置のデータ要素を前記取り出されたデータ要素に置換し、そうでない場合には、前記判定された宛先位置に前記第１データ要素を挿入する工程と
を備えることを特徴とするデインタリーブ方法。
【請求項２】
前記宛先位置は、前記第１位置のインデックスと、前記シーケンスの前記データ要素の数に基づいて算出される
ことを特徴とする請求項１に記載のデインタリーブ方法。
【請求項３】
２つのデータ要素が、前記工程の各シーケンスで再配置される
ことを特徴とする請求項１または２に記載のデインタリーブ方法。
【請求項４】
メモリ位置のセットを有するメモリ（１１０）内で実行されるインプレース方法である
ことを特徴とする請求項１乃至３のいずれか１項に記載のデインタリーブ方法。
【請求項５】
前記シーケンスは、偶数のデータ要素を有し、前記シーケンスの第１セットのデータ要素に関連するデータ要素の数は、前記シーケンスの第２セットのデータ要素に関連するデータ要素の数と等しい
ことを特徴とする請求項１乃至４のいずれか１項に記載のデインタリーブ方法。
【請求項６】
第１セットのデータ要素と第２セットのデータ要素それぞれに関連するデータ要素は、ソートされる前は前記シーケンス内で交互に配置されていて、
前記シーケンス内でソートされている前記データ要素は、連続位置で連続データ要素にグループ化されている
ことを特徴とする請求項１乃至５のいずれか１項に記載のデインタリーブ方法。
【請求項７】
同一の再配置シーケンスで再配置対象の２つの第１データ要素は、第１セットのデータ要素及び第２セットのデータ要素のそれぞれに関連する１つのデータ要素として選択され、
前記２つの第１データ要素は、前記シーケンスの最初と最後のデータ要素以外の他のデータ要素として選択される
ことを特徴とする請求項５に記載のデインタリーブ方法。
【請求項８】
前記再配置対象の２つの第１データ要素は、前記シーケンスの中央位置で記憶されているデータ要素として選択される
ことを特徴とする請求項５または７に記載のデインタリーブ方法。
【請求項９】
前記宛先位置にデータ要素が含んでいない場合、再配置対象の、間違って配置されているデータ要素が少なくとも１つあると判定する工程と、
前記間違って配置されているデータ要素の少なくとも１つを再配置する工程と
を更に備えることを特徴とする請求項１乃至８のいずれか１項に記載のデインタリーブ方法。
【請求項１０】
再配置対象の、間違って配置されているデータ要素の少なくとも１つの位置は、
データ要素を含んでいない第１宛先位置より前の位置及び
データ要素を含んでいない第２宛先位置より後の位置
の少なくとも一方として判定される
ことを特徴とする請求項９に記載のデインタリーブ方法。
【請求項１１】
前記シーケンスは、０から始まるインデックスが付加され、
間違って配置されているデータ要素の前記宛先位置は、
前記第１位置のインデックスが偶数である場合には、該第１位置のインデックスを２で除算したものであり、
前記第１位置のインデックスが奇数である場合には、該第１位置のインデックスを２で除算したものを、メモリ位置の総数を２で除算したものに加算したものである
ことを特徴とする請求項１乃至１０のいずれか１項に記載のデインタリーブ方法。
【請求項１２】
データ要素のシーケンスを記憶するためのメモリ位置のセットを有するメモリ（１１０）と、前記データ要素をソートするプロセッサ（１２０）とを備える、第１順序から第２順序へ前記データ要素のシーケンスをソートするデインタリーブ装置（１３０）であって、
第１メモリ位置の少なくとも第１データ要素を記憶するためのバッファを備え、
前記プロセッサは、前記バッファから前記データ要素を取り出し、前記取り出したデータ要素に対する宛先メモリ位置を判定し、前記判定された宛先メモリ位置にデータ要素が含んでいるかを判定し、そうである場合には、前記判定された宛先メモリ位置のデータ要素を前記取り出したデータ要素に置換し、そうでない場合には、前記判定された宛先メモリ位置に前記第１データ要素を挿入するように構成されている
ことを特徴とするデインタリーブ装置。
【請求項１３】
前記プロセッサは、前記第１位置のインデックスと、前記シーケンスの前記データ要素の数に基づいて、前記宛先メモリ位置を算出するように構成されている
ことを特徴とする請求項１２に記載のデインタリーブ装置。
【請求項１４】
前記プロセッサは、各再配置シーケンスで、２つのデータ要素を再配置するように構成されている
ことを特徴とする請求項１２または１３に記載のデインタリーブ装置。
【請求項１５】
前記プロセッサは、レジスタファイルを備え、
前記データ要素の再配置は、前記メモリ（１１０）内のインプレースで実行される
ことを特徴とする請求項１２乃至１４のいずれか１項に記載のデインタリーブ装置。
【請求項１６】
前記メモリ（１１０）は、偶数のメモリ位置を備える
ことを特徴とする請求項１２乃至１５のいずれか１項に記載のデインタリーブ装置。
【請求項１７】
前記プロセッサ（１２０）は、
同一の再配置シーケンスで再配置対象の２つの第１データ要素を、第１セットのデータ要素及び第２セットのデータ要素のそれぞれに関連する１つのデータ要素として選択し、かつ
前記２つの第１データ要素は、前記シーケンスの最初と最後のデータ要素以外の他のデータ要素として選択するように構成されている
ことを特徴とする請求項１４に記載のデインタリーブ装置。
【請求項１８】
前記プロセッサ（１２０）は、前記再配置対象の２つの第１データ要素を、前記メモリ（１１０）の中央メモリ位置で記憶されているデータ要素として選択するように構成されている
ことを特徴とする請求項１６または１７に記載のデインタリーブ装置。
【請求項１９】
前記宛先メモリ位置にデータ要素が含んでいない場合、前記シーケンスのすべてのデータ要素が、それらの正しいメモリ位置に配置されているかを判定し、
任意のデータ要素が間違ったメモリ位置に記憶されている場合、再配置対象の、間違って配置されているデータ要素の少なくとも１つを判定し、
前記間違って配置されているデータ要素の少なくとも１つを再配置する
ように構成されている
ことを特徴とする請求項１２乃至１８のいずれか１項に記載のデインタリーブ装置。
【請求項２０】
前記間違って配置されているデータ要素の少なくとも１つのメモリ位置は、
データ要素を含んでいない第１宛先メモリ位置より前のメモリ位置及び
データ要素を含んでいない第２宛先メモリ位置より後のメモリ位置
の少なくとも一方として判定される
ことを特徴とする請求項１９に記載のデインタリーブ装置。
【請求項２１】
前記メモリ位置は、０から始まるインデックスが付加され、
間違って配置されているデータ要素の前記宛先メモリ位置は、
前記第１メモリ位置のインデックスが偶数である場合には、該第１メモリ位置のインデックスを２で除算したものであり、
前記第１メモリ位置のインデックスが奇数である場合には、該第１メモリ位置のインデックスを２で除算したものを、メモリ位置の総数を２で除算したものに加算したものである
ことを特徴とする請求項１２乃至２０のいずれか１項に記載のデインタリーブ装置。
【請求項２２】
インタリーブ化データ要素のシーケンスを再現するための電子機器（１）であって、
請求項１２乃至２０のいずれか１項に従うデータ要素をソートするためのデインタリーブ装置（１３０）を備える
ことを特徴とする電子機器。
【請求項２３】
当該電子機器（１）は、移動端末、パーソナルデジタルアシスタント、ページャ、スマート電話、コミュニケータ、電子オーガナイザ、あるいはデジタルマルチメディアファイルを再生するためのマルチメディアプレーヤである
ことを特徴とする請求項２２に記載の電子機器。
【請求項２４】
当該電子機器は、移動電話（１）である
ことを特徴とする請求項２２に記載の電子機器。
【請求項２５】
デジタルコンピュータ処理機能を有する電子機器によって実行される場合に、請求項１乃至１１のいずれか１項に従う方法を実行するためのコンピュータ可読命令を記憶する、コンピュータ可読媒体（１１１）で実現されるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
本発明は、データ処理の分野に関するものであり、より詳しくは、所望の順序で、データ要素のシーケンスをソートする分野に関するものである。
【０００２】
関連技術の説明
ある電子機器あるいはユニットから別のものへの送信のためにデジタルデータをインタリーブすることで、誤りの影響を最小化して、データ復元可能性を高めることが知られている。電子機器で受信されたインタリーブ化デジタルデータは、デインタリーブ（deinterleaved）され、かつアナログ信号を、例えば、音声信号に再現してもいいように、デジタルアナログ変換される。インタリーブ化送信ストリーム内の連続データ要素の損失は、一般的には、デインタリーブ化データシーケンス内の連続誤りには対応しない。これは有効なことである。なぜなら、データストリーム内の孤立したデータ誤りを訂正することはより容易なことであるからである。
【０００３】
従来のデインタリーバ（deinterleaver）は、再現対象のデータ要素のインタリーブ化ストリームを受信して、第１メモリエリアに記憶する。デインタリービング処理は、インタリーブ化データ要素を第１メモリエリアから第２メモリエリアへ転送する。第２メモリエリアでは、これらは、それらが読取られる順序で配置される。あるいは、いくつかのデータ要素のセットにグループ化される。
【０００４】
従来のデインタリーバの問題は、２つのメモリエリアが使用されることであり、それぞれのメモリエリアは、デインタリーブされるデータ要素のシーケンス全体を記憶するのに十分な容量となっている。
【０００５】
ＷＡＶファイルあるいは非圧縮ＷＭＡファイルのようなインタリーブ化オーディオデータ要素のシーケンスは、たいていは、シーケンス内で交互に配置される左右チャネルに対して意図されるサンプルで提供される。そのシーケンスをデインタリービングする場合、左右チャネルのサンプルは連続サンプルのセットに分けられる。また、このようなバッファは、同一数の左右チャネルのサンプルを有する長さ分となっている。また、オーディオデータをデインタリービングするための処理速度の要求は、たいていはかなり厳しいものである。インタリーブ化データの処理が明確なデッドライン前に完了しないと、それによって得られる歪みがかなり容易に人間によって知覚されることになる。
【０００６】
移動無線端末、移動電話、パーソナルデジタルアシスタント、スマート電話、電子オーガナイザあるいはマルチメディアプレーヤのような、ポータブル電子機器は、バッテリ容量、処理能力、インタリーブ化データ要素を有するデジタルデータファイルを再現するために利用可能なメモリ容量に制限がある。つまり、メモリ容量と処理能力との間でのトレードオフを行わなければならない。アルゴリズムに対するメモリ消費が低下すると、実行時間は増加する。
【０００７】
余計なメモリを必要としない、周知のデインタリービングアルゴリズムは存在する。これらのアルゴリズムに従えば、データ要素が特定の方法でインタリーブされると、隣接データ要素の位置が数回スイッチされる。ここで、第１のデータ要素のセットと、第２のデータ要素のセットに関連するデータ要素はグループ化される。しかしながら、このようなデインタリービングアルゴリズムは計算が複雑（時間を消費する）であり、また、高い処理能力を必要とする。このスイッチングアルゴリズムを使用するデータ要素をデインタリーブするために必要とされる処理時間は、シーケンス内のいくつかのデータ要素の２乗に比例する時間となる。アルゴリズムの調整（scale）を良好にするためには、処理時間がデータ要素のシーケンスのデータ要素の数にほぼ線形に比例することが好ましい。
【０００８】
ＷＯ０１／８２０５４は、メモリ要求が削減されたメモリにデータ要素のシーケンスを記憶する方法を開示している。メモリのデータ要素は、第１データ要素を読み出し、かつその第１データ要素で第２データ要素を上書きすることによってデインタリーブされる。第２データ要素は、第１データ要素が適切に読み出されるまでは上書きされない。別のフラグメモリが、特定のデータ要素が適切に読み出されているかを追跡するために提供されている。つまり、追加のメモリが必要とされ、また、データ処理は、フラグメモリのフラグの設定が介在する。
【０００９】
本発明の要約
本発明の目的は、メモリのいくつかの位置に記憶されているインタリーブ化データ要素の配列あるいはシーケンスを、メモリ内でインプレースの状態でデインタリーブされる、方法及び装置を提供することであり、そうすることで、デインタリーブを実行するための余計な追加のメモリが必要でなくなる。
【００１０】
本発明の第２の目的は、データ要素のシーケンスをデインタリーブするための処理時間が、そのシーケンス内のデータ要素の数に対して実質的に線形となる、方法及び装置を提供することである。
【００１１】
本発明の第１の構成に従えば、上述の目的は、データ要素の配列あるいはシーケンスが第１順序から第２順序へソートされることに従う、デインタリーブ方法によって達成される。第１位置の少なくとも１つのデータ要素が、データ要素のシーケンスから取り出される。取り出されたデータに対する宛先位置が、シーケンス内で判定される。また、宛先位置にデータ要素を含んでいるかが判定される。そうである場合、宛先位置のデータ要素は、取り出されたデータ要素に置き換えられる。そうでない場合、第１データ要素が、判定された宛先位置に直接挿入される。
【００１２】
第１データ要素を取り出すと、シーケンスあるいは配列内にホールを生成することになり、このホールには、正しいデータが、データ要素を再配置するためのいくつかの再配置シーケンスの後に挿入されることになる。
【００１３】
本方法に従えば、宛先位置にデータ要素が含まない場合、データ要素のシーケンスのすべてのデータ要素が、自身の正しい位置に配置されているかが判定される。また、データ要素のシーケンスのデータ要素が正しく配置されていない場合、再配置対象である、間違って配置されたデータ要素の少なくとも１つが検索される。そして、その間違って配置されたデータ要素が再配置される。
【００１４】
データ要素の宛先位置は、データ要素のシーケンス内のデータ要素のソース位置のインデックスと、そのシーケンス内のデータ要素の数に基づいて計算されても良い。選択的には、データ要素には番号が付加されて、そうすることで、シーケンス内の自身の正しい位置が判定される。
【００１５】
２つのデータ要素は、各シーケンスの工程で再配置されても良い。また、本方法は、メモリ位置のセットを有するメモリ（１１０）内で実行されるインプレース方法であっても良い。その結果、余計なメモリが必要でなくなる。
【００１６】
データ要素のシーケンスは、偶数のデータ要素を有していて、また、そのシーケンスの第１セットのデータ要素に関連するデータ要素の数は、そのシーケンスの第２セットのデータ要素に関連するデータ要素の数と等しい。
【００１７】
同一再配置シーケンスにおいて、再配置対象の第１データ要素は、第１セットのデータ要素と第２セットのデータ要素それぞれに関連する１つのデータ要素として選択されても良い。また、２つの第１データ要素が、データ要素のシーケンスの最初と最後のデータ要素以外の他のデータ要素として選択されても良い。これらは、第１セットのデータ要素と第２セットのデータ要素に交互に関連するデータ要素でインタリーブされたベクトルが与えられることによって、それらの正しい位置に既になっている。また、再配置対象の２つの第１データ要素は、データ要素のシーケンスの中央位置に記憶されているデータ要素として選択されても良く、これにより、対称性を達成する。
【００１８】
本発明の第２の構成に従えば、上述の目的は、第１順序から第２順序へデータ要素の配列をソートするためのデインタリーブ装置によって達成される。このデインタリーブ装置は、データ要素のシーケンスを記憶するためのメモリ位置のセットを有するメモリと、そのデータ要素をソートするためのプロセッサとを備える。このプロセッサは、本発明の方法を実行するように構成されている。
【００１９】
このプロセッサは、データ要素が一時的に記憶されるレジスタファイルを備えていても良い。このメモリは、データ要素を記憶するための偶数のメモリ位置を有している。
【００２０】
本発明に従うデインタリーブ装置は、移動無線端末、移動電話、パーソナルデジタルアシスタント、ページャ、スマート電話、コミュニケータ、電子オーガナイザあるいはデジタルマルチメディアファイルを再生するためのマルチメディアプレーヤで構成されていても良い。
【００２１】
本発明の第３の構成に従えば、コンピュータ可読媒体上で実現されるコンピュータプログラムが本発明の目的を達成する。このコンピュータプログラムは、デジタルコンピュータ処理機能を有する電子機器によって実行される場合に本発明の方法を実行するためのコンピュータ可読命令を備えている。
【００２２】
更なる本発明の実施形態は、請求項によって定義される。
【００２３】
本発明の効果は、メモリ消費及び処理時間に対する要求が厳しい環境で使用できることである。本発明に従う方法は、追加のメモリを必要とすることなく使用することができ、また、デインタリーブ化オーディオデータを提供するために十分に高速である。本方法は、メモリ内でインプレースで実行することができる（即ち、余計なメモリは必要とされない）。また、本方法は、線形時間的に実行することができる。即ち、入力データ処理するために必要とされる時間は、入力データのサイズに直接比例する。
【００２４】
本明細書で使用される場合の用語「備える／備えている」は、説明される特徴、整数値、ステップ群あるいはコンポーネントの存在を特定するものであるが、１つ以上の他の特徴、整数値、ステップ群、コンポーネントあるいはそれらのグループの存在あるいは追加を除外するものではないことが強調されるべきである。
【００２５】
実施形態の詳細説明
図１は、端末を操作するためのマン−マシンインタフェースを有する移動端末１を示している。マン−マシンインタフェースは、マイク１０、スピーカあるいはイヤホーン１１、キーパッド１２及びディスプレイ１３を備えていても良い。また、移動端末１は、ネットワーク及び別の電子機器と接続するための接続手段を備えていても良い。この電子機器には、例えば、コンピュータ、パーソナルデジタルアシスタント、コミュニケータ、ＭＰ３プレーヤのような外部マルチメディアプレーヤ、あるいはスマート電話がある。通信手段は、無線通信リンクを介して、例えば、ＧＳＭ／ＧＰＲＳ、ＵＭＴＳ（例えば、ＷＣＤＭＡ及びＥＤＧＥ技術を使用する）あるいはｃｄｍａ２０００規格に従う電気通信ネットワークのような通信ネットワークと通信するための第１アンテナ１４を備えても良い。移動端末は、例えば、ブルートゥース（登録商標）規格に従う無線ローカルエリアネットワークと通信する短距離用補助アンテナ１５、あるいは、別の電子機器との赤外線（ＩＲ）接続を確立するための手段１６を備えていても良い。移動端末１は、ＭＰ３プレーヤのような外部装置と直接あるいはシリアルケーブルを介して接続され得るアクセサリコネクタ１７を備えていても良い。この通信手段は、通信インタフェースを使用する様々な通信用回路、例えば、変調器、復調器、増幅器、送信機、受信機等を備えていてもよい。
【００２６】
以下では、移動端末あるいは移動電話１について言及する。しかしながら、本発明は、移動端末１に限定されるものではなく、メモリあるいはバッファのデータ要素をソートすることが必要な電子機器にも応用することができる。このような電子機器には、移動電話端末、移動電話、ページャ、コミュニケータ、電子オーガナイザ、スマート電話、コンピュータあるいは、ＭＰ３プレーヤのような、デジタルマルチメディアファイルを再生するマルチメディアプレーヤがあるが、これらに限定されるものではない。
【００２７】
本発明に従う移動端末１はマルチメディアファイルを再生するように構成されている。これには、好ましくは、ＭＰ３、ＷＭＡ、ＡＭＲ、ＡＡＣ、ＰＣＭ、Ｏｇｇ  ＶｏｒｂｉｓあるいはＡＴＲＡＣ３ファイルのようなデジタルオーディオファイルがある。マルチメディアファイルは、オーディア再生用の符号化データを備えていても良い。符号化データは復号されなければならず、また、再生される前の後処理（例えば、デインタリーブ化）をおそらく行わなければならない。ＰＣＭ（パルス符号変調）データの場合、このデータはインタリーブ形式で外部ソースによって提供されても良い。ここで左右オーディオチャネル用に意図されているデータ要素は、２つのデータ要素のセットに分けられる。これは、符号化データ（例えば、ＷＭＡ）が提供される場合に、デコーダによって出力されるデータストリームにも適用しても良い。データ要素が提供されると、各チャネルのサンプルが交互にデインタリーブされる前に、そのデータ要素は記憶されても良い。
【００２８】
本明細書で参照されるデータ要素を用いることは、シングルデジタルデータビットあるいは相関デジタルデータビットのセットであることを意味する。この相関データビットは、例えば、オーディオサンプルとともに構成しても良く、これは、アナログ信号に変換される時に再生され得る。
【００２９】
本明細書で使用されるインタリーブ化データ要素を用いることは、２つ以上の異なるデータ要素のセットに関連する、例えば、左あるいは右オーディオチャネルに関連するデータ要素であることを意味する。これは、データ要素のセットそれぞれに関連するサンプルを交互に配置するリストあるいは配列で配置されている。データ要素の配列では、最初及び最後のデータ要素は常にそれら自身の正しい位置に配置され、再配置する必要はない。以下では、２つのデータ要素のセットについて言及する。しかしながら、本発明は、２つ以上のデータ要素のセットに関連するデータ要素をソートすることにも適用されても良い。その場合、奇数番号のデータ要素のセットと偶数番号のデータ要素のセットは対称関係にあり、これは、以下に説明するように、任意のデータ要素の位置を再配置することをより容易にする。
【００３０】
本明細書で使用されるデインタリーブ化データ要素は、第１あるいは第２のデータ要素のセットに関連するデータ要素であり、これらは、データ要素の配列でそうなるように配置されている。そうすることで、各セットのデータ要素は、配列内で、連続した順序でグループ化される。第１セットに関連するデータ要素は、例えば、配列内の最初に現れる。一方、第２セットに関連するデータ要素は、配列内の最後に現れる。
【００３１】
図２は、本発明に従うマルチメディアデコーダ１００を示している。マルチメディアデコーダ１００は、入力ファイル、例えば、インタリーブ化デジタルオーディオファイルを、外部ソースから受信するための第１入力手段を備えている。外部ソースは、移動端末内のメモリであっても良く、あるいは、無線あるいは有線通信インタフェースを介してデータ要素を送信する別のソースであっても良い。また、マルチメディアデコーダは、入力ファイルを再生するためのコマンドを受信する第２入力手段を備えている。このようなコマンドには、マン−マシンインタフェースを介して移動端末１のユーザによって実行される、例えば、「再生」、「ポーズ」、「停止」、「巻き戻し」及び「送り」コマンドがある。
【００３２】
マルチメディアデコーダ１００は、デインタリーブ対象の受信データ要素を一時的に記憶するためのメモリあるいはバッファ１１０を備えている。後述するように、バッファに設定されているメモリ（１１０）のメモリ位置番号は所定のものである。メモリは、データ要素を一時的に記憶するためのランダムアクセスメモリ（ＲＡＭ）であっても良い。また、メモリ１１０は、マルチメディアデコーダ１００が実装されているチップ上の専用エリアとして提供されても良い。移動端末１は、第２メモリ１１１で集約して示される、様々な他のメモリを備えていても良い。第２メモリ１１１は、リードオンリメモリ（ＲＯＭ）、ＲＡＭ及び加入者アイデンティティモジュール（ＳＩＭ）カードを備えていても良い。第２メモリ１１１では、複数の定数及び変数が記憶されていても良く、これは、例えば、移動端末１の任意のプロセッサによって使用されても良い。第２メモリ１１１は、プロセッサー１２０のようなコントローラ装置によって実行される場合に、本発明に従う方法を実行するためのコンピュータ可読命令を記憶しても良い。プロセッサ１２０は、本発明の方法に従って、メモリ１１０のメモリ位置のセット内で、データ要素の配列をデインタリーブするための論理関数を実現するために必要な回路を備えている。プロセッサ１２０は、デジタル信号プロセッサ、マイクロプロセッサ、様々なアナログデジタルコンバータ、ＡＳＩＣ（特定用途集積回路）及び配線接続論理回路の１つ以上で構成されていても良い。
【００３３】
以下に説明するように、バッファ１１０とともにプロセッサ１２０は、バッファ内に記憶されているデータ要素をデインタリーブするためのデインタリーバ１３０を構成しても良い。入力データを復号するように構成されているデコーダ１４０は、バッファ１１０と出力手段に接続されている。出力手段は、オーディオミキサー２００に接続されていても良く、これは、復号オーディオデータと、任意の他のオーディオデータ、例えば、出力データ編集用のデータとを混合するように構成されている。オーディオミキサ２００の出力は、ポスト−プロセッサ２１０に接続されていて、これは、混合されたオーディオデータを後処理するために提供される。後処理（ポストプロセス）は、例えば、ノイズレベルを削減するためのフィルタリングであっても良い。ポスト−プロセッサ２１０の出力は、デジタル信号をアナログ信号に変換するように構成されているＤ／Ａコンバータに接続されていて、これは、スピーカ１１によって再生されても良い。スピーカあるいはイヤホーン以外のものが、アクセサリコネクタ１７を介して、動作可能なようにＤ／Ａコンバータに接続されても良い。
【００３４】
本発明に従うインタリーブ化データ要素をソートするためのインプレース（in-place：配置済）方法の第１実施形態を、図３及び図４を参照して説明する。本明細書で使用するインプレースとは、データ要素の配列をソートするために必要なメモリ位置の数が、配列のデータ要素の数に対応していて、おそらくは、これには、以下に説明するように、任意の補助的な不要な（garbage）データを伴っていることを意味するように意図されているものである。
【００３５】
図３では、各ボックスはメモリ位置を示していて、これは、データ要素を含んでいる。グレー表示のボックスは、第１セットのデータ要素に関連するデータ要素を含むメモリ位置を示していて、白表示のボックスは、第２セットのデータ要素に関連するデータ要素を含むメモリ位置を示している。本実施形態では、バッファ１１０に記憶される入力ベクトルは、６つのデータ要素を含んでいる。バッファ１１０のメモリ位置は、バッファ１００の最初のメモリ位置から開始する、０から５のインデックスが付与されている。
【００３６】
図４は、バッファ１１０のデータ要素のデインタリーブするための、本発明に従う方法のフローチャートを示している。第１ステップ３００で、再配置シーケンス内で再配置対象の２つの第１データ要素は、プロセッサ１２０によってバッファから取り出され（withdrawn）、例えば、プロセッサのレジスタファイル１２１に一時的に記憶される。図３の実施形態では、第１データ要素Ｎ１及び第２データ要素Ｎ２がそれぞれバッファ１１０から取り出される。取り出されたデータ要素の１つが第１セットのデータ要素に関連し、もう１つのデータ要素が第２セットのデータ要素に関連するように、データ要素は選択される。図３では、インデックス１及び４のメモリ位置に記憶されている番号４及び３のデータ要素がそれぞれ取り出される。データ要素を含まないメモリ位置は、Ｈ（ホール：ＨＯＬＥ）で示される。
【００３７】
図４の第２ステップ３１０で、取り出されたデータ要素の宛先位置が判定される。本実施形態では、データ要素に番号が付加される。つまり、プロセッサ１２０は、データ要素の宛先位置のインデックス（番号−１＝宛先位置のインデックス）を判定する。次のステップ３２０で、取り出されたデータ要素の挿入対象である宛先位置に、任意のデータ要素を含んでいるかを判定する。そうである場合、再配置シーケンスはステップ３３０に進み、そこで、宛先位置あるいはメモリ位置に現在記憶されているデータ要素を、ステップ３３０で取り出されたデータ要素に置き換える。つまり、宛先位置に記憶されているデータ要素は取り出された後、一時的に記憶される。一方で、データ要素Ｎ１とＮ２は、自身の正しい位置に挿入される。取り出されたデータ要素は、ここでは、Ｎ１及びＮ２で示されている。ステップ３３０から、再配置シーケンスはステップ３１０に戻る。但し、ステップ３２０の結果が否である場合、即ち、データベクトルにホールが存在する場合、取り出されたデータ要素Ｎ１、Ｎ２は、自身の宛先位置に直接挿入されても良い。６つのメモリ位置を有するバッファ１１０では、再配置対象のデータ要素が正しく判定される場合に、ホールだけが一回現れる。つまり、本実施形態では、ホールが一旦ヒットすると、シーケンスは終了となる。しかしながら、このことは、バッファ１１０のあらゆるサイズに対するものではなく、以下に説明するような場合にはあてはまらない。
【００３８】
図５及び図６は、本発明の第２実施形態を示している。図５では、各ボックスは、データ要素を含むメモリ位置を示している。ここで、グレー表示のボックスは、データ要素を示していて、これは、データ要素の配列がデインタリーブされる場合の自身の正しい位置を持っている。バッファの各データ要素は、第１あるいは第２セットのデータ要素に属している。第２実施形態では、バッファは、０から１５のインデックスが付加されている、１６のメモリ位置を備えている。バッファは、１から１６の番号が付加されたメモリ位置に記憶されている１６のデータ要素を含んでいる。最初と最後のデータ要素は、自身の正しい位置に配置されている。
【００３９】
図６のフローチャートの第１ステップ４０１で、取り出し対象の第１データ要素のインデックスが判定される。メモリ位置（及びデータ要素の配列の位置）は０からインデックスが付加され、バッファの長さは、変数ＬＥＮＧＴＨに割り当てられる。第１及び第２インデックスはそれぞれ、ＨＯＬＥ１及びＨＯＬＥ２で示される。図５では、中央の位置に記憶されるデータ要素が選択される。これは、ＨＯＬＥ１＝ＬＥＮＧＴＨ／２−１とＨＯＬＥ２＝ＬＥＮＧＴＨ／２として、ホールを計算することによって判定されても良い。ステップ４０２で、位置変数ＰＯＳ１、ＰＯＳ２は、ＨＯＬＥ１及びＨＯＬＥ２の値にそれぞれ割り当てられる。ステップ４０２で、ＰＯＳ１及びＰＯＳ２の位置に記憶されているデータ要素の値が、バッファ１１０から取り出され、ここでは、それぞれＮ１及びＮ２で示されている。また、バッファの最初と最後のデータ要素が自身の正しい位置にあり、また２つのデータ要素が、各再配置シーケンスで再配置されるように、カウンタ値Ｉが０に設定され、反復停止値ＩＳＴＯＰが（ＬＥＮＧＴＨ）／２に設定される。図５の実施形態では、バッファのインデックス７及び８の中央の位置に記憶されている２つのデータ要素が、取り出す対象の第１データ要素のインデックスとして選択される。また、各再配置シーケンスであるデータ要素のみを取り出すことが可能である。各再配置シーケンスで２つのデータ要素を取り出すことは、データ要素を検索するためにアクセスしなければならないバッファの回数を抑える、つまり、データ処理速度を向上する効果がある。また、取り出すデータ要素の最初の位置あるいはメモリ位置に、中央位置あるいはメモリ位置を選択することは、第１及び第２のセットのデータ要素と交互に関連する、データ要素でインタリーブ化されたベクトルにおいて本来の対称性を使用することになる。これは、別の位置、例えば、２番目（インデックス１）の位置と最後から２番目（インデックス１４）の位置を選択することによっても達成される。
【００４０】
ステップ４０４で、すべてのデータ要素が再配置されているかが判定される。つまり、カウンタ値ＩがＩＳＴＯＰより小さいかがチェックされる。ステップ４０４の判定がｙｅｓの場合、データ要素の再配置が完了し、処理が終了される。しかしながら、ステップ４０４の判定がｎｏである場合、処理はステップ４０５に進み、ここでは、ステップ４０３で取り出されたデータ要素の宛先位置のインデックスが判定される。つまり、ＰＯＳ１とＰＯＳ２が宛先位置のインデックスに割り当てられる。この宛先位置は、データ要素の番号をチェックすることによって判定されても良い。選択的には、宛先位置は、ソース位置のインデックスとバッファの長さあるいはベクトルの長さを入力とする、宛先位置処理ｄｅｓｔ（ＰＯＳ、ＬＥＮＧＴＨ）、例えば、以下に説明される、図７の処理に従って判定される。
【００４１】
次のステップ４０６で、例えば、ＰＯＳ１及びＰＯＳ２の新規の値がＨＯＬＥ１及びＨＯＬＥ２それぞれの値に対応するかを判定することによって、宛先位置の任意のインデックスがホールＨ（即ち、データ要素なし）を有するかどうかが判定される。ステップ４０６の判定がｎｏである場合、処理はステップ４０７に進む。ここで、判定された宛先位置である、現在のＰＯＳ１とＰＯＳ２に現在記憶されているデータ要素が取り出され、それぞれ一時的にＴＥＭＰ１とＴＥＭＰ２に記憶される。次に、ステップ４０３で取り出されたデータ要素の値であり、Ｎ１とＮ２として記憶される値が、ステップ４０８で、それらの正しい位置に挿入される。つまり、Ｎ１とＮ２は、それぞれＴＥＭＰ１とＴＥＭＰ２の値に割り当てられる。ステップ４０３で取り出されるデータ要素はここで再配置される。ここで、再配置シーケンスは、ステップ４１０で、カウンタ値Ｉの値を１インクリメントすることによって終了される。次に、処理は、ステップ４０４に戻る。
【００４２】
ステップ４０６の判定がｙｅｓである場合、ホールはヒットする。図５では、これは、４回目の反復中に発生する。次に、処理はステップ４１１に進み、ここで、Ｎ１とＮ２の値は、ＰＯＳ１とＰＯＳ２によって設定される宛先位置に挿入される。つまり、取り出さられたデータ要素Ｎ１とＮ２は、任意の値をＴＥＭＰ１とＴＥＭＰ２に割り当てることなく直接自身の正しい位置に挿入される。ここで、配列内にホールＨは存在していないが、すべてのデータ要素は、まだ自身の正しい位置にはない。その結果、一時的にレジスタファイルに記憶されるデータ要素はなく、また、すべてのデータ要素は、自身の正しい位置にも配置されていない。ステップ４１１で、取り出し対象の２つの新規のデータ要素のインデックスが判定される。取り出し対象のインデックスを判定するために、プロセッサは、間違って配置されているデータ要素を選択する試行をしなければならない。本実施形態に従えば、ステップ４０３で取り出された第１データ要素が中央位置に記憶されているものとして選択されている場合、例えば、図５の再配置シーケンス４及び７の間に、ホールＨがヒットするときに、ホールＨの次の位置のデータ要素が選択される。ステップ４１２で、取り出し対象の新規のデータ要素のインデックスが、以前のホール、即ち、ＰＯＳ１＝ＨＯＬＥ１−１とＰＯＳ２＝ＨＯＬＥ２＋１の次の位置のインデックスに設定される。
【００４３】
取り出し対象の新規のデータ要素の位置を選択するための上述のスキームは、間違って配置されているデータ要素を検出することを確実にする。しかしながら、プロセッサ１２０は、間違って配置されているデータ要素を選択するための別のスキームを使用しても良く、これは、各特定の場合にテストされかつ評価されなければならない。
【００４４】
取り出し対象の新規のデータ要素の割当後、新規のホールＨＯＬＥ１とＨＯＬＥ２のインデックスは、ステップ４１３で、それぞれＰＯＳ１とＰＯＳ２に設定される。ステップ４１４で、インデックスＰＯＳ１とＰＯＳ２を有するメモリ位置に記憶されているデータ要素が取り出され、一時的にＮ１とＮ２として記憶される。次に、取り出されたデータ要素の再配置シーケンスは、ステップ４１０に進む。
【００４５】
データ要素は、常に番号が付加されるわけではない。このような場合、取り出されたデータ要素の宛先位置が、自身の宛先位置を計算するために判定されても良い。図７は、宛先位置を判定するための方法を示している。宛先位置ｄｅｓｔ（ＰＯＳ，ＬＥＮＧＴＨ）を判定するための方法への入力として、ソース位置ＰＯＳと受け入れ可能なベクトルあるいはバッファの長さＬＥＮＧＴＨが使用される。次に、長さＬＥＮＧＴＨを有するベクトルのインデックスＰＯＳを有するデータ要素の宛先位置あるいは正しいメモリ位置のインデックスが判定される。図７の最初のステップ５００で、データ要素が取り出される位置のインデックスＰＯＳが偶数であるかが判定される。ステップ５００の判定がｙｅｓである場合、ステップ５０１で、宛先位置のインデックスがＰＯＳ／２に設定される。しかしながら、ステップ５００の判定がｎｏである場合、ステップ５０２で、宛先位置のインデックスがＬＥＮＧＴＨ／２＋ＰＯＳ／２に設定される。
【００４６】
プロセッサ１２０は、自身の番号を読み出すことによって、あるいは自身の正しい位置を算出することによって、取り出されたデータの宛先位置を判定するように構成されても良い。また、プロセッサは、例えば、上述のようにカウンタ値Ｉをインクリメントすることによって、再配置が実行される回数を追跡することによって、すべてのデータ要素が正しく配置されていることを判定しても良い。バッファ１１０内のデータ要素数あるいはバッファ内のメモリ位置の数を知ることによって、実行された再配置数は、常に、データ要素の数あるいはメモリ位置の数から２減算した数になるようにすべきである。
【００４７】
本発明に従って使用されても良いバッファサイズは、図３及び図５で示される実施形態に限定されるものではない。しかしながら、上述の正しく配置されていないデータ要素を選択する方法が使用される場合、本発明に従うアルゴリズムによって、デインタリーブすることができるバッファサイズには制限が存在する。本発明に従って使用することができるバッファサイズは、図８に示される方法に従って判定されても良い。最初のステップ６００で、与えられる長さに従うインタリーブ化数を有するベクトルＶが生成される。ベクトルは、例えば、ベクトル｛１、４、２、５、３、６｝によって与えられても良い。ベクトルの最初と最後のデータ要素は、自身の正しい位置を持っているべきである。次のステップ６１０で、例えば、上述の図６に従うソーティング（sorting）アルゴリズムが、ステップ６００で生成されるベクトルについて実行される。ベクトルのソーティングが完了すると、ステップ６２０で、ベクトルのすべての要素が自身の正しい位置にあるかが判定される。例えば、上述のように、ベクトルが生成された場合、最初のもの以外の、ベクトルのすべてのデータ要素の値が、先行するデータ要素の値よりも大きいかをチェックすることによって、その判定が実行される。そうすることで、上述のインタリーブ化ベクトルは、｛１、２、３、４、５、６｝の順序となる。ステップ６３０の判定がｙｅｓである場合、ベクトル長は受け入れられる。しかしながら、ステップ６３０の判定がｎｏである場合、ベクトル長は受け入れられず、処理はステップ６００に戻り、そこで、異なる長さのベクトルがテストされる。
【００４８】
本発明のソーティングアルゴリズムに従って受け入れることができない長さになるベクトルあるいはバッファを使用したい場合は、そのようなベクトルは、受け入れ可能な長さを有するベクトルを取得するためにバッファ１１０に読み出される不要データ要素の数で補間されても良い。不要データ要素は、インデックス０で開始するバッファの始めに位置している。再配置のためのデータ要素が上述のように選択される場合、例えば、２０４８のデータ要素を備えるベクトルは受け入れられない。次に受け入れられるベクトル長は２０５４である。つまり、２０５４のメモリ位置を有するバッファを使用することができる。長さ２０４８のベクトルをデインタリーブするために、ベクトルがバッファに読み出される前に、６つの不要データ要素が、長さ２０５４のバッファに読み出される。次に、ベクトルのデータ要素がデインタリーブされる。使用される不要データ要素の数を追跡することによって、デインタリーブされる場合に、正しいベクトルを検索することができる。
【００４９】
本発明は、特定の実施形態を参照して説明されている。しかしながら、上述の実施形態以外の他の実施形態が、本発明の範囲内で等しく可能である。ハードウェアあるいはソフトウェアによって実行する上述の方法以外の異なる方法のステップを、本発明の範囲内で提供するようにしても良い。本発明の異なる特徴及びステップは、上述以外の他の組み合わせで組み合わされても良い。本発明は、請求項によってのみ制限されるものである。
【図面の簡単な説明】
【００５０】
【図１】移動端末の前面図である。
【図２】オーディオ経路に接続されている、本発明に従う処理装置のブロック図である。
【図３】第１実施形態のメモリのメモリ位置及びそれに記憶されているデータ要素を示すブロック図である。
【図４】本発明に従うデータ要素をソートするための方法の一実施形態のフローチャートである。
【図５】第２実施形態のメモリのメモリ位置及びそれに記憶されているデータ要素を示すブロック図である。
【図６】本発明に従うデータ要素をソートするための方法の第２実施形態のフローチャートである。
【図７】データ要素の宛先位置を判定するための方法のフローチャートである。
【図８】ある長さを有するベクトルが、本発明に従って受け入れられるかを判定するための方法のフローチャートである。
【図１】
2007507933.tif 000003
【図２】
2007507933.tif 000004
【図３】
2007507933.tif 000005
【図４】
2007507933.tif 000006
【図５】
2007507933.tif 000007
【図６】
2007507933.tif 000008
【図７】
2007507933.tif 000009
【図８】
2007507933.tif 000010
【国際調査報告】
2007507933.tif 000011
2007507933.tif 000012
2007507933.tif 000013