[C코드]LDPC Codes에서 PEG 알고리즘과 IPEG 알고리즘의 성능 비교 평가 및 분석

소개

정보이론에서 채널코딩 분야입니다.
정말 중요한 LDPC코드의 수많은 알고리듬 중에서, PEG, IPEG 알고리듬을 구현하여
비교분석한 논문입니다. 파일의 개수는 총 4개이고,압축파일로 업로드합니다
압출파일을 풀면 1개는 논문한글파일, 2개는 각각 PEG, IPEG 코드를 첨부한 MS word 파일입니다. 그리고 또다른 압축파일은 LDPC encoding-AWGN채널-decoding 을할수 있는 C프로젝트파일입니다-이름: simpleLDPC
방법은
PEG IPEG 각각 워드파일 코드를 이용하여 새로운 프로젝트를 생성한후 실행을 시키면
alist.txt 라는 텍스트파일이 만들어집니다(H행렬을 표시하는 파일) 생성한 alist 파일을 simpleLDPC 프로젝트내부에 복사한 후에 simpleLDPC 프로젝트를 빌드 하면 저절로 alist파일을 읽어들여서 인코딩과 디코딩 과정을 수행하여 BER-SNR 형태로 나타냅니다.

목차

요약
1.서론
2.PEG 알고리듬
가. 개요
나. 순서도
3.IPEG 알고리듬
가. 개요
나. 순서도
4. 모의실험
가. 실험환경
나. 실험과정및 절차
1. PEG알고리즘과 IPEG 알고리즘 비교
2. 부호길이와 BER 비교
3. 부호율에 따른 성능 비교.
5. 분석 및 결론
6. 참고문헌

본문내용

1. 서론
1962년 R.G Gallager가 제안한 LDPC(Low Density Parity- Check)부호는 Shannon의 채널 용량의 한계에 근접한 우수한 오류정정(error correction) 부호이다. 제안당시에는 LDPC 부호 생성의 복잡성 때문에 많은 주목을 받지 못했지만 IC(Integrated Circuit) 기술의 발전에 따른 고성능 컴퓨터의 개발과 더불어 효율적인 LDPC 부호 생성 알고리즘이 많이 개발되면서 최근 들어 활발하게 연구가 진행되고 있다.
우수한 LDPC부호 생성 조건 중 가장 중요한 부분은 바로 girth(최소 사이클 길이)를 최대화 하는 과정인데, Xiao-Yu Hu와 Dieter M. Arnold 가 제안한 PEG(Progressive Edge- Growth)알고리즘은 이 조건을 충분히 만족시키는 우수한 알고리즘으로 인정받고 있다. 이후 Hua Xiao와 Amir H. Banihashemi는 높은 SNR 범위 에서 PEG알고리즘의 성능을 개선한 IPEG (Improved PEG) 알고리즘이 제안했으며 그 외에도 PEG 알고리즘을 기반으로 한 여러 다른 형태의 성능을 향상시킨 알고리즘이 제안되었다. 본 논문은 PEG와 IPEG 알고리즘을 토대로 직접 구성한 알고리즘을 통해 생성한 패리티검사 행렬을 이용하여 BPSK(Binary Phase Shift Keying 변조된 신호를 AWGN(Addictive White Gaussian Noise) 채널 환경에서 복호화하는 과정을 실험해서 BER(Bit Error Rate)관점에서 결과를 출력하고, 두 알고리즘의 결과를 비교 분석하였다. 나아가 PEG 알고리즘에서 고려되고 있지 않은 조건은 무엇이 있는지 알아보고 이를 토대로 더 좋은 성능을 가지는 알고리즘의 방향에 대해 논의한다.

2. PEG 알고리즘

가. 개 요
성능이 뛰어난 LDPC부호를 생성하기 위해서는 큰 girth를 갖는 tanner 그래프(Tanner Graph)를 구성해야 하는데 PEG 알고리즘을 통해 이 조건을 충분히 만족시킬 수 있다.
PEG알고리즘의 핵심은 현재 심벌노드 에서 가장 먼 거리에 있는 체크노드를 찾은 후에 해당 체크노드를 연결하여 새로운 edge를 배치하는 것이다. 이 방법은 tree spreading 방법을 통해 구현할 수 있다. 가장 먼 거리에 있는 체크노드 집합 중에서 degree가 가장 작은 체크노드를 선택하고, 만약 최소 degree를 가진 체크노드가 2개 이상 존재한다면 임의로 한 체크노드를 선택한다. 이와 같은 방법을 통해 패리티검사행렬(Parity Check Matrix)의 small cycle 생성을 억제하고 국부 girth를 최대화할 수 있다. PEG알고리즘의 자세한 설명은 논문[1]에 기재되어 있다.

참고자료

· [1] Xiao-Yu Hu and Dieter M. Arnold "Regular and Irregular Progressive Edge Growth Tanner Graphs," IEEE Trans.inform. theory, vol.51 pp 386-398, Jan. 2005.[2] Hua. Xiao and A. H. Banihashemi "Improved Progressive Edge Growth(PEG) Construction of Ireegular LDPC codes,"IEEE Comm. Letter,vol.8 pp 715-717, Dec. 2004.
· [3] Tao Tian, Chris Jones, John D. Villasenor, and Richard D. Wesel "Construction of Irregular LDPC Codes with Low Error Floors" ULCA, CA, 90095, USA
· [4] http://ipgdemos.epfl.ch/ldpcopt/ Urbanke`s website forcalculating Degree Distribution of symbol nodes and check nodes