Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
JP7746401B2 - エンコーディングおよびデコーディング方法、およびデバイス、並びにシステム - Google Patents
[go: Go Back, main page]

JP7746401B2 - エンコーディングおよびデコーディング方法、およびデバイス、並びにシステム - Google Patents

エンコーディングおよびデコーディング方法、およびデバイス、並びにシステム

Info

Publication number
JP7746401B2
JP7746401B2 JP2023557239A JP2023557239A JP7746401B2 JP 7746401 B2 JP7746401 B2 JP 7746401B2 JP 2023557239 A JP2023557239 A JP 2023557239A JP 2023557239 A JP2023557239 A JP 2023557239A JP 7746401 B2 JP7746401 B2 JP 7746401B2
Authority
JP
Japan
Prior art keywords
parity
target
check matrix
candidate
matrix
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2023557239A
Other languages
English (en)
Other versions
JP2024511046A (ja
Inventor
ホワーン，コーァチャオ
コン レイモンド リョン，ワイ
マー，ホゥイシヤオ
ヤーン，シヤオリーン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Publication of JP2024511046A publication Critical patent/JP2024511046A/ja
Application granted granted Critical
Publication of JP7746401B2 publication Critical patent/JP7746401B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/19—Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/1174—Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1111—Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H03M13/1168—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices wherein the sub-matrices have column and row weights greater than one, e.g. multi-diagonal sub-matrices
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/61—Aspects and characteristics of methods and arrangements for error correction or error detection, not provided for otherwise
    • H03M13/615—Use of computational or mathematical techniques
    • H03M13/616—Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/61—Aspects and characteristics of methods and arrangements for error correction or error detection, not provided for otherwise
    • H03M13/618—Shortening and extension of codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Algebra (AREA)
  • Computing Systems (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)

Description

本開示の実施形態は、一般的に、通信技術の分野に関する。そして、より特定には、エンコーディングおよびデコーディング方法、およびデバイス、並びにシステムに関する。
通信システムにおいて、情報は、信号の形態で送信端から送られ、そして、光ファイバ、ケーブル、または、電波といった、通信チャネルを通じて、受信端に送信される。このプロセスにおいては、チャネル内のノイズ、または、受信端および送信端からのノイズが、たいてい、信号に重畳（superimposed）され、それにより、受信端によって受信された信号の誤り（error）を引き起こす。受信端が、誤って受信された信号に基づいて、送信端によって送信された元の信号を復元することができるように、現在、信号が送信される前に情報をエンコーディングするために、前方誤り訂正(Forward Error Correction、FEC)技術が通信システムにおいて、一般的に使用されている。加えて、FEC技術は、ストレージシステムにも、また、広く適用されている。
FECベースのエンコーディング技術は、例えば、ハミング符号(Hamming code)、BCH符号(BCH code)、RS符号、および、ターボプロダクト符号(Turbo product code、TPC)を含んでいる。ハミング符号は、単純な硬判定デコーディング方式（hard-decision decoding scheme）を用いる完全な符号（perfect code）であり、そして、ハミング符号は、1ビット誤りを検出して、かつ、訂正することができる。具体的には、ハミング符号のために、パリティビットの概念が使用されている。情報は、最初にグループ化され、そして、次いで、情報ビットの各グループの前にチェックビットが追加される。このデザインにおいては、情報の有効性（validity）を検証することができ、そして、情報内の誤りの位置を、さらに示すことができる。実際には、様々な形式の拡張ハミング符号が提供されている。拡張ハミング符号の原理は、追加的なパリティビットまたは行（row）ベクトルを使用することによって、従来のハミング符号を拡張して、強化された検出および誤り訂正能力を実施することである。しかしながら、単一拡張（single-extended）ハミング符号の現在の性能は、理想的なものではなく、そして、二重拡張（double-extended）ハミング符号の性能は改善されているが、エンコーディングおよびデコーディングの複雑性が比較的に高い。
一般的に、本開示の例示的な実施形態は、二重拡張ハミング符号を生成するための方式、並びに、関連するエンコーディング方式およびデコーディング方式を提供する。
本開示の第１態様に従って、エンコーディング方法が提供される。本方法においては、エンコーディングのための生成行列が獲得される。本開示のコンテキストにおいて、前記生成行列は、エンコーディングのためのハミング符号のターゲットパリティチェック行列に基づいて決定され、かつ、前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定される。前記ターゲット関数は、前記ターゲットパリティチェック行列に基づいて拡張された非オールゼロ行ベクトルを決定するために使用される。前記ターゲット関数は、既定の関数セットのうちの１つである。本方法においては、前記生成行列を使用することによって情報ビットがエンコーディングされて、エンコーディングされたデータストリームを獲得する。本方法は、さらに、前記エンコーディングされたデータストリームを送信するステップを含む。
本発明に係るこの実施形態において提供されるエンコーディング方法では、改良された二重拡張ハミング符号が使用され、かる、改良された二重拡張ハミング符号のターゲットパリティチェック行列は、より少ない操作量を有し、所定の関数セットから選択されるターゲット関数に基づいて獲得され、その結果、そうした拡張ハミング符号は、特定のコード空間において、より低いエンコーディング複雑性および最適化された性能を実装することができる。
前記第１態様に係る第１実装において、前記ターゲット関数h(S0,i，S1,i，S2,i)は、非オールゼロ行ベクトルに対応している列ベクトルに係る最初の3個の要素S0,i、S1,i、S2,iのうちの少なくともいくつかの要素に基づいて、非オールゼロ行ベクトルを決定し、かつ、
前記既定の関数セットは、
のうちの１つ以上を含む。
前記第１態様に係る第２実装において、前記ハミング符号のコード長は180であり、前記情報ビットの長さは170であり、前記ターゲットパリティチェック行列の第9行における全ての要素は1であり、かつ、 前記ターゲット関数h(S0,i，S1,i，S2,i)は、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S8,iを決定し、ここで、iは、0以上、かつ、180未満の整数であり、
であり、かつ、S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
前記第１態様に係る第３実装において、前記ハミング符号のコード長は128であり、前記情報ビットの長さは119であり、前記ターゲットパリティチェック行列の第８行における全ての要素S8,iは1であり、かつ、前記ターゲット関数h(S0,i，S1,i，S2,i)は、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S7,iを決定する。ここで、iは、0以上、かつ、128未満の整数であり、
であり、かつ、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
前記第１態様に係る第４実装において、前記ハミング符号のコード長は64であり、前記情報ビットの長さは56であり、前記ターゲットパリティチェック行列の第７行における全ての要素S7,iは1であり、かつ、前記ターゲット関数h(S0,i，S1,i，S2,i)は、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S6,iを決定する。ここで、iは、0以上、かつ、64未満の整数であり、
であり、かつ、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
前記第１態様に係る第５実装において、前記生成行列は、システムチェック行列に基づいて決定され、かつ、前記システムチェック行列は、前記ターゲットパリティチェック行列を変換することによって獲得される。
前記第１態様に係る第６実装において、前記既定の関数セットは、前記ターゲットパリティチェック行列に基づいて拡張された前記非オールゼロ行ベクトルを決定するための複数の候補関数を含む。
前記第１態様に係る第７実装において、前記ターゲットパリティチェック行列は、前記複数の候補関数に基づいて、複数の候補パリティチェック行列を決定するステップと、前記複数の候補パリティチェック行列から非特異行列を選択するステップであり、第１候補パリティチェック行列セットを獲得するステップと、前記第１候補パリティチェック行列セットを系統的な形式の第２候補パリティチェック行列セットへと変換するステップと、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第３パラメータを決定するステップであり、前記第３パラメータは、前記ハミング符号のエンコーディング複雑性を示すステップと、前記第３パラメータに基づいて、前記第１候補パリティチェック行列セットから候補パリティチェック行列の第１グループを選択するステップと、前記候補パリティチェック行列の第１グループから前記ターゲットパリティチェック行列を決定するステップと、により決定される。
前記第１態様に係る第８実装において、前記ターゲットパリティチェック行列は、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に関連付けられた第４パラメータを決定するステップであり、前記第４パラメータは、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に対応する前記ハミング符号の最小コード重みの量を示すステップと、前記第４パラメータに基づいて、前記候補パリティチェック行列の第１グループから候補パリティチェック行列の第２グループを選択するステップと、前記候補パリティチェック行列の第２グループから、前記ターゲットパリティチェック行列を決定するステップと、により、前記候補パリティチェック行列の第１グループから決定される。
前記第１態様に係る第９実装において、前記ターゲットパリティチェック行列は、前記複数の候補関数に基づいて、複数の候補パリティチェック行列を決定するステップと、前記複数の候補パリティチェック行列から非特異行列を選択するステップであり、第１候補パリティチェック行列セットを獲得するステップと、前記第１候補パリティチェック行列セットを、系統的な形式の第２候補パリティチェック行列セットへと変換するステップと、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第４パラメータを決定するステップであり、前記第４パラメータは、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に対応する前記ハミング符号の最小コード重みの量を示すステップと、前記第４パラメータに基づいて、前記第１候補パリティチェック行列セットから候補パリティチェック行列の第１グループを選択するステップと、前記候補パリティチェック行列の第１グループから前記ターゲットパリティチェック行列を決定するステップと、
により、決定される。
前記第１態様に係る第１０実装において、前記ターゲットパリティチェック行列は、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に関連付けられた第３パラメータを決定するステップであり、前記第３パラメータは、前記ハミング符号のエンコーディング複雑性を示すステップと、前記候補パリティチェック行列の第１グループから、候補パリティチェック行列の第２グループを選択するステップであり、前記候補パリティチェック行列の第２グループは、既定の閾値未満の前記第３パラメータを有するステップと、前記候補パリティチェック行列の第２グループから前記ターゲットパリティチェック行列を決定するステップと、により、前記候補パリティチェック行列の第１グループから決定される。
前記第１態様に係る第１１実装において、前記系統的な形式の第２候補パリティチェック行列セットは、前記第１候補パリティチェック行列セット内の各候補パリティチェック行列について、少なくともいくつかの線形独立列ベクトルを、対応する候補パリティチェック行列の右端まで、右から左へ移動するステップと、前記対応する候補パリティチェック行列の右部分が単位行列であるように、基本行変換を実行するステップと、による、変換を通じて獲得される。
前記第１態様に係る第１２実装において、前記ターゲットパリティチェック行列は、前記関数セットにおける前記候補パリティチェック行列の第２グループ内の各候補パリティチェック行列に対応する関数の操作量を決定するステップと、前記操作量に基づいて、前記ターゲットパリティチェック行列を決定するステップと、により、前記候補パリティチェック行列の第２グループから決定される。
本開示の第２態様に従って、デコーディング方法が提供される。本方法は、データストリームを受信するステップと、デコーディングのためにハミング符号のターゲットパリティチェック行列を獲得するステップであり、前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、前記ターゲット関数は、前記ターゲットパリティチェック行列に基づいて、拡張された非オールゼロ行ベクトルを決定するために使用され、かつ、前記ターゲット関数は、既定の関数セットのうちの１つであるステップと、前記ターゲットパリティチェック行列を使用することにより、前記データストリームをデコーディングするステップと、を含む。
本発明に係るこの実施形態において提供されるデコーディング方法では、改良された拡張ハミング符号が使用され、改良された拡張ハミング符号のターゲットパリティチェック行列は、より少ない操作量を有し、所定の関数セットから選択されるターゲット関数に基づいて獲得され、その結果、そうした拡張ハミング符号は、エンコーディング端によって出力されるコードワードを変更することなく、デコーディング端において、より低い復号複雑性および最適化された性能を実現することができる。
前記第２態様に係る第１実装において、前記ターゲット関数h(S0,i，S1,i，S2,i)は、非オールゼロ行ベクトルに対応している列ベクトルに係る最初の3個の要素S0,i、S1,i、S2,iのうちの少なくともいくつかの要素に基づいて、非オールゼロ行ベクトルを決定し、かつ、前記既定の関数セットは、
のうちの１つ以上を含む。
前記第２態様に係る第２実装において、前記ハミング符号のコード長は180であり、前記情報ビットの長さは170であり、前記ターゲットパリティチェック行列の第9行における全ての要素は1であり、かつ、前記ターゲット関数h(S0,i，S1,i，S2,i)は、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S8,iを決定し、
である。ここで、iは、0以上、かつ、180未満の整数であり、S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
前記第２態様に係る第３実装において、前記ハミング符号のコード長は128であり、前記情報ビットの長さは119であり、前記ターゲットパリティチェック行列の第８行における全ての要素S8,iは1であり、かつ、前記ターゲット関数h(S0,i，S1,i，S2,i)は、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S7,iを決定する。ここで、iは、0以上、かつ、128未満の整数であり、
であり、かつ、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
前記第２態様に係る第４実装において、前記ハミング符号のコード長は64であり、前記情報ビットの長さは56であり、前記ターゲットパリティチェック行列の第７行における全ての要素S7,iは1であり、かつ、前記ターゲット関数h(S0,i，S1,i，S2,i)は、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S6,iを決定する。ここで、iは、0以上、かつ、64未満の整数であり、
であり、かつ、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
前記第２態様に係る第５実装において、前記既定の関数セットは、前記ターゲットパリティチェック行列に基づいて拡張された前記非オールゼロ行ベクトルを決定するための複数の候補関数を含む。
前記第２態様に係る第６実装において、前記ターゲットパリティチェック行列は、前記複数の候補関数に基づいて、複数の候補パリティチェック行列を決定するステップと、前記複数の候補パリティチェック行列から非特異行列を選択して、第１候補パリティチェック行列セットを獲得するステップと、前記第１候補パリティチェック行列セットを系統的な形式の第２候補パリティチェック行列セットに変換するステップと、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第３パラメータを決定するステップであり、前記第３パラメータは、前記ハミング符号のエンコーディング複雑性を示すステップと、前記第３パラメータに基づいて、前記第１候補パリティチェック行列セットから候補パリティチェック行列の第１グループを選択するステップと、前記候補パリティチェック行列の第１グループから前記ターゲットパリティチェック行列を決定するステップと、により、決定される。
前記第２態様に係る第７実装において、前記ターゲットパリティチェック行列は、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に関連付けられた第４パラメータを決定するステップであり、前記第４パラメータは、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に対応する前記ハミング符号の最小コード重みの量を示すステップと、前記第４パラメータに基づいて、前記候補パリティチェック行列の第１グループから候補パリティチェック行列の第２グループを選択するステップと、前記候補パリティチェック行列の第２グループから前記ターゲットパリティチェック行列を決定するステップと、により、前記候補パリティチェック行列の第１グループから決定される。
前記第２態様に係る第８実装において、前記ターゲットパリティチェック行列は、前記複数の候補関数に基づいて、複数の候補パリティチェック行列を決定するステップと、前記複数の候補パリティチェック行列から非特異行列を選択するステップであり、第１候補パリティチェック行列セットを獲得するステップと、前記第１候補パリティチェック行列セットを系統的な形式の第２候補パリティチェック行列セットへと変換するステップと、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第４パラメータを決定するステップであり、前記第４パラメータは、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に対応する前記ハミング符号の最小コード重みの量を示すステップと、前記第４パラメータに基づいて、前記第１候補パリティチェック行列セットから候補パリティチェック行列の第１グループを選択するステップと、前記候補パリティチェック行列の第１グループから前記ターゲットパリティチェック行列を決定するステップと、
により、決定される。
前記第２態様に係る第９実装において、前記ターゲットパリティチェック行列は、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に関連付けられた第３パラメータを決定するステップであり、前記第３パラメータは、前記ハミング符号のエンコーディング複雑性を示すステップと、前記候補パリティチェック行列の第１グループから、候補パリティチェック行列の第２グループを選択するステップであり、前記候補パリティチェック行列の第２グループは、既定の閾値未満の前記第３パラメータを有するステップと、前記候補パリティチェック行列の第２グループから前記ターゲットパリティチェック行列を決定するステップと、により、前記候補パリティチェック行列の第１グループから決定される。
前記第２態様に係る第１０実装において、前記系統的な形式の前記第２候補パリティチェック行列セットは、前記第１候補パリティチェック行列セット内の各候補パリティチェック行列について、少なくともいくつかの線形独立列ベクトルを、前記対応する候補パリティチェック行列の右端まで、右から左へ移動するステップと、前記対応する候補パリティチェック行列の右部分が単位行列であるように、基本行変換を実行するステップと、による、変換を通じて獲得される。
前記第２態様に係る第１１実装において、前記ターゲットパリティチェック行列は、前記関数セットにおけるの前記候補パリティチェック行列の第２グループ内の各候補パリティチェック行列に対応する関数の操作量を決定するステップと、前記操作量に基づいて、前記ターゲットパリティチェック行列を決定するステップと、により、前記候補パリティチェック行列の第２グループから決定される。
前記第２態様に係る第１２実装において、前記ターゲットパリティチェック行列を使用することによって、前記データストリームをデコーディングするステップは、前記ターゲットパリティチェック行列に基づいて、前記データのシンドロームを計算するステップと、前記シンドロームがゼロである場合に、デコーディングされた情報ビットとして、前記データストリームの少なくともいくつかのビットを出力するステップ、または、前記シンドロームがゼロでない場合に、前記ターゲットパリティチェック行列内に前記シンドロームに等しい第１列ベクトルが存在するか否かを判定するステップと、前記ターゲットパリティチェック行列内に前記シンドロームに等しい第１列ベクトルが存在する場合に、前記第１列ベクトルに対応する前記データストリーム内のビットを反転するステップと、前記デコーディングされた情報ビットとして、前記反転の後の前記データストリームのうち少なくともいくつかのビットを出力するステップと、を含む。
本開示の第３態様に従って、エンコーディング装置が提供される。本エンコーディング装置は、少なくとも１つのプロセッサ、および、コンピュータプログラムコードを含む少なくとも１つのメモリを含む。前記少なくとも１つのメモリおよび前記コンピュータプログラムコードは、前記少なくとも１つのプロセッサと協働して、前記エンコーディング装置が本開示の第１態様の方法を実行することを可能にするように構成されている。
本開示の第４態様に従って、デコーディング装置が提供される。本デコーディング装置は、少なくとも１つのプロセッサ、および、コンピュータプログラムコードを含む少なくとも１つのメモリを含む。前記少なくとも１つのメモリおよび前記コンピュータプログラムコードは、前記少なくとも１つのプロセッサと協働して、前記デコーディング装置が本開示の第２態様の方法を実行することを可能にするように構成されている。
装置。
本開示の第５態様に従って、通信システムが提供される。本通信システムは、本開示の第３態様に従ったエンコーディング装置、および、本開示の第４態様に従ったデコーディング装置を含んでいる。
本発明の実施形態で提供される改良された拡張ハミング符号に基づいて、エンコーディング装置、デコーディング装置、並びに、エンコーディング装置およびデコーディング装置を含む通信システムについて、ビット誤り率を大幅に低減することができ、かつ、チャネル干渉に耐える能力を向上させることができ、それによって、システム性能を向上させている。
本開示の実施形態に係る前述および他の特徴、利点、および態様は、添付の図面を参照して、かつ、以下の詳細な説明を参照して、より明らかになる。添付の図面において、同一または類似の参照番号は、同一または類似の要素を表している。
図１は、本開示の一つの例示的な実施形態に従った、通信システムのアーキテクチャの概略図である。 図2は、本開示の一つの例示的な実施形態に従った、エンコーディング方法のフローチャートである。 図3は、本開示の一つの例示的な実施形態に従った、デコーディング方法のフローチャートである。 図4は、本開示の一つの例示的な実施形態に従った、二重拡張ハミング符号、および、従来の拡張ハミング符号の性能のダイアグラムである。 図5は、本開示の一つの例示的な実施形態に従った、電子デバイスのブロック図である。
以下は、添付図面を参照して、本発明の実施形態について説明している。本開示のいくつかの例示的な実施形態が添付の図面に示されているが、本開示は、様々な形態で実施されてよく、そして、本明細書に記載された実施形態に限定されるものとして解釈されるべきではないことが理解されるべきである。反対に、これらの実施形態は、本開示が徹底的に、かつ、完全に理解され得るように提供されている。本発明の添付図面および実施形態は、単に例として使用されているだけであり、本発明の保護範囲を限定するように意図されたものではないことが理解されるべきである。
本明細書で使用される用語「含む(“include”)」およびその変形は、オープンな包含（inclusion）、すなわち、「含むが、それに限定されない（“include but not limited to”）」を示す。特に明記しない限り、用語「または（“or”）」は、「及び／又は（“and/or”）」を意味する。用語「に基づいて（“based on”）」は、「少なくとも部分的に基づいて（“at least partially based on”）」を意味する。「例示的な実施形態（“example embodiments”）」および「いくつかの実施形態（“some embodiments”）」という用語は、「少なくとも１つの例示的な実施形態（“at least one embodiment”）」を表している。他の明示的および暗黙的な定義も、また、以下に含まれ得る。
従来のハミング符号(Hamming)の最小ハミング距離は3であり、そして、従来のハミング符号は、1ビットの誤りを検出して、訂正することができる。ハミング符号の性能を強化するために、追加のパリティビットが、従来のハミング符号、例えば、ハミング符号（2m-1,2m-1-m）に追加されてよく、シングルビット拡張ハミング符号(eHamming)（2m,2m-1-m）を得る。これは、また、以下では「拡張ハミング符号（“extended Hamming code”）」または「従来の拡張ハミング符号（“conventional extended Hamming code”）」とも呼ばれる。従来の拡張ハミング符号は、（m+1）×2mのサイズのパリティチェック行列を有している、それは、以下のように表すことができる。
ここで、Hは、従来のハミング符号(Hamming)（2m-1,2m-1-m）のパリティチェック行列を表している。前記パリティチェック行列のサイズは、m×（2m-1）であり、1は、長さが1のオールワン行ベクトル（all-one row vector）を表しており、そして、0は、オールゼロ列ベクトル（all-zero column vector）を表している。明らかに、Heの最終行は、2mの長さのオールワン行ベクトルである。
従来の拡張ハミング符号(eHamming)の最小ハミング距離は4であり、そして、2ビットの誤りを検出し、かつ、1ビットの誤りを訂正することができる。従来の拡張ハミング符号(eHamming)（2m,2m-1-m）の符号化率は、Re=（2m-1-m）/2mである。より低いコードレートを実現するために、短縮(shorten)技術を使用することによって、q情報ビットが0に設定されてよく、短縮された拡張ハミング符号（2m-q,2m-1-m-q）を獲得する。ここで、0≦q＜（2m-1）/2である。
従来の拡張ハミング符号(eHamming)の関数式は単純であるが、従来の拡張ハミング符号の性能は、さらに改善される必要がある。加えて、いくつかの特定のコード長の場合に、従来の拡張ハミング符号の短縮ビット長は、より長い。例えば、従来の拡張ハミング符号(eHamming)（180,170）につて、従来の拡張ハミング符号の符号パラメータは、m=9であり、そして、短縮ビットの長さは、q=332である。ここで、qは、情報長k=170のほぼ2倍である。この観点で、ハミング符号を改善して、最適化する必要がある。
本発明の実施形態に従って、改良された二重拡張（double-extended）ハミング符号、並びに、改良された二重拡張ハミング符号に基づくエンコーディングおよびデコーディング方法が提供される。改良された二重拡張ハミング符号の目標（target）パリティチェック行列は、より少ない操作量を有し、かつ、既定の関数セットから選択される、ターゲット関数に基づいて獲得され、その結果、そうした拡張ハミング符号は、特定のコード空間において、より低いエンコーディングおよびデコーディングの複雑性（complexity）と、より低いビット誤り率とを実装し、そして、最適化された性能を提供することができる。このようにして、通信システムの耐干渉性が改善される。
図1は、本開示の一つの例示的な実施形態に従った、通信システムのアーキテクチャの概略図である。図1に示されるように、通信システム100は、エンコーディング装置110、デコーディング装置120、および、エンコーディング装置110とデコーディング装置120とを接続するチャネル104を備える。通信システム100のアーキテクチャは、単なる例であり、本開示の範囲に対するいかなる限定も示唆するように意図されたものではない。本開示の実施形態は、他の通信システムにおいても実装され得る。加えて、さらに、通信システム100は、情報またはデータなどを受信し、送信し、エンコーディングし、デコーディングするように構成された、別の要素またはエンティティをさらに含み得ることが理解されるべきである。これらの要素またはエンティティは、説明を簡単にするために、通信システム100には示されていない。しかしながら、それは、本開示の実施形態がこれらの要素またはエンティティを含まないことを意味するものではない。
エンコーディング装置110は、情報またはデータの送信端（transmit end）として機能する。エンコーディング装置110は、ソース(図示せず)から送信されるべき（to-be-sent）情報ビットuを獲得し、情報ビットuをデータストリームcへとエンコーディングし、そして、データストリームcを、チャネル104を介してデコーディング装置120に送信する。チャネル104は、これらに限定されるわけではないが、光ファイバ、ケーブル、または電波を含む、有線または無線接続といった、様々な形態で実装され得る。情報またはデータストリームを送信するプロセスにおいては、チャネル104内のノイズ、または、送信端及び／又は受信端によって導入されるノイズが、たいてい、重畳され、その結果、受信端によって受信されるデータストリーム内にはエラーが存在する。様々なエンコーディングおよびデコーディング技術を使用することによって、通信システム100の耐干渉（interference resistance）性能を良好に高めることができる。
エンコーディング装置110は、様々なエンコーディング方式で情報をエンコーディングすることができる。いくつかの実施形態において、エンコーディング装置110は、ハミング符号をエンコーディング技術として使用してよく、そして、それに対応して、デコーディング装置120も、また、ハミング符号をデコーディング技術として使用する。ハミング符号は、エンコーディングのための生成行列G、および、デコーディングのためのパリティチェック行列Hに対応している。生成行列Gは、パリティチェック行列Hに基づいて決定される。いくつかの実施形態において、生成行列Gは、エンコーディング装置110のために構成されている。情報ビットシーケンスuを送信する前に、エンコーディング装置110は、生成行列uを使用することにより、情報ビットシーケンスuをエンコーディングして、エンコーディングされたデータストリームcを生成する。
デコーディング装置120は、受信端として働く。デコーディング装置120は、チャネル104を介して、エンコーディング装置110からデータストリームcを受信し、そして、データストリームcをデコーディングして、エンコーディング装置110によって送信された元の情報ビットシーケンスuを獲得する。デコーディング装置120は、エンコーディング装置110のエンコーディング方式に対応するデコーディング方式でデータストリームcをデコーディングすることができる。いくつかの実施形態において、デコーディング装置120は、デコーディング技術としてハミング符号を使用し得る。そうした実施形態において、ハミング符号の生成行列Gに対応しているパリティチェック行列Hが、デコーディング装置120のために構成され得る。データストリームcを受信した後で、デコーディング装置100は、最初に、データストリームcおよびパリティチェック行列Hに基づいて、シンドローム（syndrome）Tを決定する。シンドロームがゼロである場合、すなわち、T=0のときは、データストリームcが訂正される必要がないことを示している。シンドロームがゼロでない場合は、データストリーム内にエラーが存在することを示している。この場合に、デコーディング装置120は、シンドロームと一致し、かつ、パリティチェック行列H内にある、列ベクトルに対応しているビットを反転する（flipping）ことによってデータストリームを訂正して、元の情報ビットuを獲得する。
本開示の一つの例示的な実施形態に従って、最適化されたハミング符号が提供され、ビット長をさらに短縮し、そして、従来のハミング符号に基づいて二重拡張を実施する。最適化されたハミング符号は、比較的に単純な関数を使用することによって生成され、その結果、ハミング符号は、より低いデザイン複雑性を有している。加えて、最適化されたハミング符号は、様々なコード長および情報ビット長について、エンコーディングおよびデコーディングの複雑性を低減し、そして、システムの良好な耐干渉性能を提供することができる。
本開示におけるハミング符号(DE-Hamming)のコード長は、2m-qであり、そして、情報ビットの長さは、2m-2-m-qであり、ここで、mは正の整数であって、m≧3、かつ、0≦q＜（2m-1）/2である。ハミング符号のパリティチェック行列HDEは、m×（2m-1-q）の行列であり、そして、以下のように表され得る。
ここで、Hは、コード長が2m-1-qであり、かつ、情報ビット長が2m-1-m-qである従来のハミング符号のパリティチェック行列である。1は、長さが1のオールワン行ベクトルを表しており、0は、m次元のオールゼロ列ベクトルを表しており、そして、Dは、拡張されるべきであり、かつ、その長さが2m-qである非オールゼロ行ベクトルを表している。
数式(2)から、本開示におけるハミング符号のパリティチェック行列(DE-Hamming)HDEを獲得するために、行ベクトルDおよびlが、従来のハミング符号のパリティチェック行列において拡張されることが決定され得る。別の言葉で言えば、パリティチェック行列HDEは、(m+2)次元の列ベクトルを含んでいる。本発明の実施形態に従って、本発明におけるハミング符号(DE-Hamming)のデザインの複雑性を効果的に低減するために、拡張のための非オールゼロ行ベクトルDを生成するように適切な関数が選択され、その結果、本発明におけるハミング符号は、従来のハミング符号(Hamming)および従来の拡張ハミング符号(eHamming)よりも良好なエンコーディングおよびデコーディング性能を有している。
非オールゼロ行ベクトルDを決定するために、関数ｇが考慮され、そして、本関数は、パリティチェック行列HDEの(m+2)次元の行ベクトルを(m+2)次元の列ベクトルにマッピングすることができる。具体的には、関数ｇは、整数iに基づいて(m+2)次元の列ベクトルをマッピングする。ここで、0≦i≦2m-q-1である。ここにおいて、関数ｇは、以下のように決定され得る。
ここで、
である。S0,i、S1,i、…、Sm-1,iは、それぞれに、パリティチェック行列Hの行ベクトルに対応する列ベクトルの要素を表しており、Sm,iは、非オールゼロ行ベクトルDに対応する列ベクトルの要素を表し、そして、最後の列ベクトルの全ての要素は1である。
さらに、関数hは、Sm,iを決定するために使用することができる。これは、以下のように記述される。
関数hは、3ビットの入力、すなわち、S0,i、S1,i、およびS2,iを有しており、そし、1ビットの要素Sm,iを出力する。
明らかに、関数hは、関数hのセット（set）を形成する、28の入出力可能性を有している。関数hのセットは、真理値表によって表され得る。非オールゼロ行ベクトルDの長さが2m-qなので、関数hの出力は、少なくとも１つの値「1」を含んでいる。加えて、関数hの出力が7個、6個、5個の1を含む場合は、それぞれ、関数hの出力が1個、2個、3個の値「1」を含む場合と等価である。従って、一つの例示的な実施形態においては、関数hの出力が1、2、3、4個の値「1」を含んでいる場合のみを考慮する。このように、関数hは、
の可能性を有している。すなわち、関数hのセットは、表1から表4までに示されるように、162個の関数を含んでいる。ここで、関数h j は、ｊ番目（jth）の場合を表しており、ここで、0＜j≦162である。
関数hのセット：h1からh162まで、0＜j≦162、におけるの所与の関数hjについて、(m+2)×(2m-q)のサイズを有する、以下のパリティチェック行列Hjが決定される。
式(5)に基づいて、関数ｇは、以下のように決定され得る。
さらに、パリティチェック行列Hjが決定される。パリティチェック行列Hjが、非特異（non-singular）行列ではない場合に、それは、パリティチェック行列Hjに対応している関数hjが利用可能ではないことを示している。そうでなければ、パリティチェック行列Hjが、非特異行列である場合に、それは、パリティチェック行列Hjに対応している関数hjが利用可能であることを示している。
いくつかの例示的な実施形態において、非特異パリティチェック行列Hjは、系統的（systematic）な形式へと変換される。例えば、m+2の線形独立列ベクトルが、パリティチェック行列Hjから右から左へ選択されてよく、そして、これらの列ベクトルは、以下に示されるように、パリティチェック行列Hjの右端に移動される。
ここで、HRは、パリティチェック行列HDE,jの右部分を表しており、かつ、m+2の線形独立な列ベクトルを含み、かつ、そのサイズが(m+2)×(m+2)である行列であり、そして、HLは、行列HjからHRが除去された後で獲得される(m+2)×（2m-2-m-q）の行列を表している。
さらに、パリティチェック行列HDE,jに対して行基本変換（elementary row transformation）が実行され、その結果、パリティチェック行列の右部分は単位行列（identity matrix）であり、システムチェック行列Hsys,jを獲得する。
ここにおいて、Iは、サイズが(m+2)×(m+2)の単位行列を表し、Pは、サイズが(m+2)×（2m-2-m-q）の行列を表しており、そして、P=(HR)-1HLである。
さらに、関数hjについて、システムハミング符号であり、かつ、サイズが(2m-2-m-q)×(2mq)である生成行列Gjが、式(9)に従って決定され得る。
ここにおいて、Iは、サイズが(2m-2-m-q)×（2m-2-m-q）の単位行列を表している。
ここで、ハミング符号のエンコーディング複雑性は、行列Pにおける要素1の数に関連しおり、そして、要素1の量は、Оjとして示されている。従って、いくつかの例示的な実施形態において、パラメータОjは、本開示におけるハミング符号(DE-Hamming)のエンコーディング複雑性を示す指標（indicator）として使用され得る。
システムチェック行列Hsys,jに基づいて、本開示におけるハミング符号(DE-Hamming)の重み階層（weight hierarchy）が、さらに決定され得る。最小コード重み4の量Ajが、ハミング符号の性能に支配的な影響を及ぼすので、いくつかの例示的な実施形態において、パラメータAjは、ハミング符号の性能を示す指標として使用され得る。
表1から表4までに示される関数hのセット、すなわち関数h1からh162まで、について、上記の操作が繰り返され、そして、それぞれに、エンコーディング複雑性およびハミング符号の性能を示す、パラメータОjおよびAjが決定される。パラメータОjおよびAjのうち１つ以上に基づいて、ターゲット関数(target function)h(S0,i，S1,i，S2,i)、ターゲットパリティチェック行列（target parity-check matrix）HDE、および、低いエンコーディング複雑性と優れた性能とを提供することができるハミング符号を生成するための生成行列Gを決定することができる。
以下は、本発明の一つの実施形態に従った、ハミング符号生成方法を簡単に説明している。いくつかの実施形態において、対応するパリティチェック行列Hjが、関数hのセットにおけるh1からh162までの全てについて決定され得る。いくつかの他の実施形態において、関数hのセットにおけるいくつかの関数hを使用することにより獲得されるパリティチェック行列Hjは、絶対に非特異（non-singular）ではない。例えば、表1から表4までにおける関数h93、h102、h113、h142、h153、およびh162である。このことを考慮して、これらの関数h、および、それらのパリティチェック行列Hjについて、後続のステップは実行されなくてよい。本実施形態においては、関数hのセットにおけるいくつかの関数を含む既定の関数が使用されてよく、そして、複数の候補関数hを含んでいる。
既定の関数セットは、一つの例として使用されている。複数の対応する候補パリティチェック行列Hjは、複数の候補関数hに基づいて決定され得る。これらの候補パリティチェック行列Hjから、第１候補パリティチェック行列セットとして、非特異行列が選択される。第１候補パリティチェック行列セットは、変換されて、系統的な形式で第２候補パリティチェック行列セットを獲得する。第２候補パリティチェック行列セットについて、第２候補パリティチェック行列セットに対応している行列Pは、最初に、パラメータОjに基づいてソートされ得る。そして、既定の閾値より小さいパラメータОjを有する行列Pが、第２候補パリティチェック行列セットから選択される。次いで、これらの行列Pに対応しているパリティチェック行列HDEが、候補パリティチェック行列の第１グループとして決定される。さらに、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第１グループから決定されてよく、そして、ターゲットパリティチェック行列に対応しているターゲット関数h(S0,i，S1,i，S2,i)が決定され得る。この実施形態において、既定の閾値は、要素1の既定の量であり得る。追加的または代替的に、全てのパラメータОjにおいて最小値を有する行列Pが選択され得る。
前述の実施形態の実装では、対応するパラメータAjが、さらに、候補パリティチェック行列の決定された第１グループにおける各候補パリティチェック行列について決定され得る。次いで、パラメータAjに基づいて、ターゲットパリティチェック行列が、第１候補パリティチェック行列グループから決定され、そして、ターゲット関数h(S0,i，S1,i，S2,i)として、対応する関数hが決定される。例えば、最小コード重みの最小量を有する候補パリティチェック行列が、パラメータAjに基づいて、候補パリティチェック行列の第２グループとして、候補パリティチェック行列の第１グループから選択され得る。次いで、ターゲットパリティチェック行列が、第２候補パリティチェック行列グループから決定され、そして、対応する関数hが、ターゲット関数h(S0,i，S1,i，S2,i)として決定される。
他の例示的な実施形態においては、パラメータAjが、最初に考慮され得る。同様に、一つの例として、既定の関数セットが使用される。複数の対応する候補パリティチェック行列Hjが決定され得る。非特異行列が、第１候補パリティチェック行列セットとして、これらの候補パリティチェック行列Hjから選択される。同様に、第１候補パリティチェック行列セットが変換され、系統的な形式で第２候補パリティチェック行列セットを獲得する。第２候補パリティチェック行列セットについて、パラメータAjに基づいて、ソート（sorting）が実行され得る。そして、最小コード重みの最小量を有するパリティチェック行列が、候補パリティチェック行列の第１グループとして、第２候補パリティチェック行列セットから選択される。さらに、ターゲットパリティチェック行列が、候補パリティチェック行列の第１グループから決定される。
前述の実施形態に係る一つの実装において、対応するパラメータОjが、さらに、候補パリティチェック行列の決定された第１グループにおける各候補パリティチェック行列について決定され得る。次いで、パラメータОjに基づいて、ターゲットパリティチェック行列が、第１候補パリティチェック行列グループから決定され、そして、対応する関数hが、ターゲット関数h(S0,i，S1,i，S2,i)として決定される。例えば、既定の閾値よりも小さいパラメータОjを有する候補パリティチェック行列が、候補パリティチェック行列の第１グループにおける各候補パリティチェック行列に関連するパラメータОjに基づいて、候補パリティチェック行列の第２グループとして、選択され得る。例えば、最小コード重みの最小量を有する候補パリティチェック行列が、候補パリティチェック行列の第２グループとして、候補パリティチェック行列の第１グループから選択されてよい。次いで、ターゲットパリティチェック行列が、候補パリティチェック行列の第２グループから決定され、そして、対応する関数hが、ターゲット関数h(S0,i，S1,i，S2,i)として決定される。
候補パリティチェック行列の第２グループからターゲットパリティチェック行列を決定する実装では、関数hのセット内にあり、かつ、候補パリティチェック行列の第２グループにおける各候補パリティチェック行列に対応する、関数hの操作量が決定されてよく、操作量に基づいて、対応するターゲット関数h(S0,i，S1,i，S2,i)、および、候補パリティチェック行列の第２グループからターゲットパリティチェック行列を決定する。例えば、最小操作量を伴う関数hが、ターゲット関数h(S0,i，S1,i，S2,i)として選択される。
本開示に係る一つの例示的な実施形態において、ターゲット関数h(S0,i，S1,i，S2,i)を決定するための既定の関数セットは、表1から表4までに示される関数hの論理式に従って獲得されてよく、そして、既定の関数セットは、以下の関数のうち１つ以上を含む。すなわち、
であり、それぞれに、表1から表4までにおけるh4、h6、h7、h33、h35、h36、h40、h54、h65、h143、およびh152に対応している。しかしながら、上記で提供される既定の関数セットおよび関数hのユニバーサルセットは、単なる例に過ぎないことが理解されるべきである。実際には、要件に従って、より多く、または、より少ない候補関数が含まれてよく、そして、表1から表4までに示されていない候補関数hが含まれてもよい。本開示の範囲は、この態様に限定されるものではない。
本発明に係る一つの実施形態に従って、ハミング符号生成方法が提供される。本方法に従って、様々なコード長および情報ビット長について、適切な関数が、パリティチェック行列を決定するための関数セットから選択される。従って、生成されたハミング符号は、優れた性能を実現し、そして、エンコーディング側とデコーディング側の両方でエンコーディングおよびデコーディングの複雑性を低減することができ、それによって、通信システムの性能を高め、かつ、通信の質を改善している。
本開示の実施形態に従った最適化されたハミング符号、例示的なエンコーディング化プロセス、および、最適化されたハミング符号に基づく例示的なデコーディングプロセスが、図2から図5までを参照して、以下で詳細に説明される。
図2は、本開示の一つの例示的な実施形態に従った、エンコーディング方法200のフローチャートである。方法200は、図1に示されるエンコーディング装置110によって実施されてよく、そして、図1に示されるチャネル104およびデコーディング装置120を含み得る。説明を容易にするために、以下では、図1を参照して方法200を説明する。方法200は、また、他の通信シナリオおよび他のエンコーディング装置に対して適用可能であることが理解されるべきである。
ブロック201において、エンコーディング装置110は、エンコーディングのための生成行列Gを獲得する。生成行列Gは、エンコーディングのためのハミング符号のターゲットパリティチェック行列HDEに基づいて決定される。いくつかの例示的な実施形態において、ターゲットパリティチェック行列HDEは、デコーディングのためのターゲット関数h(S0,i，S1,i，S2,i)に基づいて決定される。ターゲット関数h(S0,i，S1,i，S2,i)は、既定の関数セットのうち１つであり、そして、ターゲットパリティチェック行列HDEに基づいて拡張された非オールゼロ行ベクトルDを決定するために使用される。
既定の関数セットは、ターゲットパリティチェック行列HDEに基づいて拡張された非オールゼロ行ベクトルDを決定するための複数の候補関数を含み得る。いくつかの例示的な実施形態において、ターゲット関数h(S0,i，S1,i，S2,i)は、非オールゼロ行ベクトルDに対応している列ベクトルのうち最初の3個の要素S0,i、S1,i、およびS2,iのうち少なくともいくつかの要素に基づいて、非オールゼロ行ベクトルDを決定し得る。例えば、既定の関数セットは、以下のうち１つ以上を含み得る。
別の例として、既定の関数セットは、代替的に、表1から表4までに示される関数hの一部または全部、もしくは、表1から表4までに示されていない関数を含み得る。
いくつかの例示的な実施形態において、ハミング符号の指定されたコード長は180であり、送信されるべき情報ビットの長さは170であり、ターゲットパリティチェック行列の第9行における全ての要素は1であり、そして、ターゲット関数h(S0,i，S1,i，S2,i)は、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、非オールゼロ行ベクトルDに対応する列ベクトルの要素S8,iを決定する。ここで、iは、0以上、かつ、180未満の整数であり、
であり、かつ、S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
いくつかの他の例示的な実施形態において、ハミング符号の指定されたコード長は128であり、そして、送信されるべき情報ビットの長さは119である。この実施形態において、ターゲットパリティチェック行列HDEの第８行における全ての要素S8,iは1であり、そして、ターゲット関数h(S0,i，S1,i，S2,i)は、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルDに対応する列ベクトルの要素S7,iを決定する。ここで、iは、0以上、かつ、128未満の整数であり、
であり、かつ、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
さらに他の実施形態において、ハミング符号の特定コード長は64であり、そして、情報ビットの長さは56である。この実施形態において、ターゲットパリティチェック行列HDEの第７行における全ての要素S7,iは1であり、そして、ターゲット関数h(S0,i，S1,i，S2,i)は、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルDに対応する列ベクトルの要素S6,iを決定する。ここで、iは、0以上、かつ、64未満の整数であり、
であり、かつ、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
いくつかの例示的な実施形態において、生成行列Gは、システムチェック行列を使用することによって決定され、そして、システムチェック行列は、例えば、本開示の実施形態において提供される前述のハミング符号生成方法において説明されるように、ターゲットパリティチェック行列HDEを変換することによって獲得される。
ターゲットパリティチェック行列HDEを決定する一つの例示的な実装において、複数の候補パリティチェック行列Hjは、複数の候補関数hjに基づいて決定され得る。非特異行列が、複数の候補パリティチェック行列Hjから選択され、第１候補パリティチェック行列セットを獲得する。次いで、第１候補パリティチェック行列セットは、系統的な形式の第２候補パリティチェック行列セットに変換される。関連する第３パラメータは、第２候補パリティチェック行列セットにおける各候補パリティチェック行列について決定され得る。例えば、第３パラメータは、ハミング符号のエンコーディング複雑性を示し得る。候補パリティチェック行列の第１グループが、第３パラメータに基づいて、第１候補パリティチェック行列セットから選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第１グループから決定され得る。
いくつかの例示的な実施形態において、ターゲットパリティチェック行列HDEが、さらに、ハミング符号の最小コード重みの量を示す第４パラメータに基づいて、候補パリティチェック行列の第１グループから決定され得る。具体的には、関連する第４パラメータが、候補パリティチェック行列の第１グループにおける各候補パリティチェック行列について決定され、そして、第４パラメータは、候補パリティチェック行列の第１グループにおける各候補パリティチェック行列に対応しているハミング符号の最小コード重みの量を示し得る。候補パリティチェック行列の第２グループは、決定された第４パラメータに基づいて、候補パリティチェック行列の第１グループから選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第２グループから決定され得る。
ターゲットパリティチェック行列HDEを決定する別の例示的な実装では、系統的な形式で第２候補パリティチェック行列セットが獲得された後で、第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第４パラメータが決定され得る。例えば、第４パラメータは、第２候補パリティチェック行列セット内の各候補パリティチェック行列に対応しているハミング符号の最小コード重みの量を示し得る。候補パリティチェック行列の第１グループは、第４パラメータに基づいて、第１候補パリティチェック行列セットから選択され得る。例えば、最小量の最小コード重みを有するハミング符号に対応している候補パリティチェック行列が、候補パリティチェック行列の第１グループとして選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第１グループから決定され得る。
いくつかの例示的な実施形態において、ターゲットパリティチェック行列HDEは、さらに、ハミング符号のエンコーディング複雑性を示す第３パラメータに基づいて、候補パリティチェック行列の第１グループから決定され得る。具体的には、関連する第３パラメータが、候補パリティチェック行列の第１グループ内の各候補パリティチェック行列について決定され得る。例えば、第３パラメータは、ハミング符号のエンコーディング複雑性を示し得る。次いで、決定された第３パラメータに基づいて、候補パリティチェック行列の第１グループから、候補パリティチェック行列の第２グループが選択され得る。例えば、候補パリティチェック行列の第２グループは、既定の閾値よりも小さい第３パラメータを有している。追加的または代替的に、最低のエンコーディング複雑性を有する候補パリティチェック行列が、候補パリティチェック行列の第２グループとして選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第２グループから決定され得る。
ターゲットパリティチェック行列HDEを決定する一つの例示的な実装では、前記候補パリティチェック行列の第２グループから、関数セットにおける候補パリティチェック行列の第２グループ内の各候補パリティチェック行列に対応している関数hjの操作量が、さらに、決定され得る。例えば、関数hjにおける演算子（operator）「negate
」（以降、「negate b－」として記載）、「and ∧」、および、「or ∨」の総数である。次いで、決定された操作量に基づいて、ターゲットパリティチェック行列HDEが決定される。例えば、最小の操作量を伴うターゲット関数hjが、ターゲット関数h(S0,i，S1,i，S2,i)として選択されてよく、そして、ターゲットパリティチェック行列HDEに対応しているパリティチェック行列HDE,jが、ターゲットパリティチェック行列HDEとして決定される。
いくつかの例示的な実施形態において、第１候補パリティチェック行列セット内の各候補パリティチェック行列について、少なくともいくつかの線形独立列ベクトルが、対応する候補パリティチェック行列の右端まで、右から左へ移動され、そして、対応する候補パリティチェック行列の右部分が単位行列（identity matrix）であるように、基本行変換が実行され、系統的な形式で第２候補パリティチェック行列セットを獲得する。
ブロック202で、エンコーディング装置110は、エンコーディングされたデータストリーム（encoded data stream）cを獲得するために、生成行列Gを使用することによって、情報ビットシーケンスをエンコーディングする。例えば、情報ビットシーケンスbについて、情報ビットシーケンスに対応するエンコーディングされたデータストリームは、c=bGである。
ブロック203において、エンコーディング装置110は、エンコーディングされたデータストリームを送信する。例えば、エンコーディング装置110は、チャネル104を介してデコーディング装置120にエンコーディングされたデータストリームを送信することができる。
本発明のこの実施形態に従って、エンコーディング方法が提供される。本方法では、従来のハミング符号に基づいて、二重拡張ハミング符号が獲得され、そして、パリティチェック行列HDEが、適切な関数hjを選択することによって生成される。従って、特定のコード空間において、エンコーディング複雑性Оj、および、デザインされた二重拡張ハミング符号の最小コード重み4の量Ajの両方が、最小である。加えて、ハミング符号の使用に係るエンコーディング複雑性を低減するために、関数の論理式において最小の操作量を有するターゲット関数（例えば、「negate b－」、「and ∧」、または、「or ∨」）が選択され得る。
図3は、本開示の一つの例示的な実施形態に従った、デコーディング方法300のフローチャートである。方法300は、図1に示されるデコーディング装置120によって実施されてよく、そして、図1に示されるチャネル104およびエンコーディング装置110を含み得る。説明を容易にするために、以下では、図1を参照して方法300を説明する。方法300は、また、他の通信シナリオおよび他のデコーディング装置にも適用可能であることが理解されるべきである。
ブロック301において、デコーディング装置120は、データストリームを受信する。例えば、デコーディング装置120は、チャネル104を介してエンコーディング装置110から、ハミング符号を使用することによりエンコーディングされたデータストリームを受信する。
ブロック302において、デコーディング装置120は、デコーディングのためのハミング符号のターゲットパリティチェック行列HDEを獲得する。いくつかの例示的な実施形態において、ターゲットパリティチェック行列HDEは、デコーディングのためのターゲット関数h(S0,i，S1,i，S2,i)に基づいて決定される。ターゲット関数h(S0,i，S1,i，S2,i)は、既定の関数セットのうちの１つであり、そして、ターゲットパリティチェック行列HDEに基づいて拡張された非オールゼロ行ベクトルDを決定するために使用される。
既定の関数セットは、ターゲットパリティチェック行列HDEに基づいて拡張された非オールゼロ行ベクトルDを決定するための複数の候補関数を含み得る。いくつかの例示的な実施形態において、ターゲット関数h(S0,i，S1,i，S2,i)は、非オールゼロ行ベクトルDに対応している列ベクトルに係る最初の3個の要素S0,i、S1,i、S2,iのうちの少なくともいくつかの要素に基づいて、非オールゼロ行ベクトルDを決定し得る。例えば、既定の関数セットは、以下のうちの１つ以上を含み得る。
別の例として、既定の関数セットは、代替的に、表1から表4までに示される関数hの一部または全部、もしくは、表1から表4までに示されていない関数を含み得る。
いくつかの例示的な実施形態において、ハミング符号の指定されたコード長は180であり、受信された情報ビットの長さは170であり、ターゲットパリティチェック行列の第9行における全ての要素は1であり、そして、ターゲット関数h(S0,i，S1,i，S2,i)は、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S8,iを決定する。ここで、iは、0以上、かつ、180未満の整数であり、
であり、かつ、S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
いくつかの他の例示的な実施形態において、ハミング符号の指定されたコード長は128であり、そして、受信された情報ビットの長さは119である。この実施形態において、ターゲットパリティチェック行列HDEの第８行における全ての要素S8,iは1であり、そして、ターゲット関数h(S0,i，S1,i，S2,i)は、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルDに対応する列ベクトルの要素S7,iを決定する。ここで、iは、0以上、かつ、128未満の整数であり、
であり、かつ、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
さらに他の実施形態において、ハミング符号の特定コード長は64であり、そして、情報ビットの長さは56である。この実施形態において、ターゲットパリティチェック行列HDEの第７行における全ての要素S7,iは1であり、そして、ターゲット関数h(S0,i，S1,i，S2,i)は、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルDに対応する列ベクトルの要素S6,iを決定する。ここで、iは、0以上、かつ、64未満の整数であり、
であり、かつ、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
いくつかの例示的な実施形態において、生成行列Gは、システムチェック行列を使用することによって決定され、そして、システムチェック行列は、例えば、本開示の実施形態において提供される前述のハミング符号生成方法において説明されるように、ターゲットパリティチェック行列HDEを変換することによって獲得される。
ターゲットパリティチェック行列HDEを決定する一つの例示的な実装において、複数の候補パリティチェック行列Hjは、複数の候補関数hjに基づいて決定され得る。非特異行列が、複数の候補パリティチェック行列Hjから選択され、第１候補パリティチェック行列セットを獲得する。次いで、第１候補パリティチェック行列セットは、系統的な形式の第２候補パリティチェック行列セットに変換される。関連する第３パラメータは、第２候補パリティチェック行列セットにおける各候補パリティチェック行列について決定され得る。例えば、第３パラメータは、ハミング符号のエンコーディング複雑性を示し得る。候補パリティチェック行列の第１グループが、第３パラメータに基づいて、第１候補パリティチェック行列セットから選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第１グループから決定され得る。
いくつかの例示的な実施形態において、ターゲットパリティチェック行列HDEが、さらに、ハミング符号の最小コード重みの量を示す第４パラメータに基づいて、候補パリティチェック行列の第１グループから決定され得る。具体的には、関連する第４パラメータが、候補パリティチェック行列の第１グループにおける各候補パリティチェック行列について決定され、そして、第４パラメータは、候補パリティチェック行列の第１グループにおける各候補パリティチェック行列に対応しているハミング符号の最小コード重みの量を示し得る。候補パリティチェック行列の第２グループは、決定された第４パラメータに基づいて、候補パリティチェック行列の第１グループから選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第２グループから決定され得る。
ターゲットパリティチェック行列HDEを決定する別の例示的な実装では、系統的な形式で第２候補パリティチェック行列セットが獲得された後で、第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第４パラメータが決定され得る。例えば、第４パラメータは、第２候補パリティチェック行列セット内の各候補パリティチェック行列に対応しているハミング符号の最小コード重みの量を示し得る。候補パリティチェック行列の第１グループは、第４パラメータに基づいて、第１候補パリティチェック行列セットから選択され得る。例えば、最小量の最小コード重みを有するハミング符号に対応している候補パリティチェック行列が、候補パリティチェック行列の第１グループとして選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第１グループから決定され得る。
いくつかの例示的な実施形態において、ターゲットパリティチェック行列HDEは、さらに、ハミング符号のエンコーディング複雑性を示す第３パラメータに基づいて、候補パリティチェック行列の第１グループから決定され得る。具体的には、関連する第３パラメータが、候補パリティチェック行列の第１グループ内の各候補パリティチェック行列について決定され得る。例えば、第３パラメータは、ハミング符号のエンコーディング複雑性を示し得る。次いで、決定された第３パラメータに基づいて、候補パリティチェック行列の第１グループから、候補パリティチェック行列の第２グループが選択され得る。例えば、候補パリティチェック行列の第２グループは、既定の閾値よりも小さい第３パラメータを有している。追加的または代替的に、最低のエンコーディング複雑性を有する候補パリティチェック行列が、候補パリティチェック行列の第２グループとして選択され得る。次いで、ターゲットパリティチェック行列HDEが、候補パリティチェック行列の第２グループから決定され得る。
ターゲットパリティチェック行列HDEを決定する一つの例示的な実装では、前記候補パリティチェック行列の第２グループから、関数セットにおける候補パリティチェック行列の第２グループ内の各候補パリティチェック行列に対応している関数hjの操作量が、さらに、決定され得る。例えば、関数hjにおける演算子「negate b－」、「and ∧」、および、「or ∨」の総数である。次いで、決定された操作量に基づいて、ターゲットパリティチェック行列HDEが決定される。例えば、最小の操作量を伴うターゲット関数hjが、ターゲット関数h(S0,i，S1,i，S2,i)として選択されてよく、そして、ターゲットパリティチェック行列HDEに対応しているパリティチェック行列HDE,jが、ターゲットパリティチェック行列HDEとして決定される。
いくつかの例示的な実施形態において、第１候補パリティチェック行列セット内の各候補パリティチェック行列について、少なくともいくつかの線形独立列ベクトルが、対応する候補パリティチェック行列の右端まで、右から左へ移動され、そして、対応する候補パリティチェック行列の右部分が単位行列（identity matrix）であるように、基本行変換が実行され、系統的な形式で第２候補パリティチェック行列セットを獲得する。
ブロック303において、デコーディング装置120は、ターゲットパリティチェック行列HDEを使用することによって、データストリームをデコーディングする。このようにして、デコーディング装置120は、送信端によって送信された元の情報ビットを獲得し得る。
いくつかの例示的な実施形態において、デコーディング装置120は、ターゲットパリティチェック行列HDEに基づいて、データについてシンドローム（syndrome）を計算することができる。シンドロームがゼロである場合、デコーディングされた情報ビットとして、データストリームの少なくともいくつかのビットが出力され得る。そうでなければ、シンドロームがゼロでない場合、ターゲットパリティチェック行列内にシンドロームに等しい第１列ベクトルが存在するか否かが判定される。ターゲットパリティチェック行列においてシンドロームに等しい第１列ベクトルが存在する場合、第１列ベクトルに対応するデータストリーム内のビットが反転され（flipped）、そして、反転後のデータストリームの少なくともいくつかのビットが、デコーディングされた情報ビットとして出力される。
本開示の一つの例示的な実施形態に従って、デコーディング方法が提供される。本方法は、従来のハミング符号に基づいて、二重拡張ハミング符号を使用している。ハミング符号のパリティチェック行列HDEは、複雑性Оj、最小コード重みの量Aj、および、関数の論理式の操作量（例えば、「negate b－」、「and ∧」、「or ∨」）基づいて、既定の関数セットから選択されたより簡潔なターゲット関数を使用することによって生成される。このようにして、デザインされた二重拡張ハミング符号を使用することによって、特定のコード空間において、同じデータストリームが送信端で生成され、そして、受信端でより低いデコーディング複雑性を実現することができ、それによって、通信システムの性能を改善し、かつ、ビット誤り率をさらに低減している。
前述の方法200および300のステップは、特定の順序で説明されているが、その順序は、限定の代わりに、単なる例示のためのものに過ぎない。明示的に述べられていない限り、そうしたプロセスは、示された特定の順序で、または、連続した順序で完了される必要があることが理解されるべきである。場合によっては、マルチタスキングまたは並列処理が有利である。加えて、方法200および300は、さらに、図示されていない追加の動作を含んでよく、かつ／あるいは、１つ以上の示された動作が省略され得る。
以下は、本開示のいくつかの例示的な実施形態を説明している。
第1実施形態
本開示の第１実施形態において、改良されたハミング符号(DE-Hamming)(180、170)が提供される。コード長は180であり、送信されるべき情報ビットの長さは170である。本発明に従ったハミング符号(DE-Hamming)は、従来のハミング符号(DE-Hamming)に基づいて獲得され得るものであり、そして、二重拡張（double extension）、すなわち、m=8かつq=76、を実行している。デコーディングは、有限体（finite field）GF(28)に基づいて実行されると考えられ得る。本開示に従ったハミング符号(DE-Hamming)のターゲットパリティチェック行列HDEは、式(2)の形式である。
この実施形態において、短縮ハミング符号(179,171)のパリティチェック行列Hのサイズは、8×179であり、1は長さが180のオールワン行ベクトルであり、0は長さが1であるオールゼロ列ベクトルであり、そして、ターゲットパリティチェック行列HDEの非オールゼロ行ベクトルDの長さは、18である。式(3)に従って、以下が獲得される。
ここで、iは、0以上、かつ、180未満の整数であり、
であり、かつ、ターゲットパリティチェック行列HDEの第９行における要素は、全て1である。本開示に従ったハミング符号(DE-Hamming)のターゲット関数h(S0,i，S1,i，S2,i)は、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S8,iを決定し、かつ、S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
式(6)、および、表1から表4までに従って、10×180のサイズを有する以下の候補パリティチェック行列Hjが決定され得る。ここで、0＜j≦162である。
得られる。
非特異行列が、複数の候補パリティチェック行列Hjから選択され、第１候補パリティチェック行列セットを獲得する。さらに、第１候補パリティチェック行列セットは、式(7)に従って、系統的な形式の第２候補パリティチェック行列セットに変換される。具体的には、本実施形態において、10個の線形独立列ベクトルが、右から左へ、候補パリティチェック行列Hjから選択され、そして、行列の右端に移動される。ここにおいて、HRは、10個の線形独立な列ベクトルによって形成された10×10行列であり、そして、HLは、候補パリティチェック行列HjからHRが除去された後で獲得される10×170行列である。
さらに、式(8)に従って、システムチェック行列Hsys,jが、基本行変換を通じて獲得され得る。ここにおいて、Iは、10×10の単位行列であり、そして、行列P=(HR)-1HLは、10×170のサイズを有している。
170×180のサイズを有する生成行列Gjが、式(9)に従って決定され得る。
表1から表4までに示される162個の関数hjについて、対応する候補パリティチェック行列Hjが、式(4)および式(5)に従って、それぞれに獲得される。162個の候補パリティチェック行列Hjのうち14個の行列が非特異行列ではないことが、決定され得る。148個の非特異行列Hjについて、8個の線形独立列ベクトルが右から左に選択され、そして、式(7)に従った変換を通じて、行列の右端に移動されて、候補パリティチェック行列HDE,jの第１グループを獲得する。
候補パリティチェック行列HDE,jの第１グループから、エンコーディング複雑性を示す第３パラメータОj、および、最小コード重み4の量を示す第４パラメータAjに基づいて、ターゲットパリティチェック行列HDEが選択され、そして、ターゲット関数h(S0,i，S1,i，S2,i)が選択され得る。表5は、この実施形態について候補関数hj、および、候補関数に対応する操作量
（以降、「Ηj」として記載）の論理式を示している。
表5から、第１実施形態に従って、ハミング符号のエンコーディング複雑性は、Оj=706であり、かつ、最小コード重み4の量は、Aj=107660であることが決定され得る。
さらに、より複雑性の低い関数が、表5に示される操作量Ηjに基づいて、12個の候補関数hから選択され得る。この実施形態において、h33=S0,i∧S1,iの関数の複雑性は、Η33=1であり、かつ、12個の候補関数hの中で最も低く、そして、この関数に対応する短縮二重拡張ハミング符号の複雑性は、より低い。
図4は、本開示の一つの例示的な実施形態に従った、二重拡張ハミング符号(180、170)、および、従来の拡張ハミング符号(180、170)の性能のダイアグラムである。ここびおいて、二重拡張ハミング符号(DE-Hamming)(180、170)は、最大事後復号(maximum a posteriori decoding、MAP)を使用する。この例において、従来の拡張ハミング符号(eHamming)(180,170)は、332ビットだけ短縮され、そして、従来のハミング符号(Hamming)(511,502)に基づいて、単一ビット拡張を実施する。従来の拡張ハミング符号に対するデコーディングは、有限体GF(29)に基づいて実施されるものと考えられ得る。図4に示されるように、本開示に従ったハミング符号(DE-Hamming)（180,170）は、従来の拡張ハミング符号(eHamming)（180,170）よりも良好な性能を有している。加えて、本開示に従った二重拡張ハミング符号(DE-Hamming)（180,170）の硬判定デコーディング（hard-decision decoding）は、有限体GF(28)に基づいており、一方で、従来の拡張ハミング符号(eHamming)の硬判定デコーディングは、有限体GF(29)に基づいている。従って、本開示で提供される二重拡張ハミング符号(DE-Hamming)（180,170）のデコーディング複雑性は、従来の拡張ハミング符号(180,170)のものよりも低い。
従来の拡張ハミング符号(180,170)は、式(12)に示される関数を使用する。
従来の拡張ハミング符号(180,170)のエンコーディング複雑性は、748であり、かつ、最小コード重み4の量は、107749である。本開示で提供される二重拡張ハミング符号(DE-Hamming)(180,170)のエンコーディング複雑性は、706であり、かつ、最小コード重み4の量は、107660であり、これらは、両方とも、従来の拡張ハミング符号(180,170)よりも良好である。加えて、第１実施の形態では、ターゲット関数の関数論理式S8,i=h33=S0,i∧S1,iは、式(12)よりも簡単である。従って、本開示で提供される二重拡張ハミング符号(DE-Hamming)の機能複雑性も、また、より低い。
第2実施形態
本開示の第２実施形態において、改良されたハミング符号(DE-Hamming)(128,119)が提供される。コード長は128であり、送信されるべき情報ビットの長さは119、m=7、かつq=0である。本発明に従ったハミング符号(DE-Hamming)(128,119)は、従来のハミング符号(DE-Hamming)(127,120)に基づいて、二重拡張を実行することにより獲得され得るものであり、すなわち、m=7、かつq=0、を実行している。デコーディングは、有限体GF(27)に基づいて実行されると考えられ得る。本開示に従ったハミング符号(DE-Hamming)(128,119)のターゲットパリティチェック行列HDEは、式(2)の形式である。
この実施形態において、従来のハミング符号(127,120)のパリティチェック行列Hのサイズは、8×179であり、1は長さが128のオールワン行ベクトルであり、0は長さが7であるオールゼロ列ベクトルであり、そして、ターゲットパリティチェック行列HDEの非オールゼロ行ベクトルDの長さは、128である。式(3)に従って、以下が獲得される。
ここで、iは、0以上、かつ、180未満の整数であり、
であり、かつ、ターゲットパリティチェック行列HDEの第８行における要素は、全て1である。本開示に従ったハミング符号(DE-Hamming)のターゲット関数h(S0,i，S1,i，S2,i)は、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S7,iを決定し、かつ、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
式(5)、および、表1から表4までに従って、9×128のサイズを有する以下の候補パリティチェック行列Hjが決定され得る。ここで、0＜j≦162である。
得られる。
非特異行列が、複数の候補パリティチェック行列Hjから選択され、第１候補パリティチェック行列セットを獲得する。さらに、第１候補パリティチェック行列セットは、式(7)に従って、系統的な形式の第２候補パリティチェック行列セットに変換される。具体的には、本実施形態において、9個の線形独立列ベクトルが、右から左へ、候補パリティチェック行列Hjから選択され、そして、行列の右端に移動される。ここにおいて、HRは、9個の線形独立な列ベクトルによって形成された9×9行列であり、そして、HLは、候補パリティチェック行列HjからHRが除去された後で獲得される9×128行列である。
さらに、式(8)に従って、システムチェック行列Hsys,jが、基本行変換を通じて獲得され得る。ここにおいて、Iは、9×9の単位行列であり、そして、行列P=(HR)-1HLは、9×119のサイズを有している。
119×128のサイズを有する生成行列Gjが、式(9)に従って決定され得る。
候補パリティチェック行列HDE,jの第１グループに対して、表1から表4までに示される162個の関数hjについて、対応する候補パリティチェック行列Hjが、式(4)および式(5)に従って、それぞれに獲得される。162個の候補パリティチェック行列Hjのうち14個の行列が非特異行列ではないことが、決定され得る。148個の非特異行列Hjについて、9個の線形独立列ベクトルが右から左に選択され、そして、式(7)に従った変換を通じて、行列の右端に移動されて、候補パリティチェック行列HDE,jの第１グループを獲得する。
エンコーディング複雑性を示す第３パラメータОj、および、最小コード重み4の量を示す第４パラメータAjに基づいて、ターゲットパリティチェック行列HDEが選択され、そして、ターゲット関数h(S0,i，S1,i，S2,i)が選択され得る。表6は、この実施形態について候補関数hj、および、候補関数に対応する操作量Ηjの論理式を示している。

表6から、第２実施形態に従って、ハミング符号のエンコーディング複雑性は、Оj=471であり、かつ、最小コード重み4の量は、Aj=52576であることが決定され得る。
さらに、より複雑性の低い関数が、表６に示される操作量Ηjに基づいて、36個の候補関数hから選択され得る。この実施形態において、S7,i=h33=S0,i∧S1,i、S7,i=h35=S0,i∧S2,i、および、S7,i=h36=S1,i∧S2,iの関数の複雑性は、1である。3個の関数は、36個の候補関数hの中で最も低く、そして、3個の関数に対応する短縮二重拡張ハミング符号の複雑性は、より低い。
特に、S7,i=h36=S1,i∧S2,iの場合は、式(5)に従って、以下のように決定され得る。
ここにおいて、g(a):g(b)は、[g(a),g(a+1),g(a+2),…,g(b)]を示している。
生成行列Gは、式(9)および式(16)に従って決定され得る。
ここにおいて、
である。
本開示の第２実施形態においては、この実施形態におけるハミング符号の対応するパリティチェック行列HDE,36は、OIF-400ZR規格で定義されているハミング符号(DE-Hamming)(128,119)OIFとは異なる。しかし、本実施形態における系統的なパリティチェック行列HDE,36、および、ハミング符号の生成行列Gjの両方は、OIF-400ZR規格で定義されているハミング符号(DE-Hamming)(128,119)OIFのものと同じである。別の言葉で言えば、2個の二重拡張ハミング符号(128,119)および(128,119)OIFに基づくエンコーディングを通じて、同じコードワード（codewords）が獲得される。別の言葉で言えば、送信端から出力されるデータストリームは一貫している。本開示に従った二重拡張ハミング符号(DE-Hamming)は、受信端において、より低い関数複雑性S7,i=h36=S1,i∧S2,iを有している。
第３実施例
本開示の第３実施形態において、改良されたハミング符号(DE-Hamming)(64,56)が提供される。コード長は64であり、送信されるべき情報ビットの長さは56である。ハミング符号(DE-Hamming)(64,56)は、従来のハミング符号(DE-Hamming)(63,57)に基づいて、二重拡張を実行することにより獲得され得るものであり、すなわち、m=6、かつq=0である。デコーディングは、有限体GF(26)に基づいて実行されると考えられ得る。本開示に従ったハミング符号(DE-Hamming)のターゲットパリティチェック行列HDEは、式(2)の形式である。
この実施形態において、従来のハミング符号(63,57)のパリティチェック行列Hのサイズは、6×63であり、1は長さが64のオールワン行ベクトルであり、0は長さが6であるオールゼロ列ベクトルであり、そして、ターゲットパリティチェック行列HDEの非オールゼロ行ベクトルDの長さは、64である。式(3)に従って、以下が獲得される。
ここで、iは、0以上、かつ、64未満の整数であり、
であり、かつ、ターゲットパリティチェック行列HDEの第７行における要素は、全て1である。本開示に従ったハミング符号(DE-Hamming)のターゲット関数h(S0,i，S1,i，S2,i)は、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S6,iを決定し、かつ、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である。
式(5)、および、表1から表4までに従って、8×64のサイズを有する以下の候補パリティチェック行列Hjが決定され得る。ここで、0＜j≦162である。
得られる。
非特異行列が、複数の候補パリティチェック行列Hjから選択され、第１候補パリティチェック行列セットを獲得する。さらに、第１候補パリティチェック行列セットは、式(7)に従って、系統的な形式の第２候補パリティチェック行列セットに変換される。具体的には、本実施形態において、8個の線形独立列ベクトルが、右から左へ、候補パリティチェック行列Hjから選択され、そして、行列の右端に移動される。ここにおいて、HRは、8個の線形独立な列ベクトルによって形成された8×8行列であり、そして、HLは、候補パリティチェック行列HjからHRが除去された後で獲得される8×56行列である。
さらに、式(7)に従って、システムチェック行列Hsys,jが、基本行変換を通じて獲得され得る。ここにおいて、Iは、8×8の単位行列であり、そして、行列P=(HR)-1HLは、8×56のサイズを有している。
56×64のサイズを有する生成行列Gjが、式(9)に従って決定され得る。
表1から表4までに示される162個の関数hjについて、対応する候補パリティチェック行列Hjが、式(4)および式(5)に従って、それぞれに獲得される。162個の候補パリティチェック行列Hjのうち14個の行列が非特異行列ではないことが、決定され得る。148個の非特異行列Hjについて、8個の線形独立列ベクトルが右から左に選択され、そして、式(7)に従った変換を通じて、行列の右端に移動されて、候補パリティチェック行列HDE,jの第１グループを獲得する。
候補パリティチェック行列HDE,jの第１グループに対して、エンコーディング複雑性を示す第３パラメータОj、および、最小コード重み4の量を示す第４パラメータAjに基づいて、ターゲットパリティチェック行列HDEが選択され、そして、ターゲット関数h(S0,i，S1,i，S2,i)が選択され得る。表7は、この実施形態について候補関数hj、および、候補関数に対応する操作量Ηjの論理式を示している。


表7から、第３実施形態に従って、ハミング符号のエンコーディング複雑性は、Оj=200であり、かつ、最小コード重み4の量は、Aj=6320であることが決定され得る。
さらに、より複雑性の低い関数が、表７に示される操作量Ηjに基づいて、36個の候補関数hから選択され得る。この実施形態において、S6,i=h33=S0,i∧S1,i、S6,i=h35=S0,i∧S2,i、および、S6,i=h36=S1,i∧S2,iの関数の複雑性は、1である。3個の関数は、36個の候補関数hの中で最も低く、そして、3個の関数に対応する短縮二重拡張ハミング符号の複雑性は、より低い。
第４実施形態
本開示の第４実施形態において、短縮二重拡張ハミング符号(DE-Hamming)（2m-q,2m-2-m-q）が提供される。ここで、mは所与のものである。式(19)に示されるように、長さqの短縮ビットが選択され、異なる符号冗長度（code redundancy）OHを実装する。ここで、0≦q＜（2m-1）/2である。
コード長は、n=2m-qであり、そして、情報長は、k=2m-2-m-qである。
表８および表９においては、本開示で提供される短縮二重拡張ハミング符号のためのターゲット関数hjが、m=8かつ異なるqs、および、m=7かつ異なるqsの場合について列挙されている。




本発明の第４実施形態に従って、改良された二重拡張ハミング符号が提供される。改良された二重拡張ハミング符号のターゲットパリティチェック行列は、既定の関数セットから選択されたより少ない操作量を有するターゲット関数に基づいて獲得され、その結果、そうした拡張ハミング符号は、様々なコード長および情報ビット長の構成に適応することができる。本開示に従った二重拡張ハミング符号は、指定されたコード空間において低いエンコーディングおよびデコーディング複雑性を提供し、通信システムのビット誤り率を低減し、かつ、適切な範囲内に冗長性を維持し、それによって、最適化されたハミング符号性能を提供することができる。
図5は、本開示のいくつかの実施形態を実装することができるデバイス500のブロック図である。デバイス500は、図1に示されるエンコーディング装置110およびデコーディング装置120を実装するために使用され得る。デバイス500は、単に例として使用されているだけであり、本開示の範囲について、いかなる限定も暗示するものではないことが理解されるべきである。本開示の実施形態は、さらに、異なる装置において具現化され得る。デバイス500は、説明を容易にするために示されていない他の要素またはエンティティをさらに含み得るが、それは、本開示の実施形態がこれらの要素またはエンティティを有しないことを意味するものではないことが、さらに理解されるべきである。
図5に示されるように、デバイス500は、プロセッサ510を含んでいる。プロセッサ510は、デバイス500の動作および機能を制御する。例えば、いくつかの例示的な実施形態において、プロセッサ510は、プロセッサ510に結合されたメモリ520に保管された命令530を使用することによって、様々な動作を実行し得る。メモリ520は、ローカルな技術環境に適用可能な任意の適切なタイプのものであってよく、そして、任意の適切なデータ記憶技術を使用することによって実装され得る。これらに限定されるわけではないが、半導体ベースの記憶デバイス、磁気記憶デバイスおよびシステム、並びに、光記憶デバイスおよびシステム、を含むものである。図5には１つのメモリユニットのみが示されているが、デバイス500内には複数の物理的に異なるメモリユニットが存在してよい。
プロセッサ510は、ローカルな技術環境に適用できる任意の適切なタイプのものであってよく、そして、これらに限定されるわけではないが、汎用コンピュータ、専用コンピュータ、マイクロコントローラ、デジタル信号プロセッサ(DSP)、およびコントローラベースのマルチコアコントローラアーキテクチャのうちの１つ以上を含み得る。デバイス500は、また、複数のプロセッサ510を含み得る。プロセッサ510は、通信ユニット540に結合されている。通信ユニット540は、無線信号を使用することによって、または、光ファイバ、ケーブル、及び／又は、別の構成要素を通して、情報を受信および送信することができる。
デバイス500がエンコーディング装置110またはデコーディング装置120として働くときに、プロセッサ510は、命令を実行することによって、図2および図3を参照して上記で説明した動作およびアクションを実施することができる。図2および図3を参照して上記で説明した全ての特徴は、デバイス500に適用可能である。詳細は、ここにおいて、再び説明されない。
一般的に、本開示の様々な例示的な実施形態は、ハードウェアまたは専用回路、ソフトウェア、論理、または、それらの任意の組合せで実装され得る。いくつかの態様は、ハードウェアで実装され得る。他の態様は、コントローラ、マイクロプロセッサ、または、別のコンピューティングデバイスによって実行することができるファームウェアまたはソフトウェアで実装され得る。本開示の例示的な実施形態の態様が、ブロック図、フローチャートとして示され、または、説明され、もしくは、いくつかの他のグラフを使用して表されるとき、本明細書で説明されるブロック、装置、システム、技法、または方法は、ハードウェア、ソフトウェア、ファームウェア、専用回路または論理、汎用ハードウェアまたはコントローラ、別のコンピューティングデバイス、もしくは、それらのいくつかの組合せにおける、非限定的な例として実装され得ることが理解されるだろう。
例えば、本開示の例示的な実施形態は、機械実行可能命令またはコンピュータ実行可能命令のコンテキストにおいて説明され得る。機械実行可能命令は、例えば、ターゲットの実プロセッサまたは仮想プロセッサにおいてデバイス内で実行されるプログラムモジュールに含まれている。一般的に、プログラムモジュールは、ルーチン、プログラム、ライブラリ、オブジェクト、タイプ、コンポーネント、データ構造、などを含み、そして、特定のタスクを実行するか、または、特定の抽象データ構造を実装する。様々な例示的な実施形態において、プログラムモジュールの機能は、説明されたプログラムモジュール間で組み合わされてよく、または、分割されてもよい。プログラムモジュールに使用される機械実行可能命令は、ローカルに、または、分散デバイスにおいて実行され得る。分散デバイスにおいて、プログラムモジュールは、ローカルストレージ媒体およびリモートストレージ媒体の両方に配置され得る。
本開示で開示される方法を実装するために使用されるコンピュータプログラムコードは、１つ以上のプログラミング言語で書かれ得る。コンピュータプログラムコードは、汎用コンピュータ、専用コンピュータ、または、別のプログラマブルデータ処理装置のプロセッサに対して提供され得る。このようにして、プログラムコードがコンピュータまたは別のプログラマブルデータ処理装置によって実行されると、フローチャート及び／又はブロック図に指定された機能/動作が実施される。プログラムコードは、完全にコンピュータ上で、部分的にコンピュータ上で、独立したソフトウェアパッケージとして、部分的にコンピュータ上で、部分的にリモートコンピュータ上で、もしくは、全てリモートコンピュータまたはサーバ上で実行されてよい。
本開示のコンテキストにおいて、機械可読媒体またはコンピュータ可読媒体は、命令実行システム、装置、またはデバイスのために使用され、または、関連するプログラムを含み、もしくは、保管する、任意の有形媒体であり得る。機械可読媒体は、機械可読信号媒体または機械可読記憶媒体であり得る。機械可読媒体は、これらに限定されるわけではないが、電子、磁気、光学、電磁気、赤外線、または半導体システム、装置、またはデバイス、もしくは、それらの任意の適切な組合せを含み得る。機械可読記憶媒体のより詳細な例は、１つ以上の導線との電気接続、ポータブルコンピュータディスク、ハードディスク、ランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、消去可能プログラマブル読取り専用メモリ(EPROMまたはフラッシュメモリ)、光記憶デバイス、磁気記憶デバイス、または、それらの任意の適切な組合せを含む。
加えて、特定の順序で動作が説明されているが、これは、そうした動作が、示される特定の順序で、または、連続した順序で完了されることを必要とするものとして、もしくは、所望の結果を得るために全ての図示される動作を実行するものとして理解されるべきではない。場合によっては、マルチタスキングまたは並列処理が有利である。同様に、上記の説明は、いくつかの特定の実装の詳細を含んでいるが、これは、任意の発明または特許請求の範囲を限定するものと解釈されるべきではなく、むしろ、特定の発明について特有であり得る特定の例示的な実施形態の説明として解釈されるべきである。別個の例示的な実施形態のコンテキストにおいて本明細書で説明されたいくつかの特徴は、代替的に、単一の例示的な実施形態へと統合され得る。あるいは、単一の例示的な実施形態のコンテキストで説明される様々な特徴は、複数の例示的な実施形態において、または、任意の適切なサブコンビネーションにおいて、別々に実装され得る。
技術的事項（subject matter）は、構造的特徴、及び／又は、方法論的アクションに特有の言語で説明されてきたが、添付の特許請求の範囲において定義される技術的事項は、上記で説明された特定の特徴またはアクションに限定されるものではないことが理解されるべきである。逆に、上述の特定の特徴および動作は、特許請求の範囲を実施する例示的な形態として開示されている。

Claims (17)

  1. エンコーディング方法であって、
    エンコーディングのための生成行列を獲得するステップであり、
    前記生成行列は、エンコーディングのためのハミング符号のターゲットパリティチェック行列に基づいて決定され、
    前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、
    前記ターゲット関数は、非オールゼロ行ベクトルを決定するために使用され、かつ、
    前記ターゲット関数は、既定の関数セットのうちの１つである、
    ステップと、
    前記生成行列を使用することによって情報ビットをエンコーディングするステップであり、
    エンコーディングされたデータストリームを獲得する、
    ステップと、
    前記エンコーディングされたデータストリームを送信するステップと、
    を含み、
    前記ハミング符号のコード長は180であり、
    前記情報ビットの長さは170であり、
    前記ターゲットパリティチェック行列の第10行における全ての要素は1であり、かつ、
    前記ターゲット関数は、関数h(S0,i，S1,i，S2,i)であり、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S8,iを決定し、
    ここで、iは、0以上、かつ、180未満の整数であり、

    であり、かつ、
    S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である、
    方法。
  2. エンコーディング方法であって、
    エンコーディングのための生成行列を獲得するステップであり、
    前記生成行列は、エンコーディングのためのハミング符号のターゲットパリティチェック行列に基づいて決定され、
    前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、
    前記ターゲット関数は、非オールゼロ行ベクトルを決定するために使用され、かつ、
    前記ターゲット関数は、既定の関数セットのうちの１つである、
    ステップと、
    前記生成行列を使用することによって情報ビットをエンコーディングするステップであり、
    エンコーディングされたデータストリームを獲得する、
    ステップと、
    前記エンコーディングされたデータストリームを送信するステップと、
    を含み、
    前記ハミング符号のコード長は128であり、
    前記情報ビットの長さは119であり、
    前記ターゲットパリティチェック行列の第８行における全ての要素は1であり、かつ、
    前記ターゲット関数は、関数h(S0,i，S1,i，S2,i)であり、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S7,iを決定し、
    ここで、iは、0以上、かつ、128未満の整数であり、

    であり、かつ、
    S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である、
    方法。
  3. エンコーディング方法であって、
    エンコーディングのための生成行列を獲得するステップであり、
    前記生成行列は、エンコーディングのためのハミング符号のターゲットパリティチェック行列に基づいて決定され、
    前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、
    前記ターゲット関数は、非オールゼロ行ベクトルを決定するために使用され、かつ、
    前記ターゲット関数は、既定の関数セットのうちの１つである、
    ステップと、
    前記生成行列を使用することによって情報ビットをエンコーディングするステップであり、
    エンコーディングされたデータストリームを獲得する、
    ステップと、
    前記エンコーディングされたデータストリームを送信するステップと、
    を含み、
    前記ハミング符号のコード長は64であり、
    前記情報ビットの長さは56であり、
    前記ターゲットパリティチェック行列の第７行における全ての要素は1であり、かつ、
    前記ターゲット関数は、関数h(S0,i，S1,i，S2,i)であり、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S6,iを決定し、
    ここで、iは、0以上、かつ、64未満の整数であり、

    であり、かつ、
    S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である、
    方法。
  4. 前記生成行列は、システムチェック行列に基づいて決定され、かつ、
    前記システムチェック行列は、前記ターゲットパリティチェック行列を変換することによって獲得される、
    請求項１乃至３いずれか一項に記載の方法。
  5. 前記既定の関数セットは、前記ターゲットパリティチェック行列に基づいて拡張された前記非オールゼロ行ベクトルを決定するための複数の候補関数を含む、
    請求項１乃至３いずれか一項に記載の方法。
  6. 前記ターゲットパリティチェック行列は、
    前記複数の候補関数に基づいて、複数の候補パリティチェック行列を決定するステップと、
    前記複数の候補パリティチェック行列から非特異行列を選択するステップであり、
    第１候補パリティチェック行列セットを獲得する、
    ステップと、
    前記第１候補パリティチェック行列セットを、系統的な形式の第２候補パリティチェック行列セットへと変換するステップと、
    前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第３パラメータを決定するステップであり、
    前記第３パラメータは、前記ハミング符号のエンコーディング複雑性を示す、
    ステップと、
    前記第３パラメータに基づいて、前記第１候補パリティチェック行列セットから、候補パリティチェック行列の第１グループを選択するステップと、
    前記候補パリティチェック行列の第１グループから、前記ターゲットパリティチェック行列を決定するステップと、
    により、決定される、
    請求項５に記載の方法。
  7. 前記ターゲットパリティチェック行列は、
    前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に関連付けられた第４パラメータを決定するステップであり、
    前記第４パラメータは、前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に対応する前記ハミング符号の最小コード重みの量を示す、
    ステップと、
    前記第４パラメータに基づいて、前記候補パリティチェック行列の第１グループから候補パリティチェック行列の第２グループを選択するステップと
    前記候補パリティチェック行列の第２グループから、前記ターゲットパリティチェック行列を決定するステップと、
    により、前記候補パリティチェック行列の第１グループから決定される、
    請求項６に記載の方法。
  8. 前記ターゲットパリティチェック行列は、
    前記複数の候補関数に基づいて、複数の候補パリティチェック行列を決定するステップと、
    前記複数の候補パリティチェック行列から非特異行列を選択するステップであり、
    第１候補パリティチェック行列セットを獲得する、
    ステップと、
    前記第１候補パリティチェック行列セットを、系統的な形式の第２候補パリティチェック行列セットへと変換するステップと、
    前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に関連付けられた第４パラメータを決定するステップであり、
    前記第４パラメータは、前記第２候補パリティチェック行列セット内の各候補パリティチェック行列に対応する前記ハミング符号の最小コード重みの量を示す、
    ステップと、
    前記第４パラメータに基づいて、前記第１候補パリティチェック行列セットから、候補パリティチェック行列の第１グループを選択するステップと、
    前記候補パリティチェック行列の第１グループから、前記ターゲットパリティチェック行列を決定するステップと、
    により、決定される、
    請求項５に記載の方法。
  9. 前記ターゲットパリティチェック行列は、
    前記候補パリティチェック行列の第１グループ内の各候補パリティチェック行列に関連付けられた第３パラメータを決定するステップであり、
    前記第３パラメータは、前記ハミング符号のエンコーディング複雑性を示す、
    ステップと、
    前記候補パリティチェック行列の第１グループから、候補パリティチェック行列の第２グループを選択するステップであり、
    前記候補パリティチェック行列の第２グループは、既定の閾値未満の前記第３パラメータを有する、
    ステップと、
    前記候補パリティチェック行列の第２グループから、前記ターゲットパリティチェック行列を決定するステップと、
    により、前記候補パリティチェック行列の第１グループから決定される、
    請求項８に記載の方法。
  10. 前記系統的な形式の第２候補パリティチェック行列セットは、
    前記第１候補パリティチェック行列セット内の各候補パリティチェック行列について、
    少なくともいくつかの線形独立列ベクトルを、対応する候補パリティチェック行列の右端まで、右から左へ移動するステップと、
    前記対応する候補パリティチェック行列の右部分が単位行列であるように、基本行変換を実行するステップと、
    による、変換を通じて獲得される、
    請求項６または８に記載の方法。
  11. 前記ターゲットパリティチェック行列は、
    前記関数セットにおける前記候補パリティチェック行列の第２グループ内の各候補パリティチェック行列に対応する関数の操作量を決定するステップと、
    前記操作量に基づいて、前記ターゲットパリティチェック行列を決定するステップと、
    により、前記候補パリティチェック行列の第２グループから決定される、
    請求項７または９に記載の方法。
  12. デコーディング方法であって
    データストリームを受信するステップと、
    デコーディングのためにハミング符号のターゲットパリティチェック行列を獲得するステップであり、
    前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、
    前記ターゲット関数は、非オールゼロ行ベクトルを決定するために使用され、かつ、
    前記ターゲット関数は、既定の関数セットのうちの１つである、
    ステップと、
    前記ターゲットパリティチェック行列を使用することにより、前記データストリームをデコーディングするステップと、
    を含み、
    前記ハミング符号のコード長は180であり、
    情報ビットの長さは170であり、
    前記ターゲットパリティチェック行列の第10行における全ての要素は1であり、かつ、
    前記ターゲット関数は、関数h(S0,i，S1,i，S2,i)であり、S8,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,iとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S8,iを決定し、

    であり、ここで、iは、0以上、かつ、180未満の整数であり、
    S8,i、S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である、
    方法。
  13. デコーディング方法であって
    データストリームを受信するステップと、
    デコーディングのためにハミング符号のターゲットパリティチェック行列を獲得するステップであり、
    前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、
    前記ターゲット関数は、非オールゼロ行ベクトルを決定するために使用され、かつ、
    前記ターゲット関数は、既定の関数セットのうちの１つである、
    ステップと、
    前記ターゲットパリティチェック行列を使用することにより、前記データストリームをデコーディングするステップと、
    を含み、
    前記ハミング符号のコード長は128であり、
    情報ビットの長さは119であり、
    前記ターゲットパリティチェック行列の第８行における全ての要素は1であり、かつ、
    前記ターゲット関数は、関数h(S0,i，S1,i，S2,i)であり、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S7,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S7,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、前記非オールゼロ行ベクトルに対応する列ベクトルの要素S7,iを決定し、
    ここで、iは、0以上、かつ、128未満の整数であり、

    であり、かつ、
    S7,i、S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である、
    方法。
  14. デコーディング方法であって
    データストリームを受信するステップと、
    デコーディングのためにハミング符号のターゲットパリティチェック行列を獲得するステップであり、
    前記ターゲットパリティチェック行列は、デコーディングのためのターゲット関数に基づいて決定され、
    前記ターゲット関数は、非オールゼロ行ベクトルを決定するために使用され、かつ、
    前記ターゲット関数は、既定の関数セットのうちの１つである、
    ステップと、
    前記ターゲットパリティチェック行列を使用することにより、前記データストリームをデコーディングするステップと、
    を含み、
    前記ハミング符号のコード長は64であり、
    情報ビットの長さは56であり、
    前記ターゲットパリティチェック行列の第７行における全ての要素は1であり、かつ、
    前記ターゲット関数は、関数h(S0,i，S1,i，S2,i)であり、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S1,i、S6,i=h(S0,i，S1,i，S2,i)=S0,i∧S2,i、および、S6,i=h(S0,i，S1,i，S2,i)=S1,i∧S2,iのうちの１つとして、非オールゼロ行ベクトルに対応する列ベクトルの要素S6,iを決定し、
    ここで、iは、0以上、かつ、64未満の整数であり、

    であり、かつ、
    S6,i、S5,i、S4,i、S3,i、S2,i、S1,i、およびS0,iは、それぞれに、前記ターゲットパリティチェック行列の行ベクトルに対応している列ベクトルの要素である、
    方法。
  15. エンコーディング装置であって
    少なくとも１つのプロセッサと、
    データを含む、少なくとも１つのメモリと、
    を含み、
    前記少なくとも１つのプロセッサは、請求項１乃至１１いずれか一項に記載の方法を実行するように構成されている、
    エンコーディング装置。
  16. デコーディング装置であって、
    少なくとも１つのプロセッサと、
    データを含む、少なくとも１つのメモリと、
    を含み、
    前記少なくとも１つのプロセッサは、請求項１２乃至１４いずれか一項に記載の方法を実行するように構成されている、
    デコーディング装置。
  17. 通信システムであって
    請求項１５に記載のエンコーディング装置と、
    請求項１６に記載のデコーディング装置と、
    を含む、システム。
JP2023557239A 2021-03-18 2022-03-15 エンコーディングおよびデコーディング方法、およびデバイス、並びにシステム Active JP7746401B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
CN202110293130.9 2021-03-18
CN202110293130.9A CN115118287A (zh) 2021-03-18 2021-03-18 用于编解码的方法、设备和系统
PCT/CN2022/081021 WO2022194170A1 (zh) 2021-03-18 2022-03-15 用于编解码的方法、设备和系统

Publications (2)

Publication Number Publication Date
JP2024511046A JP2024511046A (ja) 2024-03-12
JP7746401B2 true JP7746401B2 (ja) 2025-09-30

Family

ID=83321722

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2023557239A Active JP7746401B2 (ja) 2021-03-18 2022-03-15 エンコーディングおよびデコーディング方法、およびデバイス、並びにシステム

Country Status (5)

Country Link
US (1) US12500607B2 (ja)
EP (1) EP4322411B1 (ja)
JP (1) JP7746401B2 (ja)
CN (1) CN115118287A (ja)
WO (1) WO2022194170A1 (ja)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2016187099A (ja) 2015-03-27 2016-10-27 ルネサスエレクトロニクス株式会社 データ処理回路

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2006068435A2 (en) * 2004-12-22 2006-06-29 Lg Electronics Inc. Apparatus and method for decoding using channel code
DE102005022107B9 (de) * 2005-05-12 2016-04-07 Infineon Technologies Ag Vorrichtung und Verfahren zum Bestimmen einer Position eines Bitfehlers in einer Bitfolge
KR101147768B1 (ko) * 2005-12-27 2012-05-25 엘지전자 주식회사 채널 코드를 이용한 복호화 방법 및 장치
JP5509165B2 (ja) * 2011-08-24 2014-06-04 株式会社東芝 誤り訂正符号化装置、誤り訂正復号装置、不揮発性半導体記憶システム及びパリティ検査行列生成方法
US8694872B2 (en) * 2011-11-28 2014-04-08 Texas Instruments Incorporated Extended bidirectional hamming code for double-error correction and triple-error detection
US8745472B2 (en) * 2012-09-01 2014-06-03 Texas Instruments Incorporated Memory with segmented error correction codes
DE102013109315B4 (de) * 2013-08-28 2016-08-04 Infineon Technologies Ag Verfahren und Datenverarbeitungseinrichtung zum Rekonstruieren eines Vektors
CN111279618B (zh) * 2017-07-10 2022-05-10 华为技术有限公司 通用低密度奇偶校验码
US10725841B1 (en) * 2017-12-18 2020-07-28 Xilinx, Inc. Method and apparatus for error detection and correction
EP3735746A1 (en) * 2018-01-23 2020-11-11 Huawei Technologies Co., Ltd. Channel code construction for decoder reuse
KR102714845B1 (ko) * 2019-06-04 2024-10-10 에스케이하이닉스 주식회사 오류 정정 디코더 및 이를 포함하는 메모리 시스템
WO2021106432A1 (ja) * 2019-11-29 2021-06-03 ソニーグループ株式会社 変換方法、変換装置、受信装置及び送信装置

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2016187099A (ja) 2015-03-27 2016-10-27 ルネサスエレクトロニクス株式会社 データ処理回路

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
G.709.3/Y.1331.3 (2018) Amendment 1 (11/18)Flexible OTN long-reach interfaces Amendment 1，ＩＴＵ－Ｔ規格文書（Ｙシリーズ） G.709.3/Y.1331.3 Amendment 1，2019年

Also Published As

Publication number Publication date
JP2024511046A (ja) 2024-03-12
CN115118287A (zh) 2022-09-27
US12500607B2 (en) 2025-12-16
EP4322411A4 (en) 2024-07-10
US20240007131A1 (en) 2024-01-04
EP4322411B1 (en) 2025-11-26
WO2022194170A1 (zh) 2022-09-22
EP4322411C0 (en) 2025-11-26
EP4322411A1 (en) 2024-02-14

Similar Documents

Publication Publication Date Title
CN106888025B (zh) 一种基于极化码的级联纠错编译码方法和系统
JP5705106B2 (ja) ユークリッド空間リード−マラー符号の軟判定復号を実行する方法
CN108650057B (zh) 一种编译码的方法、装置及系统
WO2006135878A2 (en) In-place transformations with applications to encoding and decoding various classes of codes
CN107370488A (zh) 纠错编码方法及装置
US11184034B2 (en) Method and device for decoding staircase code, and storage medium
US20160049962A1 (en) Method and apparatus of ldpc encoder in 10gbase-t system
CN111525931B (zh) Ldpc译码器、ldpc译码方法、存储介质和电子设备
JP7746401B2 (ja) エンコーディングおよびデコーディング方法、およびデバイス、並びにシステム
CN114731166A (zh) 空间耦合fec编码方法和使用gel码的分量码的设备
CN102742164B (zh) 一种译码方法和译码装置
US10516418B2 (en) Hybrid type iterative decoding method and apparatus
KR101908389B1 (ko) 에러 정정 코딩 및 디코딩
US9722636B2 (en) Arrangement and method for decoding a data word with the aid of a Reed-Muller code
WO2023023732A1 (en) Modified staircase forward error correction coding
CN115441880A (zh) 译码方法、装置、电子设备及存储介质
CN119210471A (zh) 编码方法、装置、计算机设备和存储介质
EP3529900A1 (en) Construction of ldpc convolutional turbo codes
CN119628656A (zh) 一种信号译码方法、系统、介质、设备和程序产品
RU2575399C1 (ru) Способ декодирования ldpc-кодов и устройство его реализующее
KR100956592B1 (ko) 메시지 전달 알고리즘을 이용한 ｌｄｐｃ 코드 부호화 장치및 그 방법
CN116318183A (zh) 译码方法、装置、电子设备及存储介质
KR101257776B1 (ko) 상태-체크 코드를 이용한 부호화 방법 및 부호화 장치
CN113556136A (zh) 一种gn陪集码译码方法及装置
CN118282579A (zh) 数据传输方法、装置、计算机设备以及存储介质

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20231026

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20231026

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20240930

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20241015

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20250108

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20250422

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20250626

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20250819

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20250917

R150 Certificate of patent or registration of utility model

Ref document number: 7746401

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150