검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
On the First Separating Redundancy of Array LDPC Codes
오픈 액세스
배열 LDPC 코드의 첫 번째 분리 중복에 대해

Haiyang LIU, Lianrong MA

  • 조회수

    380

  • 이것을 인용
  • Free PDF (235.8KB)

요약 :

홀수 소수가 주어지면 q 및 정수 mq, 바이너리 mq × q2 준순환 패리티 검사 행렬 H(m, q)는 어레이 저밀도 패리티 검사(LDPC) 코드에 대해 구성될 수 있습니다. C (m, q). 이 편지에서 우리는 첫 번째 분리 중복을 조사합니다. C (m, q). 우리는 그것을 증명합니다 H (m, q)는 (의 임의의 쌍에 대해 1로 분리됩니다.m, q), 그로부터 우리는 첫 번째 분리 중복이 C (m, q)의 상한은 다음과 같습니다. mq. 그런 다음 우리는 첫 번째 분리 중복에 대한 상한을 보여줍니다. C (m, q)은 문헌의 일반적인 결정론적 및 구성적 상한보다 더 엄격합니다. 을 위한 m=2, 우리는 첫 번째 분리 중복성을 추가로 증명합니다. C (2, q)는 2입니다.q 홀수 소수에 대해 q. 용 m ≥ 3, 우리는 첫 번째 분리 중복이 C (m, q)이다 mq 어떤 고정에 대해서도 m 그리고 충분히 크다 q.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.4 pp.670-674
발행일
2024/04/01
공개일
2023/08/16
온라인 ISSN
1745-1337
DOI
10.1587/transfun.2023EAL2030
원고의 종류
LETTER
범주
코딩 이론

1. 서론

분리 중복성은 통신 채널을 통한 선형 블록 코드의 오류 및 삭제 디코딩을 이해하는 데 중요한 개념입니다 [1], [2]. 이러한 중요성에도 불구하고 일반적으로 선형 블록 코드의 분리 중복성을 계산하는 것은 어렵습니다. 분리 중복에 대한 의미 있는 경계를 도출하는 것조차 어려운 문제입니다. 그러나 대수적 구조를 갖는 코드로 제한한다면 분석적 방법을 통한 분리 중복성에 대한 조사가 가능해진다. 현재까지 몇몇 연구에서는 일부 코드 클래스 또는 일부 특정 코드에 대한 분리 중복성을 연구했습니다[3]-[9].

Fan[10]이 제안한 배열 저밀도 패리티 검사(LDPC) 코드는 대수적 LDPC 코드의 중요한 클래스입니다. 배열 LDPC 코드 \({\mathcal C}(m,q)\) 바이너리로 설명 가능 \(mq\times q^2\) 준순환(QC) 패리티 검사 행렬 \({\boldsymbol H}(m,q)\)어디로 \(q\) 홀수 소수이고 \(m\) 는 만족하는 정수입니다 \(m\le q\). 최근에는 어레이 LDPC 코드가 많은 관심을 받고 있습니다. 이들 코드는 우호적인 성능을 갖고 있어 실제 적용에 적합한 것으로 나타났습니다. 또한, 좋은 대수적 특성 덕분에 배열 LDPC 코드의 여러 구조 매개변수가 이전 연구 [11]-[21]에서 이론적으로 분석되고 결정되었으며 이는 코드 성능을 이해하는 데 도움이 됩니다.

이 글에서는 배열 LDPC 코드의 분리 특성을 고려합니다. 분석적 접근법을 사용하여 우리는 다음을 증명합니다. \({\boldsymbol H}(m,q)\) 임의의 쌍에 대해 1로 분리됩니다. \((m,q)\)이는 첫 번째 분리 중복을 나타냅니다. \({\mathcal C}(m,q)\) 상한은 \(mq\), 행 수 \({\boldsymbol H}(m,q)\). 계산을 통해 우리는 첫 번째 분리 중복의 상한을 보여줍니다. \({\mathcal C}(m,q)\) 문헌의 일반적인 결정론적 및 구성적 상한보다 더 엄격합니다. 한편, 이전 결과 [2, 5]를 통해 첫 번째 분리 중복성이 있음을 알 수 있다. \({\mathcal C}(m,q)\) 하한은 다음과 같습니다. \(mq\) 최소 거리라면 \({\mathcal C}^\perp(m,q)\), 이중 \({\mathcal C}(m,q)\), 동일하다 \(q\). (최소 거리는 \({\mathcal C}^\perp(m,q)\) 기껏해야 \(q\), 각 행 이후 \({\boldsymbol H}(m,q)\) 무게가 있다 \(q\).) 을 위한 \(m=2\), 우리는 최소 거리가 \({\mathcal C}^\perp(2,q)\) is \(q\) 홀수 소수에 대해 \(q\)이는 첫 번째 분리 중복성을 의미합니다. \({\mathcal C}(2,q)\) is \(2q\). 수치적 관찰을 통해 우리는 \({\mathcal C}^\perp(m,q)\) is \(q\) 그리고 첫 번째 분리 중복 \({\mathcal C}(m,q)\) is \(mq\) 어떤 고정에 대해서도 \(m\ge 3\) 그리고 충분히 크다 \(q\).

2. 예선

이번 절에서는 행렬 분리와 중복성 분리의 개념을 소개합니다. 또한 본 연구에서 조사할 배열 LDPC 코드의 속성을 검토합니다.

2.1 중복성과 관련 개념의 분리

하자 \(\mathcal{C}\)\([n,k,d]\) 선형 코드 오버 \(\mathbb{F}_q\)어디로 \(\mathbb{F}_q\) 유한 필드는 \(q\) 집단, \(n\), \(k\)\(d\) 길이, 치수 및 최소 거리입니다. \(\mathcal{C}\), 각각. 가정하다 \(\mathcal{C}\) 로 설명됩니다. \(m\times n\) 패리티 검사 매트릭스 \({\boldsymbol H}\), 그 행은 이중 코드에 걸쳐 있습니다. \(\mathcal{C}^{\perp}\). 그 주 \({\boldsymbol H}\) 중복된 행이 포함될 수 있습니다. \(m\ge {\rm rank}({\boldsymbol H})=n-k\)어디로 \({\rm rank}({\boldsymbol H})\) 의 순위이다 \({\boldsymbol H}\) 위에 \(\mathbb{F}_q\).

하자 \(\mathcal{I}=\{1,\cdots,n\}\)\(\mathcal{J}=\{1,\cdots,m\}\) 열과 행의 인덱스가 됩니다. \({\boldsymbol H}\), 각각. 가정하다 \(\mathcal{S}\subseteq \mathcal{I}\)\(\mathcal{T}\subseteq \mathcal{J}\). 허락하다 \({\boldsymbol H}_{\mathcal{S}}^{\mathcal{T}}=[h_{j,i}]\)어디로 \(i\in \mathcal{S}\)\(j\in \mathcal{T}\). 검사를 통해 우리는 다음과 같은 사실을 알고 있습니다. \({\boldsymbol H}_{\mathcal{S}}^{\mathcal{T}}\) 의 하위 행렬이다 \({\boldsymbol H}\) 크기 \(|\mathcal{T}|\times|\mathcal{S}|\)어디로 \(|\mathcal{S}|\) (관련, \(|\mathcal{T}|\))는 세트의 크기입니다. \(\mathcal{S}\) (관련, \(\mathcal{T}\)). 나머지 논의에서 우리는 항상 다음과 같이 가정합니다. \(|\mathcal{S}|\leq d-1\).

하자 \({\boldsymbol x}=[x_i]\) 길이의 벡터가 되어야 합니다. \(n\) 위에 \(\mathbb{F}_q\). 그만큼 해밍 웨이트 (요약하자면, 무게) 의 \({\boldsymbol x}\) is

\[\begin{equation*}{\rm wt}({\boldsymbol x})=|\{i\in \mathcal{I}:x_i\ne 0\}|.\tag{1} \end{equation*}\]

세트의 경우 \(\mathcal{S}\subseteq \mathcal{I}\), 허락하다 \({\boldsymbol x}_{\mathcal{S}}\) 길이의 벡터가 되다 \(|\mathcal{S}|\) 세트에 인덱스가 있는 항목을 삭제하여 얻습니다. \(\bar{\mathcal{S}}=\mathcal{I}\backslash\mathcal{S}\)\({\boldsymbol x}\). 정의하다

\[\begin{equation*} \mathcal{C}_{\bar{\mathcal{S}}}=\{{\boldsymbol c}_{\bar{\mathcal{S}}}:{\boldsymbol c}\in\mathcal{C}\}, \tag{2} \end{equation*}\]

코드는 무엇입니까? \(\mathcal{C}\) 구멍이 뚫린 \(\mathcal{S}\). 다른 말로, \(\mathcal{C}_{\bar{\mathcal{S}}}\) 에 의해 인덱싱된 항목을 삭제하여 얻은 모든 벡터를 포함합니다. \(\mathcal{S}\) 코드워드에서 \(\mathcal{C}\).

밝히다

\[\begin{equation*} \hat{\mathcal{S}}=\{j\in \mathcal{J}:h_{j,i}=0,\ \forall\ i \in \mathcal{S}\}, \tag{3} \end{equation*}\]

\[\begin{equation*} {\boldsymbol H}(\mathcal{S})={\boldsymbol H}_{\bar{\mathcal{S}}}^{\hat{\mathcal{S}}}. \tag{4} \end{equation*}\]

우리는이 \({\rm rank}({\boldsymbol H}(\mathcal{S}))\le n-k-|\mathcal{S}|\) [2]. 만약에 \({\rm rank}({\boldsymbol H}(\mathcal{S}))=n-k-|\mathcal{S}|\), \({\boldsymbol H}(\mathcal{S})\) 코드의 패리티 검사 행렬입니다 \(\mathcal{C}_{\bar{\mathcal{S}}}\) (2)에서. 이런 경우에 우리는 이렇게 말합니다. \({\boldsymbol H}\) 분리하다 세트 \(\mathcal{S}\).

정의 1([2]): 가정 \({\boldsymbol H}\) 의 패리티 검사 행렬이다 \([n,k,d]\) 선형 코드 \(\mathcal{C}\) 위에 \(\mathbb{F}_q\)\(\mathcal{I}\) 열 인덱스 세트는 다음과 같습니다. \({\boldsymbol H}\). 면 \({\boldsymbol H}\) 모든 하위 집합을 분리합니다. \(\mathcal{I}\) 크기 \(1,2,\cdots,l\)다음, \({\boldsymbol H}\) 이라고합니다 \(l\)-분리, 어디서 \(l\) 는 다음과 같은 양의 정수입니다. \(l \le d-1\).

항상 존재함을 알 수 있다. \(l\)- 선형 코드에 대한 패리티 검사 매트릭스 분리 \(\mathcal{C}\) 최소 거리로 \(d\) 그리고 임의의 양의 정수 \(l\le d-1\) [1]-[3]. 실용적인 관점에서 볼 때, 합리적인 복잡성을 유지하기 위해서는 패리티 검사 행렬의 행 수를 가능한 한 작게 만드는 것이 바람직합니다.

정의 2([2]): 이 어플리케이션에는 XNUMXµm 및 XNUMXµm 파장에서 최대 XNUMXW의 평균 출력을 제공하는 \(l\)-차 분리 중복 코드의 \(\mathcal{C}\), 로 표시 \(s_l(\mathcal{C})\)는 의 최소 행 수로 정의됩니다. \(l\)- 패리티 검사 행렬 분리 \(\mathcal{C}\).

이 편지에서 우리는 첫 번째 분리 중복을 고려합니다. 우리의 논의에는 다음과 같은 하한이 필요합니다.

정리 1 ([2], [5]): 를 위해 \([n,k]\) 선형 코드 \({\mathcal C}\),

\[\begin{equation*} s_1(\mathcal{C})\ge \lceil \frac{n}{n-d^\perp}(n-k-1)\rceil, \tag{5} \end{equation*}\]

어디에 \(d^\perp\) 최소 거리는 \(\mathcal{C}^\perp\).

2.2 어레이 LDPC 코드

하자 \(q\) 홀수 소수가 되고 \(m\le q\) 정수. 배열 LDPC 코드 \(\mathcal{C}(m,q)\) [10]은 다음과 같이 지정되는 이진 선형 코드입니다. \(mq\times q^2\) QC 패리티 검사 매트릭스:

\[\begin{eqnarray*} &&\!\!\!\!\! {\boldsymbol H}(m,q)=\left[\begin{array}{c} {\boldsymbol H}_1 \\ {\boldsymbol H}_2 \\ \vdots \\ {\boldsymbol H}_m\end{array}\right]\nonumber\\ &&\!\!\!\!\!\quad =\left[\begin{array}{ccccc} {\boldsymbol I}_q&{\boldsymbol I}_q&{\boldsymbol I}_q&\cdots&{\boldsymbol I}_q \\ {\boldsymbol I}_q&{\boldsymbol P}&{\boldsymbol P}^2&\cdots&{\boldsymbol P}^{q-1} \\ &\vdots&&\vdots& \\ {\boldsymbol I}_q&{\boldsymbol P}^{m-1}&{\boldsymbol P}^{2(m-1)}&\cdots&{\boldsymbol P}^{(m-1)(q-1)}\end{array}\right], \tag{6} \end{eqnarray*}\]

어디에 \({\boldsymbol I}_q\) 하는 \(q\times q\) 단위 행렬, \({\boldsymbol P}=\left[\begin{array}{cc} {\bf 0}&1\\{\boldsymbol I}_{q-1}&{\bf 0}^{\rm T} \end{array}\right]\)\({\bf 0}\) 길이가 모두 0인 행 벡터입니다. \(q-1\). 그것은 분명하다 \({\boldsymbol H}(m,q)\) 규칙적이며 각 열(각각, 행)은 \({\boldsymbol H}(m,q)\) 무게가 있다 \(m\) (관련, \(q\)).

정리 2 ([11]): 우리는이 \({\rm rank}({\boldsymbol H}(m,q))=m(q-1)+1\).

행 공간 \({\boldsymbol H}(m,q)\) 이중 코드는 \(\mathcal{C}(m,q)\), 로 표시 \(\mathcal{C}^\perp(m,q)\). Lemma 2에 따르면, 차원은 \(\mathcal{C}^\perp(m,q)\) is \(m(q-1)+1\).

3. 주요 결과

이 섹션에서는 주요 이론적 결과를 제공합니다. 먼저, 다음 보조정리를 증명해 보겠습니다.

보조정리 3: 가정 \({\boldsymbol H}'(m,q)\) 다음에서 얻은 행렬입니다. \({\boldsymbol H}(m,q)\) (6)에서 각 하위 행렬에서 행을 제거하여 \({\boldsymbol H}_j,j=2,\cdots, m\). 그것은 그것을 유지 \({\rm rank}({\boldsymbol H}'(m,q))=m(q-1)+1\).

증명: 제거된 각 행이 다음 행의 일부 행의 선형 조합이라는 점만 보여주면 됩니다. \({\boldsymbol H}'(m,q)\). 먼저 생각해 보자. \(j=2\). 가정하다 \({\boldsymbol h}\) 의 행은 다음과 같습니다. \({\boldsymbol H}_2\) 에서 제거된 것 \({\boldsymbol H}(m,q)\) 구하는 \({\boldsymbol H}'(m,q)\). 검사를 통해 우리는 \(2q\)\({\boldsymbol H}_1\)\({\boldsymbol H}_2\) 는 모두 0인 벡터입니다. 결과로서, \({\boldsymbol h}\) ~의 합이다 \(2q-1\) 행, \(q\)\({\boldsymbol H}_1\) 뿐만 아니라 \(q-1\)\({\boldsymbol H}_2\) 예외사항 : \({\boldsymbol h}\), 각각은 다음의 행입니다. \({\boldsymbol H}'(m,q)\). 에 대해서도 마찬가지이다 \(j=3,\cdots, m\), 그리고 보조정리가 증명되었습니다. \(\square\)

비고 1 : Lemma 3을 통해 우리는 다음을 알고 있습니다. \({\boldsymbol H}'(m,q)\) 는 또한 다음의 패리티 검사 행렬입니다. \({\mathcal C}(m,q)\). 게다가 이후 \({\boldsymbol H}'(m,q)\)\(m(q-1)+1\) 행, 이는 다음의 생성 행렬입니다. \({\mathcal C}^\perp(m,q)\).

정리 1: 패리티 검사 매트릭스 \({\boldsymbol H}(m,q)\) 1로 분리됩니다.

증명: 고려하다 \(i\)-번째 열 \({\boldsymbol H}(m,q)\) 그리고 \({\mathcal S}=\{i\}\)어디로 \(1\le i\le q^2\). (6)에 의해 우리는 다음이 있음을 알 수 있다. \(m\)\({\boldsymbol H}(m,q)\), 각각 한 행씩 \({\boldsymbol H}_j(j=1,\cdots,m)\), 누구의 \(i\)-번째 열은 1입니다. 행 순열을 수행합니다. \({\boldsymbol H}(m,q)\) 이렇게 \(m\) 행은 얻은 행렬의 맨 위에 있으며, 이는 다음과 같이 표시됩니다. \({\boldsymbol H}\). 즉, 모든 첫 번째 \(m\) 항목의 \(i\)-번째 열 \({\boldsymbol H}\) 하나입니다. Lemma 3을 통해 우리는 첫 번째 행과 마지막 행이 다음과 같다고 결론을 내립니다. \(m(q-1)\)\({\boldsymbol H}\) are \(m(q-1)+1\) 선형 독립 행. 이는 마지막 \(m(q-1)\)\({\boldsymbol H}\) 선형독립이다. 그러므로 우리는 \({\rm rank}({\boldsymbol H}(\mathcal{S}))=m(q-1)={\rm rank}({\boldsymbol H}(m,q))-1\)어디로 \({\boldsymbol H}(\mathcal{S})\) (4)에 의해 정의된다. 이는 다음을 나타냅니다. \({\boldsymbol H}\) 세트를 분리합니다 \({\mathcal S}\), 그로부터 우리는 다음과 같은 결론을 내립니다. \({\boldsymbol H}\) 1로 분리됩니다. \(\square\)

다음 상한은 정리 1과 정의 2의 직접적인 결과입니다.

결과 1: 가정 \(s_1({\mathcal C}(m,q))\) 최초의 분리 중복입니다. \({\mathcal C}(m,q)\). 그때 \(s_1({\mathcal C}(m,q))\le mq\).

이제 우리는 추론 1의 상한을 알려진 상한과 비교합니다. 문헌에서는 일반 선형 코드 또는 일부 특정(패밀리) 코드에 대해 분리 중복성에 대한 여러 상한이 제공되었습니다[1]-[9]. 그러나 분리 중복에 대해서는 구체적인 결과가 없습니다. \({\mathcal C}(m,q)\) 우리가 아는 한도 내에서 이용 가능합니다. 따라서 우리는 한계를 일반적인 상한과 비교합니다. [2, 정리 10]과 [5, 정리 10]의 상한은 \(s_l(\mathcal{C})\) 다항식 함수인 경향이 있습니다. \(n-k\) 에 대한 \([n,k,d]\) 암호 \(\mathcal{C}\) 그리고 주어진 값 \(l\le d-1\) 특정 조건에서. 정리의 증명은 우리가 다음을 찾을 수 있음을 나타냅니다. \(l\)- 확률론적 알고리즘을 통해 상한값을 충족하는 패리티 검사 행렬을 분리합니다. 그러나 이러한 경계는 결정적이지 않습니다.

결과 1의 상한은 결정론적이며 구성적이므로 다음에서 각각 [2, 결과 5] 및 [5, 정리 17]에 제공된 두 개의 일반적인 결정론적 및 구성적 상한과 우리의 경계를 비교합니다.

[2, 추론 5]의 상한은 다음과 같습니다.

\[\begin{equation*} s_1({\mathcal C})\le\sum_{i=1}^{2}\left(\begin{array}{c}n-k \\ i\end{array}\right) \tag{7} \end{equation*}\]

에 대한 보유 \([n,k,d]\) 이진 코드 \({\mathcal C}\)\(d\ge 3\). 용 \(s_1({\mathcal C}(m,\) \(q))\), (7)의 상한은 다음과 같습니다. \(\frac{1}{2}(mq-m+1)(mq-m+2)\). 계산을 통해 우리는 다음과 같이 결론을 내립니다. \(\frac{1}{2}(mq-m+1)(mq-m+2)>mq\) 어떤 경우에도 보유 \((m,q)\) 그렇게 \(q\ge 3\)\(m\le q\)이는 결과 1의 상한이 더 좋다는 것을 의미합니다.

[5, 정리 17]의 상한은 다음과 같습니다.

\[\begin{equation*} s_1({\mathcal C})\le \min \left\{(n-k)C_1(n,\mu,1),(n-k-1)\left( \begin{array}{c} n \\ 1 \end{array} \right)\right\} \tag{8} \end{equation*}\]

에 대한 보유 \([n,k,d]\) 암호 \({\mathcal C}\)어디로 \(C_1(n,\mu,1)\) 커버링 번호 [22]이고 \(\mu=\min\{d,n-k\}-1\).

럭셔리 \({\mathcal C}(m,q)\), 우리는 \(\mu=d-1\)\(C_1(n,\mu,1)=\lceil\frac{n}{d-1}\rceil\). 조사해 보면 (8)의 상한은 다음과 같다는 것을 알 수 있습니다. \((n-k)\lceil\frac{n}{d-1}\rceil\). 그것은 그것을 유지 \(d\le 2q<2q+1\)이후 \([{\bf 1},{\bf 1},{\bf 0},\cdots,{\bf 0}]\) 의 코드워드입니다 \({\mathcal C}(m,q)\)어디로 \({\bf 1}\) (관련, \({\bf 0}\))는 길이가 모두 1인(모두 0인) 벡터입니다. \(q\). 따라서 우리는 \(\frac{n}{d-1}>\frac{q}{2}\), 이는 다음을 시사합니다.

\[\lceil\frac{n}{d-1}\rceil \ge \lceil\frac{q}{2}\rceil=\frac{q+1}{2}.\]

결과로서,

\[\begin{aligned} &&\!\!\!\!\! (n-k)\lceil\frac{n}{d-1}\rceil \ge\frac{(mq-m+1)(q+1)}{2}\\ &&\!\!\!\!\! \hskip2.7cm\overset{({\rm a})}{\ge} \frac{(2m+1)(q+1)}{2}>mq. \end{aligned}\]

위의 부등식 (a)는 다음과 같은 사실에 기인합니다. \(q\ge 3\). 다시 말하지만, 추론 1의 상한이 더 좋습니다.

표 1에는 일부 쌍에 대한 추론 1의 상한과 [2, 추론 5] 및 [5, 정리 17]의 상한 계산 결과가 나열되어 있습니다. \((m,q)\). 비교를 위해 [5, 정리 10]에서 상한도 계산했는데, 이는 선형 코드의 분리 중복성에 대한 개선된 확률적 상한입니다. 표에서 우리의 상한이 모든 계산된 사례에 대해 알려진 상한보다 낫다는 것을 알 수 있습니다.

표 1  의 상한에 대한 계산 결과 \(s_1({\mathcal C}(m,q))\).

우리는 이전 논의를 통해 다음과 같은 사실을 알고 있습니다. \({\boldsymbol H}'(m,q)\) 다음의 생성 행렬은 다음과 같습니다. \({\mathcal C}^\perp(m,q)\). 각 행부터 \({\boldsymbol H}'(m,q)\) 무게가 있다 \(q\), 우리는 \(d({\mathcal C}^\perp(m,q))\le q\). 계산을 통해 Lemma 1의 하한은 다음과 같다고 결론을 내렸습니다. \(s_1({\mathcal C}(m,q))\ge mq\) if \(d({\mathcal C}^\perp(m,q))=q\). 결론 1에 따르면, 우리는 \(s_1({\mathcal C}(m,q))=mq\) if \(d({\mathcal C}^\perp(m,q))=q\). 결과적으로, 상한선이 있는지 조사하는 것은 흥미롭습니다. \(d({\mathcal C}^\perp(m,q))\le q\) 한 쌍으로는 빡빡해요 \((m,q)\). 이를 위해 우리는 몇 가지 컴퓨터 검색을 수행했습니다. 결과는 표 2에 나열되어 있습니다.

표 2  일부 값 \(d({\mathcal C}^\perp(m,q))\).

럭셔리 \(m=2\), 우리는 모든 값에 대해 철저한 컴퓨터 검색을 수행했습니다. \(q\) 표 2에 나열되어 있습니다. \(m\ge 3\), 우리는 다음에 대한 철저한 컴퓨터 검색을 수행했습니다. \(q\le 7\). 값은 코드워드의 최소 가중치입니다. \({\mathcal C}^\perp(m,q)\) 이러한 경우에는.

나머지 경우에는 과도한 실행 시간으로 인해 철저한 컴퓨터 검색을 수행하지 않았습니다. 대신에 우리는 다음의 패리티 검사 행렬에 대해 포괄적이지 않은 컴퓨터 검색을 수행했습니다. \({\mathcal C}^\perp(m,q)\) 이러한 경우에는 [23]의 낮은 가중치 코드워드 검색 알고리즘을 사용합니다. 값은 이러한 경우에 대해 수집된 코드워드의 최소 가중치입니다. (생성기 행렬은 \({\mathcal C}(m,q)\)[11] 또는 [21]에서 제공되는 는 다음과 같은 패리티 검사 행렬입니다. \({\mathcal C}^\perp(m,q)\).) 우리는 이러한 경우의 모든 값을 다음과 같이 조판합니다. 이탤릭체.

표 2의 결과에서 알 수 있듯이 \(d({\mathcal C}^\perp(m,q))\) 보다 작을 수 있습니다 \(q\) if \(m\) 가까운 \(q\) 주어진 \(q\). 이후 \({\mathcal C}^\perp(m,q)\) 의 하위 코드입니다 \({\mathcal C}^\perp(m',q)\) if \(m<m'\), 우리는 \(d({\mathcal C}^\perp(m,q))\ge d({\mathcal C}^\perp(m',q))\). 실제로 우리는 다음과 같은 결과를 얻었습니다.

정리 2: 홀수 소수의 경우 \(q\), 우리는 \(d({\mathcal C}^\perp(q,q))=2\)어디로 \(d({\mathcal C}^\perp(q,q))\) 최소 거리는 \({\mathcal C}^\perp(q,q)\).

증명: 검사를 통해 다음과 같은 사실을 알 수 있습니다. \((q-1)\times q^2\) 매트릭스

\[\begin{equation*} \left[\begin{array}{ccccc} {\bf 1}&{\bf 1}&&& \\ &{\bf 1}&{\bf 1}&& \\ &&\ddots&\ddots& \\ &&&{\bf 1}&{\bf 1} \end{array}\right] \tag{9} \end{equation*}\]

패리티 검사 행렬은 다음과 같습니다. \({\mathcal C}^\perp(q,q)\)어디로 \({\bf 1}\) 길이가 모두 하나로 구성된 벡터입니다. \(q\). 그러므로, \({\mathcal C}^\perp(q,q)\) 가중치 1의 코드워드가 포함되어 있지 않습니다. (9) 행렬의 처음 두 열이 동일하기 때문에 다음을 얻습니다. \(d({\mathcal C}^\perp(q,q))=2\). \(\square\)

반면에 우리는 표 2에서 다음과 같은 결론을 내립니다. \(d({\mathcal C}^\perp\) \((2,q))=q\) 모든 값에 대해 유지됩니다. \(q\) 테이블에. 다음에서 우리는 다음을 증명합니다. \(d({\mathcal C}^\perp(2,q))=q\) 보유하다 어떤 홀수 소수 \(q\). 이에 앞서 작품[12]의 아이디어를 일반화하고, \({\boldsymbol H}(2,q)\), 이는 분석에 유용합니다.

우리는 (6)을 통해 다음의 각 행을 알 수 있습니다. \({\boldsymbol H}(2,q)\) 로 분할 될 수있다 \(q\) 블록과 각 블록은 세트의 하나의 벡터입니다. \(\mathcal{Z}=\{{\boldsymbol e}_0,{\boldsymbol e}_1,\cdots,{\boldsymbol e}_{q-1}\}\)어디로 \({\boldsymbol e}_i\) 길이가 모두 0인 행 벡터입니다. \(q\) 그것을 제외하고 \((i+1)\)-번째 항목은 1입니다. 매핑을 구성합니다. \(\phi:\mathcal{Z}\rightarrow\mathbb{Z}_q\) by \(\phi({\boldsymbol e}_i)=i\). 그런 다음 모든 행의 \({\boldsymbol H}_1\) 길이의 행 벡터로 표현될 수 있습니다. \(q\)

\[\begin{equation*} \left[i,i,i,\cdots,i\right] \tag{10} \end{equation*}\]

일부 \(i\in \mathbb{Z}_q\). 마찬가지로, 모든 행의 \({\boldsymbol H}_2\) 길이의 행 벡터로 표현될 수 있습니다. \(q\)

\[\begin{equation*} \hskip -0.08cm\left[i,i+(q-1),i+2(q-1),\cdots,i+(q-1)(q-1)\right] \tag{11} \end{equation*}\]

일부 \(i\in \mathbb{Z}_q\). ((10) 또는 (11)의 항목이 모드를 형성한다는 점에 유의하십시오.\(q\) 산술 진행.) 그런 다음 우리는 \(2q\times q\) 매트릭스 \(\tilde{\boldsymbol H}(2,q)=\left[ \begin{array}{c} \tilde{\boldsymbol H}_1\\ \tilde{\boldsymbol H}_2 \end{array}\right]\)어디로 \(\tilde{\boldsymbol H}_1\) (관련, \(\tilde{\boldsymbol H}_2\))는 의 각 행을 표현하여 얻습니다. \({\boldsymbol H}_1\) (관련, \({\boldsymbol H}_2\)) 양식 (10) (각각, (11)). 예를 들어, XNUMX개 행의 \(\tilde{\boldsymbol H}(2,3)\) 에 의해 연속적으로 주어진다. \([0\ 0\ 0]\), \([1\ 1\ 1]\), \([2\ 2\ 2]\), \([0\ 2\ 1]\), \([1\ 0\ 2]\)\([2\ 1\ 0]\).

리콜 \({\boldsymbol H}'(2,q)\) 다음의 생성 행렬은 다음과 같습니다. \({\mathcal C}^\perp(m,q)\)어디로 \({\boldsymbol H}'(2,q)\) 에서 얻은 \({\boldsymbol H}(2,q)\) 마지막 행을 제거하여. 편의상, \(\tilde{\boldsymbol H}'(2,q)=\left[ \begin{array}{c} \tilde{\boldsymbol H}_1\\ \tilde{\boldsymbol H}'_2 \end{array}\right]\)어디로 \(\tilde{\boldsymbol H}'_2\) 에서 얻은 \(\tilde{\boldsymbol H}_2\) 마지막 행을 제거하여.

두 개의 열 벡터의 경우 \({\boldsymbol a}\)\({\boldsymbol b}\) 길이의 \(r\), \({\boldsymbol b}\) 라고 한다 순열 버전 of \({\boldsymbol a}\) 만약 존재한다면 \(\sigma\in {\mathcal S}_r\) 그렇게 \(b_{\sigma(i)}=a_i\) 각각 \(1\le i\le r\)어디로 \({\mathcal S}_r\) 세트의 모든 순열의 집합입니다. \(\{1,2,\cdots,r\}\). 예를 들어, \([0\ 2\ 3\ 1]^{\rm T}\) 순열 버전입니다 \([1\ 3\ 0\ 2]^{\rm T}\).

정리 3: 최소 거리 \({\mathcal C}^\perp(2,q)\), \(d({\mathcal C}^\perp\) \((2,q))\)이다 \(q\) 홀수 소수에 대해 \(q\).

증명: 가정 \({\boldsymbol v}=[{\boldsymbol v}_1,{\boldsymbol v}_2,\cdots,{\boldsymbol v}_q]\) 의 코드워드입니다 \({\mathcal C}^\perp(2,q)\), 여기서 각각 \({\boldsymbol v}_i(1\le i\le q)\) 길이가 길다 \(q\). 우리는 다음 두 가지 경우를 구별합니다.

케이스 1 : \({\boldsymbol v}_i\ne {\bf 0}\) 각각 \(1\le i\le q\)어디로 \({\bf 0}\) 길이가 모두 0인 벡터입니다. \(q\). 따라서 우리는 \({\rm wt}({\boldsymbol v}_i)\ge 1\) 각각 \(1\le i\le q\), 이는 다음을 나타냅니다. \({\rm wt}({\boldsymbol v})\ge q\) 이 경우

사례 2: 벡터가 존재합니다. \({\boldsymbol v}_i\) 그것은 같다 \({\bf 0}\). 일반성을 잃지 않고 다음과 같이 가정할 수 있습니다. \({\boldsymbol v}_1={\bf 0}\). 이후 \({\boldsymbol H}'(2,q)\) 다음의 생성 행렬은 다음과 같습니다. \({\mathcal C}^\perp(2,q)\), \({\boldsymbol v}\) 일부 행의 합입니다. \({\boldsymbol H}'(2,q)\). 이 행의 인덱스 집합을 다음과 같이 나타냅니다. \({\mathcal V}={\mathcal V}_1\cup{\mathcal V}_2\)어디로 \({\mathcal V}_1\)\({\mathcal V}_2\) 의 하위 집합입니다 \(\{1,\cdots,q\}\)\(\{q+1,\cdots,2q-1\}\), 각각. 행렬 구성

\[\begin{equation*} \tilde{\boldsymbol H}''=\left[ \begin{array}{c} \tilde{\boldsymbol H}''_1 \\ \tilde{\boldsymbol H}''_2 \end{array} \right]=\left[ \begin{array}{cccc} {\boldsymbol h}_{1,1}&{\boldsymbol h}_{1,2}&\cdots&{\boldsymbol h}_{1,q} \\ {\boldsymbol h}_{2,1}&{\boldsymbol h}_{2,2}&\cdots&{\boldsymbol h}_{2,q} \end{array} \right], \tag{12} \end{equation*}\]

어디에 \(\tilde{\boldsymbol H}''_1\) (관련, \(\tilde{\boldsymbol H}''_2\))는 \(\tilde{\boldsymbol H}_1\) (관련, \(\tilde{\boldsymbol H}'_2\)) 행 인덱스가 세트에 있음 \({\mathcal V}_1\) (관련, \({\mathcal V}_2\)). 이후 \({\boldsymbol v}_1={\bf 0}\), \(\tilde{\boldsymbol H}''_1\)\(\tilde{\boldsymbol H}''_2\) 동일한 수의 행을 가집니다. 숫자를 다음과 같이 나타냅니다. \(r\). 우리는 가지고있다. \(1\le r\le q-1\). 게다가, \({\boldsymbol h}_{2,1}\) 순열 버전입니다 \({\boldsymbol h}_{1,1}\). 가정하다 \(r\) 항목 \({\boldsymbol h}_{1,1}\) or \({\boldsymbol h}_{2,1}\) are \(j_1,j_2,\cdots,j_r\).

우리는 다음과 같이 주장합니다. \({\boldsymbol h}_{2,l}\) 순열 버전이 아닙니다. \({\boldsymbol h}_{1,l}\) 각각 \(2\le l \le q\). 반대로 가정해보자. (10)에 의해 우리는 \(r\) 항목 \({\boldsymbol h}_{1,l}\) are \(j_1,j_2,\cdots,j_r\). (11)에 의해 우리는 \(r\) 항목 \({\boldsymbol h}_{2,l}\) are \(j_1+l'(q-1),j_2+l'(q-1),\cdots,j_r+l'(q-1)\)어디로 \(l'=l-1\). 면 \({\boldsymbol h}_{2,l}\) 순열 버전입니다 \({\boldsymbol h}_{1,l}\), 우리는

\[\begin{array}{@{}l@{}} j_1+j_2+\cdots+j_r=j_1+l'(q-1)+j_2+l'(q-1)\\ \hphantom{j_1+j_2+\cdots+j_r = } +\cdots+j_r+l'(q-1) \end{array}\]

몇 가지 계산을 한 후에 우리는

\[rl'(q-1)=0,\]

그 이후로 모순이다 \(1\le r\le q-1\)\(1\le l'\le q-1\).

때문에 \({\boldsymbol h}_{2,l}\) 순열 버전이 아닙니다. \({\boldsymbol h}_{1,l}\), 우리는 적어도 하나의 항목이 존재한다고 결론을 내립니다. \({\boldsymbol h}_{2,l}\) (관련, \({\boldsymbol h}_{1,l}\)) 그건 에 없어 \({\boldsymbol h}_{1,l}\) (관련, \({\boldsymbol h}_{2,l}\)) 각각 \(2\le l \le q\). 이것은 다음을 의미합니다 \({\rm wt}({\boldsymbol v}_{l})\ge 2\) 각각 보유 \(2\le l \le q\). 그러므로, \({\rm wt}({\boldsymbol v})\ge 2(q-1)>q\) 이 경우

이로써 증명이 완료되었습니다. \(\square\)

Lemma 1, Theorem 2, Corollary 1에 의해 다음과 같은 결과를 얻습니다.

결과 2: 위의 표기법을 사용하면 다음과 같습니다. \(s_1({\mathcal C}(2,q))=2q\).

비고 2 : 우리는 하한선을 언급합니다. \(s_1({\mathcal C}(2,q))\) \(\ge 2q\) [8, 정리 1]에서도 얻을 수 있습니다. \({\mathcal C}^\perp(2,q)\) 차원이 있다 \(2q-1\).

고정된 경우 \(m\ge 3\), 우리는 표 2의 결과로부터 다음을 알 수 있습니다. \(d({\mathcal C}^\perp(m,q))\) 것 같다 \(q\) as \(q\) 증가합니다. 우리는 다음과 같은 추측을 제시합니다.

추측 1: 위의 표기법을 사용하면, \(d({\mathcal C}^\perp(m,q))=q\)\(s_1({\mathcal C}(m,q))=mq\) 고정된 부분에 대해 보류 \(m\ge 3\) 그리고 충분히 크다 \(q\).

4. 결론

이 편지에서 우리는 조사했습니다. \(s_1({\mathcal C}(m,q))\), 최초의 분리 중복 \({\mathcal C}(m,q)\). 우리는 그것을 증명했다 \({\boldsymbol H}(m,q)\) 임의의 쌍에 대해 1로 분리됩니다. \((m,q)\) 그리고 상한값을 얻었습니다. \(s_1({\mathcal C}(m,q))\le mq\). 그런 다음 우리는 \(s_1({\mathcal C}(m,q))\) 문헌의 일반적인 결정론적 및 구성적 상한보다 더 엄격합니다. 을 위한 \(m=2\), 우리는 다음을 추가로 증명했습니다. \(s_1({\mathcal C}(2,q))=2q\) 홀수 소수에 대해 \(q\). 우리는 또한 다음과 같은 추측을 제시했습니다. \(s_1({\mathcal C}(m,q)=mq\) 어떤 고정에 대해서도 \(m\ge 3\) 그리고 충분히 크다 \(q\) 수치적 관찰을 기반으로 합니다.

앞으로의 연구로 위에서 언급한 추측을 증명해보도록 하겠습니다. 추가 연구를 위한 또 다른 질문은 다음의 값을 결정하는 것입니다. \(s_l(\mathcal{C}(m,q))\) 또는 다음에 대한 의미 있는 경계를 제공합니다. \(l\ge 2\).

감사의

저자들은 심사자의 귀중한 논평에 깊은 감사를 드립니다.

참고문헌

[1] K.A.S. Abdel-Ghaffar and J.H. Weber, “Separating erasures from errors for decoding,” Proc. IEEE Int. Symp. Inf. Theory, Toronto, Canada, pp.215-219, July 2008.
CrossRef

[2] K.A.S. Abdel-Ghaffar and J.H. Weber, “Parity-check matrices separating erasures from errors,” IEEE Trans. Inf. Theory, vol.59, no.6, pp.3332-3346, June 2013.
CrossRef

[3] K.A.S. Abdel-Ghaffar and J.H. Weber, “Separating redundancy of linear MDS codes,” Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, pp.7-12, July 2013.
CrossRef

[4] H. Liu, D. Kim, Y. Li, and A.Z. Jia, “On the separating redundancy of extended Hamming codes,” Proc. IEEE Int. Symp. Inf. Theory, Hong Kong, China, pp.2406-2410, June 2015.
CrossRef

[5] Y. Tsunoda, Y. Fujiwara, H. Ando, and P. Vandendriessche, “Bounds on separating redundancy of linear codes and rates of X-codes,” IEEE Trans. Inf. Theory, vol.64, no.12, pp.7577-7593, Dec. 2018.
CrossRef

[6] H. Liu, Y. Li, and L. Ma, “On the second separating redundancy of LDPC codes from finite planes,” IEICE Trans. Fundamentals, vol.E101-A, no.3, pp.617-622, March 2018.
CrossRef

[7] H. Liu, Y. Li, and L. Ma, “On the separating redundancy of the duals of first-order generalized Reed-Muller codes,” IEICE Trans. Fundamentals, vol.E102-A, no.1, pp.310-315, Jan. 2019.
CrossRef

[8] H. Liu and L. Ma, “Further results on the separating redundancy of binary linear codes,” IEICE Trans. Fundamentals, vol.E102-A, no.10, pp.1420-1425, Oct. 2019.
CrossRef

[9] H. Liu, L. Ma, and H. Zhang, “On the separating redundancy of ternary Golay codes,” IEICE Trans. Fundamentals, vol.E104-A, no.3, pp.650-655, March 2021.
CrossRef

[10] J.L. Fan, “Array codes as low-density parity-check codes,” Proc. 2nd Int. Symp. Turbo Codes, pp.543-546, Sept. 2000.

[11] T. Mittelholzer, “Efficient encoding and minimum distance bounds of Reed-Solomon-type array codes,” Proc. IEEE Int. Symp. Information Theory (ISIT), p.282, June/July 2002.
CrossRef

[12] K. Yang and T. Helleseth, “On the minimum distance of array codes as LDPC codes,” IEEE Trans. Inf. Theory, vol.49, no.12, pp.3268-3271, Dec. 2003.
CrossRef

[13] K. Sugiyama and Y. Kaji, “On the minimum weight of simple full-length array LDPC codes,” IEICE Trans. Fundamentals, vol.E91-A, no.6, pp.1502-1508, June 2008.
CrossRef

[14] Y. Kaji, “On the number of minimum weight codewords of SFA-LDPC codes,” Proc. IEEE Int. Symp. Information Theory (ISIT), pp.70-74, June/July 2009.
CrossRef

[15] M. Esmaeili and M. J. Amoshahy, “On the stopping distance of array code parity-check matrices,” IEEE Trans. Inf. Theory, vol.55, no.8, pp.3488-3493, Aug. 2009.
CrossRef

[16] M. Esmaeili, M.H. Tadayon, and T.A. Gulliver, “More on the stopping and minimum distances of array codes,” IEEE Trans. Commun., vol.59, no.3, pp.750-757, March 2011.
CrossRef

[17] H. Liu, L. Ma, and J. Chen, “On the number of minimum stopping sets and minimum codewords of array LDPC codes,” IEEE Commun. Lett., vol.14, no.7, pp.670-672, July 2010.
CrossRef

[18] H. Liu, L. He, and J. Chen, “Further results on the stopping distance of array LDPC matrices,” IEICE Trans. Fundamentals, vol.E95-A, no.5, pp.918-926, May 2012.
CrossRef

[19] L. Dolecek, Z. Zhang, M.J. Wainwright, V. Anantharam, and B. Nikolic, “Analysis of absorbing sets and fully absorbing sets of array-based LDPC codes,” IEEE Trans. Inf. Theory, vol.56, no.1, pp.181-201, Jan. 2010.
CrossRef

[20] E. Rosnes, M.A. Ambroze, and M. Tomlinson, “On the minimum/stopping distance of array low-density parity-check codes,” IEEE Trans. Inf. Theory, vol.60, no.9, pp.5204-5214, Sept. 2014.
CrossRef

[21] H. Liu, S. Yang, G. Deng, and J. Chen, “More on the minimum distance of array LDPC codes,” IEEE Commun. Lett., vol.18, no.9, pp.1479-1482, July 2010.
CrossRef

[22] C.J. Colbourn and J.H. Dinitz, eds., Handbook of Combinatorial Designs, 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2007.

[23] X.Y. Hu, M.P.C. Fossorier, and E. Eleftheriou, “On the computation of the minimum distance of low-density parity-check codes,” Proc. IEEE International Conf. Commun., pp.767-771, 2004.
CrossRef

작성자

Haiyang LIU
  Chinese Academy of Sciences
Lianrong MA
  Tsinghua University

키워드