KR101290472B1

KR101290472B1 - Method and apparatus parallel decoding in a mobile communication system

Info

Publication number: KR101290472B1
Application number: KR1020060115852A
Authority: KR
Inventors: 이종훈; 김민구; 최승훈; 김재열; 양경철
Original assignee: 삼성전자주식회사
Priority date: 2006-11-22
Filing date: 2006-11-22
Publication date: 2013-07-26
Anticipated expiration: 2026-11-22
Also published as: KR20080046421A

Abstract

본 발명의 이동 통신 시스템에서 복호 장치는, 인터리빙을 위한 메모리 영역을 상기 복수의 복호 코어 별로 균등하게 분할하고, 상기 복수의 복호 코어 각각이 복호를 위해 접근하는 메모리 뱅크의 시작 위치가 서로 상이하도록 상기 복수의 복호 코어 각각에 대한 복호 시작 위치를 서로 다르게 설정하며, 상기 복수의 복호 코어 각각에 대한 복호 시작 위치는 첫 번째 복호 코어의 메모리 뱅크 시작 행을 기준으로 R/M의 정수 배를 가지도록 설정되며, 상기 R은 상기 메모리 영역을 구성하는 행의 수이고, 상기 M은 상기 복수의 복호 코어의 개수임을 특징으로 한다.In the mobile communication system of the present invention, the decoding apparatus divides the memory area for interleaving evenly for each of the plurality of decoding cores, and the start positions of the memory banks to which each of the plurality of decoding cores approaches for decoding differ from each other. A decoding start position for each of the plurality of decoding cores is set differently, and a decoding start position for each of the plurality of decoding cores is set to have an integer multiple of R / M based on the memory bank start row of the first decoding core. R is the number of rows constituting the memory area, and M is the number of the plurality of decoding cores.

유사 균등 분할, 서로소, 병렬 복호, 메모리 접근 충돌, 인터리버, 터보 부호, 요소 부호기, 요소 복호기, 메모리 뱅크 영역, 복호 코어 Pseudo-even division, mutually, parallel decoding, memory access collision, interleaver, turbo code, element encoder, element decoder, memory bank area, decoding core

Description

METHOD AND APPARATUS PARALLEL DECODING IN A MOBILE COMMUNICATION SYSTEM}

도 1은 종래 터보 부호화기의 구조를 보이고 있는 도면;1 is a view showing the structure of a conventional turbo encoder;

도 2는 종래 터보 부호화기 내의 인터리버 구조를 보이고 있는 도면;2 shows an interleaver structure in a conventional turbo encoder;

도 3은 종래 터보 부호화기 내의 인터리버 동작을 보이고 있는 도면;3 illustrates an interleaver operation in a conventional turbo encoder;

도 4는 종래 터보 부호화기 내의 인터리버에서 출력 순서를 보이고 있는 도면;4 is a diagram illustrating output order in an interleaver in a conventional turbo encoder;

도 5 종래 터보 복호화기의 구조를 보이고 있는 도면;5 shows the structure of a conventional turbo decoder;

도 6 종래 터보 복호기 내의 인터리버 동작에 따른 메모리 접근 충돌을 보이고 있는 도면;6 illustrates a memory access collision due to an interleaver operation in a conventional turbo decoder;

도 7은 본 발명의 제1실시 예에 따른 병렬 복호 동작의 일 예를 보이고 있는 도면;7 is a diagram showing an example of a parallel decoding operation according to the first embodiment of the present invention;

도 8은 본 발명의 제1실시 예에 따른 병렬 복호 동작의 다른 예를 보이고 있는 도면;8 is a diagram showing another example of a parallel decoding operation according to the first embodiment of the present invention;

도 9는 본 발명의 제1실시 예에서 메모리 충돌을 방지하기 위한 영역 선택의 일 예를 보이고 있는 도면;9 is a view showing an example of region selection for preventing a memory conflict in a first embodiment of the present invention;

도 10은 본 발명의 제1실시 예에 따른 복호 장치의 구성을 보이고 있는 도면;10 is a diagram showing the configuration of a decoding apparatus according to the first embodiment of the present invention;

도 11은 본 발명의 제1실시 예에서 요소 복호기에 의한 주소 생성 방법의 차이를 보이고 있는 도면;11 is a view showing a difference of an address generation method by an element decoder in a first embodiment of the present invention;

도 12는 본 발명의 유사 균등 분할의 예를 보이고 있는 도면;12 shows an example of similar equal division of the present invention;

도 13은 본 발명의 유사 균등 분할을 위한 알고리즘에 사용되는 파라미터에 대한 설명을 보이고 있는 도면;FIG. 13 shows a description of parameters used in an algorithm for similar equal division of the present invention; FIG.

도 14는 본 발명의 제1실시 예에 따른 메모리 균등 분배를 위한 제어 흐름을 보이고 있는 도면;14 is a diagram illustrating a control flow for memory equal distribution according to the first embodiment of the present invention;

도 15는 본 발명의 제2실시 예에 따른 메모리 균등 분배를 위한 제어 흐름을 보이고 있는 도면;15 is a diagram illustrating a control flow for memory equal distribution according to the second embodiment of the present invention;

도 16은 본 발명의 실시 예에 따른 메모리 균등 배분 방법을 종합적으로 설명한 제어 흐름을 보이고 있는 도면.FIG. 16 is a diagram illustrating a control flow in which a memory equalization method is comprehensively described according to an exemplary embodiment of the present invention. FIG.

본 발명은 이동 통신 시스템에서의 복호 방법 및 장치에 관한 것으로, 특히 이동 통신 시스템에서 복수개의 부호기를 병렬 동작시켜 부호화한 코드워드를 고속으로 복호하기 위한 방법 및 장치에 관한 것이다.BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a decoding method and apparatus in a mobile communication system, and more particularly, to a method and apparatus for rapidly decoding a codeword encoded by performing a plurality of coders in parallel in a mobile communication system.

일반적으로, 채널 부호를 사용하는 이동통신시스템은 점차 광 대역의 주파수를 차지하면서 고속의 데이터 통신을 제공할 수 있는 형태로 발전하고 있다. 이러한 고속의 데이터 서비스는 IEEE 및 3GPP, 3GPP2 등의 다양한 무선 통신 표준 규격 단체를 통해 다양한 표준화 작업에 의해 현실화되고 있다. 최근 3GPP에서는 LTE (Long Term Evolution) 시스템 규약을 통해 초고속 무선 데이터 규약을 제정있다. 따라서 고속의 데이터 서비스를 구현하기 위해서는 수신측에 고속으로 동작하는 채널 복호화기가 필요하다. 그러나 현재의 칩 제조 기술로는 하나의 복호 코어를 사용하여 LTE 기술을 지원하기 위한 고속 복호화를 구현하는 것이 현실적으로 불가능하다. 이에 따라 고속의 채널 복호화를 위해서는 병렬 복호 처리를 필요로 한다.In general, a mobile communication system using a channel code has developed into a form capable of providing high-speed data communication while occupying a wide frequency band. Such high-speed data services are being realized by various standardization work through various wireless communication standard specification organizations such as IEEE, 3GPP, and 3GPP2. Recently, 3GPP has established high-speed wireless data protocol through Long Term Evolution (LTE) system protocol. Therefore, in order to implement a high speed data service, a channel decoder that operates at a high speed on the receiving side is required. However, with the current chip manufacturing technology, it is practically impossible to implement high-speed decoding to support LTE technology using one decoding core. Accordingly, parallel decoding processing is required for fast channel decoding.

예컨대 터보 부호화기는 하나의 코드워드 생성에 복수개의 요소 부호화기(Constituent Encoder)가 존재하며, 각 요소 부호화기 사이에는 인터리버가 존재한다. 이에 대응한 복호화기는 복수개의 복호 코어(Decoder Core)로 구성된 요소 복호화기(Constituent Decoder)를 이용하여 수신한 코드워드를 병렬 복호 처리한다.For example, the turbo encoder has a plurality of elemental encoders (Constituent Encoder) to generate one codeword, there is an interleaver between each element encoder. The corresponding decoder performs parallel decoding processing on the received codeword using a Constituent Decoder composed of a plurality of decoder cores.

통상적으로 고속의 병렬 복호 처리를 위해서는 각각의 복호 코어가 동시에 데이터 메모리에 접근할 수 있어야 한다. 이를 위해 데이터 메모리를 복수개의 메모리 뱅크로 구성하는 것이 일반적이다. 그러나 두 개의 요소 부호화기 사이의 인터리버 동작에 의해 특정 요소 복호화기 내의 몇몇 서로 다른 복호 코어는 동시에 동일한 메모리 뱅크에 접근하는 일이 발생한다. 만일 메모리 접근으로 인한 충돌 시, 임의의 복호 코어의 메모리 접근을 지연시키는 방법은 전체 복호 동작에 있어 심각한 복호 시간 지연을 유발시킬 수 있다.In general, for fast parallel decoding processing, each decoding core must be able to access the data memory at the same time. To this end, it is common to organize the data memory into a plurality of memory banks. However, due to the interleaver operation between two element encoders, several different decoding cores in a specific element decoder can access the same memory bank at the same time. If there is a collision due to memory access, the method of delaying the memory access of any decoding core can cause a significant decoding time delay in the overall decoding operation.

이하 상술한 바에 대한 설명의 편의를 위해 3GPP를 지원하는 터보 부호(Turbo Code)를 기준으로 한다.In the following description, a turbo code supporting 3GPP is used for convenience of description of the above description.

도 1은 일반적인 3GPP를 지원하는 터보 부호화기(100)의 구조를 보이고 있다.
도 1을 참조하면, 터보 부호화기(100)에 의해 만들어진 코드워드는 1개의 시스티메틱 심볼(Systematic Symbol)(S1)과 2개의 요소 부호기(105, 107)에 의한 2개의 패리티 심볼(Parity Symbol)(P1, P2)로 구성된다. 각 요소 부호기(105, 107) 사이에는 인터리버(101)가 위치하여, 상기 두 개의 요소 부호기(105, 107)로 입력되는 심볼의 순서를 다르게 한다.1 illustrates a structure of a turbo encoder 100 supporting a general 3GPP.
Referring to FIG. 1, the codeword generated by the turbo encoder 100 includes two parity symbols by one systematic symbol S1 and two element encoders 105 and 107. It consists of (P1, P2). The interleaver 101 is positioned between the element encoders 105 and 107 so that the order of symbols inputted to the two element encoders 105 and 107 is different.

도 2는 종래 3GPP를 지원하는 터보 부호화기(100)를 구성하는 내부 인터리버(101)의 구조에 대한 일 예를 보이고 있다. 즉 도 2에서는 내부 인터리버(101)로 입력되는 정보의 순서에 대한 일 예를 보이고 있다.
도 2를 참조하면, 인터리버(101)는 R x C의 입력 심볼을 입력 받을 수 있다. 이때 상기 입력 받을 수 있는 입력 심볼들은 인터리버 인덱스 순서대로 들어온다. 만일 입력 심볼의 전체 길이 K가 R x C보다 작다면, K보다 큰 인터리버 인덱스에는 정보가 채워지지 않는다.2 shows an example of a structure of an internal interleaver 101 constituting a turbo encoder 100 supporting 3GPP. That is, FIG. 2 shows an example of the order of information input to the internal interleaver 101.
Referring to FIG. 2, the interleaver 101 may receive an input symbol of R × C. At this time, the input symbols that can be input come in the interleaver index order. If the total length K of the input symbol is less than R x C, no information is filled in the interleaver index greater than K.

도 3은 종래 3GPP를 지원하는 터보 부호화기(100)를 구성하는 내부 인터리버(101)에 의해 수행되는 인터리빙 동작의 일 예를 보이고 있다. 도 3에서는 인터리버(101)에 의해 두 단계 동작에 의해 인터리빙 동작이 수행되는 예를 보이고 있다.
도 3을 참조하면, 1단계에서 인터리버(101)는 3GPP에 정해진 규격에 의해 각각의 행 별로 각 행 내에서 열의 위치를 변경하는 일차 퍼뮤테이션 (Permutation)동작(301)을 수행한다. 그 후 2단계에서 인터리버(101)는 각각의 열 내에서 동일한 규칙에 의해 행의 순서를 변경하는 이차 퍼뮤테이션 동작(303)을 수행한다.
도 4는 종래 3GPP를 지원하는 터보 부호화기(100)를 구성하는 내부 인터리버(101)에 의해 심볼이 출력되는 예를 보이고 있다.
한편 도 4에 보이고 있는 바와 같이 심볼을 출력할 시에 정보가 채워지지 않는 영역(프루닝 영역)은 인터리빙에 따른 퍼뮤테이션 동작을 수행함으로써, 초기 입력 시의 위치로부터의 변경이 발생한다. 하지만 3GPP 규격에서는 상기 변경된 위치에 상응한 영역에서는 심볼의 출력을 지나치도록 정의하고 있다. 따라서 총 K개의 입력 심볼에 대해 인터리버는 총 K개의 출력 심볼을 생성한다.3 shows an example of an interleaving operation performed by the internal interleaver 101 constituting the turbo encoder 100 supporting the conventional 3GPP. 3 illustrates an example in which an interleaving operation is performed by the interleaver 101 by a two-step operation.
Referring to FIG. 3, in step 1, the interleaver 101 performs a primary permutation operation 301 for changing the position of a column in each row for each row according to a standard specified in 3GPP. Then, in step 2, the interleaver 101 performs the secondary permutation operation 303 to change the order of the rows by the same rule in each column.
4 shows an example in which a symbol is output by an internal interleaver 101 constituting a turbo encoder 100 supporting 3GPP.
On the other hand, as shown in FIG. 4, a region (pruning region) where information is not filled in at the time of outputting a symbol performs a permutation operation according to interleaving, whereby a change from a position at the time of initial input occurs. However, the 3GPP standard defines that the output of a symbol passes in a region corresponding to the changed position. Therefore, for a total of K input symbols, the interleaver generates a total of K output symbols.

다음으로 종래 3GPP를 지원하는 터보 부호화기에 대해 설명하도록 한다.
도 5는 종래 3GPP를 지원하는 터보 복호화기(500) 구조의 일 예를 보이고 있다.Next, a turbo encoder supporting the conventional 3GPP will be described.
5 shows an example of a structure of a turbo decoder 500 supporting 3GPP.

도 5를 참조하면, 입력된 각 코드워드는 하나의 시스티메틱 심볼(S1)과 두 개의 패리티 심볼, 즉 제1 패리티 심볼(P1)과 제2 패리티 심볼(P2)로 분리된다. 상기 시스티메틱 심볼(S1)과 제1 패리티 심볼(P1)은 제1 요소 복호기(501)로 입력된다. 상기 제1 요소 복호기(501)의 복호 동작에 의해 생성한 제1 외부 정보는 제2 요소 복호기(507)에 대해 시스티메틱 심볼과 같은 역할을 한다. 하지만 제2 요소 복호기(507)가 제1 외부 정보를 입력 받기 위해서는 인터리버(505)를 통해 인터리빙 동작이 수행되어야 한다. 따라서, 상기 제2 요소 복호기(507)는 상기 인터리버(505)에 의한 인터리빙 동작이 수행된 제1 외부정보와 제2 패리티 심볼(P2)을 입력으로 받는다. 그리고 상기 제2 요소 복호기(507)는 상기 인터리빙이 이루어진 제1 외부정보와 상기 제2 패리티 심볼(P2)에 대한 복호를 수행한다.Referring to FIG. 5, each input codeword is divided into one systematic symbol S1 and two parity symbols, that is, a first parity symbol P1 and a second parity symbol P2. The systematic symbol S1 and the first parity symbol P1 are input to the first element decoder 501. The first external information generated by the decoding operation of the first element decoder 501 serves as a systematic symbol for the second element decoder 507. However, in order for the second element decoder 507 to receive the first external information, an interleaving operation must be performed through the interleaver 505. Accordingly, the second element decoder 507 receives as input the first external information and the second parity symbol P2 on which the interleaving operation by the interleaver 505 is performed. The second element decoder 507 decodes the first external information on which the interleaving is performed and the second parity symbol P2.

상기 제2 요소 복호기(507)에 의해 생성된 제2 외부정보는 상기 제1 요소 복호기(501)로 전달된다. 이때 정보의 순서를 맞추기 위해 상기 제2 외부 정보에 대해서는 상기 인터리버(505)에 의한 인터리빙의 역 과정인 디인터리빙 동작이 디인터리버(503)에 의해 수행된다. 상기 제1 요소 복호기(501)는 상기 디인터리빙이 수행된 제2 외부정보를 이용하여 추가의 복호 동작을 수행한다.
상술한 바와 같은 동작은 터보 복호기 내에서 수 차례 반복될 것이며, 상기 터보 복호기는 상기 수 차례 반복에 의한 결과로써 수신된 신호의 복호 값을 결정한다.The second external information generated by the second element decoder 507 is transmitted to the first element decoder 501. At this time, the deinterleaver 503, which is a reverse process of interleaving by the interleaver 505, is performed by the deinterleaver 503 on the second external information in order to match the information. The first element decoder 501 performs an additional decoding operation by using the second external information on which the deinterleaving is performed.
The operation as described above will be repeated several times in the turbo decoder, which determines the decoding value of the received signal as a result of said several iterations.

그러면 상술한 3GPP 터보 부호의 부호 방법과 복호 방법에 대한 설명을 바탕으로 병렬 복호시 발생하는 메모리 접근 충돌의 문제점을 도 6을 통해 설명한다.Next, the problem of memory access collision occurring in parallel decoding will be described with reference to FIG. 6 on the basis of the description of the coding method and the decoding method of the 3GPP turbo code.

도 6은 종래 3GPP를 지원하는 터보 복호기가 복호를 위해 수행하는 제어 흐름을 보이고 있다. 즉 도 6에서는 터보 복호기를 구성하는 제1 요소 복호기(501)와 제2 요소 복호기(507)에 의한 동작 흐름을 보이고 있다. 또한 도 6에서는 첫 번째 순환 복호 과정(Cyclic Decoding Process)만을 나타내었다.
도 6을 참조하면, M개의 복호 코어(601-M)로 구성된 제1 및 제2 요소 복호기(501, 507)는 M개의 병렬 복호가 수행된다. 이때 고속의 병렬 복호를 위해 각 복호 코어들(601-1 내지 601-M)은 반드시 동시에 메모리 접근이 가능하여야 한다. 따라서 메모리는 동시에 복호 코어 개수 이상의 접근이 가능한 메모리 뱅크 영역으로 구분되어야 한다.6 shows a control flow performed by a conventional turbo decoder supporting 3GPP for decoding. That is, FIG. 6 shows the operation flow by the first element decoder 501 and the second element decoder 507 constituting the turbo decoder. 6, only the first cyclic decoding process is shown.
Referring to FIG. 6, M parallel decoding is performed on the first and second element decoders 501 and 507 including M decoding cores 601 -M. At this time, each of the decoding cores (601-1 to 601-M) must be able to access the memory at the same time for high speed parallel decoding. Therefore, the memory should be divided into memory bank areas which can be accessed more than the number of decoding cores at the same time.

도 6에서 시스티메틱 심볼(S1)과 제1 및 제2 패리티 심볼(P1, P2)에 대한 각각의 메모리는 M개의 뱅크 영역으로 나뉘어졌다고 가정한다. 그러면 상기 제1 요소 복호기(501)의 각 복호 코어(601-1 내지 601-M)는 각각의 메모리 내의 데이터를 동시에 읽어 개별적인 복호를 수행한다. 이후 상기 제1 요소 복호기(501)에 의해 생성된 제1 외부정보가 순서대로 M개의 메모리 영역에 나뉘어 저장된다.
제2 요소 복호기(507)는 복호 동작을 위해, 외부정보1'의 순서로 외부정보1을 불러들인다. 이와 같은 상황에서 상기 제2 요소 복호기(507) 내 각각의 서로 다른 복호 코어가 동시에 제1 외부정보가 저장된 동일한 메모리 영역에 접근하는 메모리 충돌 현상이 발생한다. 즉 상기 제2 요소 복호기(507)의 제1 복호 코어(601-1)와 제2 복호 코어(601-2)는 두 번째 외부정보1' 심볼을 모두 제1 외부정보의 두 번째 메모리 영역에서 읽어 들였으므로, 메모리 충돌 현상이 발생된 것이다. 이하 이러한 메모리 충돌 현상을 ‘메모리 충돌(605)’이라 칭하기로 한다.In FIG. 6, it is assumed that each memory for the systematic symbol S1 and the first and second parity symbols P1 and P2 is divided into M bank regions. Then, each of the decoding cores 601-1 to 601-M of the first element decoder 501 simultaneously reads data in each memory and performs individual decoding. Thereafter, the first external information generated by the first element decoder 501 is stored in M memory regions in order.
The second element decoder 507 imports the external information 1 in the order of the external information 1 'for the decoding operation. In such a situation, a memory collision phenomenon occurs in which different decoding cores in the second element decoder 507 simultaneously access the same memory area in which the first external information is stored. That is, the first decoding core 601-1 and the second decoding core 601-2 of the second element decoder 507 read both the second external information 1 ′ symbols from the second memory area of the first external information. As a result, a memory conflict has occurred. Hereinafter, such a memory conflict will be referred to as a memory conflict 605.

이와 같은 메모리 충돌 현상은 각 요소 부호기 사이에 인터리버가 있기 때문이다. 따라서 인터리버의 설계에 의해 메모리 충돌 현상을 해결하려는 다양한 노력과 구현 방법이 논문 등을 통해 소개되었다.
하지만 인터리버의 설계에 의해서는 특정 입력 심볼 개수에 대한 메모리 충돌 현상을 해결할 수 있을 뿐, 3GPP와 같이 특정 개수를 벗어나는 입력 심볼에 대해서는 메모리 충돌 현상이 발생할 수 있다. 또한 논문에서도 일반적인 인터리버에 의한 해결 방법을 제시함으로써 구현상의 복잡함을 해결할 수가 없다.This memory conflict is due to the presence of an interleaver between each element encoder. Therefore, various efforts and implementation methods to resolve the memory conflict by the design of the interleaver were introduced in the paper.
However, the design of the interleaver can solve the memory collision phenomenon for a specific number of input symbols, and a memory conflict may occur for an input symbol beyond a certain number such as 3GPP. In addition, the paper does not solve the complexity of the implementation by suggesting a solution by a general interleaver.

따라서 본 발명의 목적은 병렬 부호화 방식을 사용하는 이동 통신 시스템에서 임의의 입력 심볼 개수에 대해 메모리 충돌을 방지하기 위한 복호화 방법 및 장치를 제공함에 있다.Accordingly, an object of the present invention is to provide a decoding method and apparatus for preventing a memory collision for any number of input symbols in a mobile communication system using a parallel coding scheme.

본 발명의 다른 목적은 병렬 부호화 방식을 사용하는 이동 통신 시스템에서 메모리를 효율적으로 분배하여 메모리 충돌을 방지하기 위한 복호화 방법 및 장치를 제공함에 있다. Another object of the present invention is to provide a decoding method and apparatus for preventing memory collision by efficiently distributing memory in a mobile communication system using a parallel coding scheme.

본 발명의 다른 목적은 병렬 복호를 사용하는 이동 통신 시스템에서 복잡도를 낮출 수 있는 복호화 방법 및 장치를 제공함에 있다.Another object of the present invention is to provide a decoding method and apparatus for reducing complexity in a mobile communication system using parallel decoding.

본 발명의 실시 예에 따른 방법은, 이동 통신 시스템에서 복수의 부호화기의 병렬 부호화에 의해 생성된 코드워드를 복수의 복호 코어를 이용하여 복호하는 복호화기의 복호 방법에 있어서, 인터리빙을 위한 메모리 영역을 상기 복수의 복호 코어 별로 균등하게 분할하는 과정과, 상기 복수의 복호 코어 각각이 복호를 위해 접근하는 메모리 뱅크의 시작 위치가 서로 상이하도록 상기 복수의 복호 코어 각각에 대한 복호 시작 위치를 서로 다르게 설정하는 과정을 포함하며, 상기 복수의 복호 코어 각각에 대한 복호 시작 위치는 첫 번째 복호 코어의 메모리 뱅크 시작 행을 기준으로 R/M의 정수 배를 가지도록 설정되며, 상기 R은 상기 메모리 영역을 구성하는 행의 수이고, 상기 M은 상기 복수의 복호 코어의 개수임을 특징으로 한다.According to an embodiment of the present invention, in a decoder decoding method for decoding codewords generated by parallel encoding of a plurality of encoders in a mobile communication system using a plurality of decoding cores, a memory area for interleaving is provided. Dividing the process evenly for each of the plurality of decoding cores, and setting decoding start positions for each of the plurality of decoding cores differently so that the starting positions of the memory banks to which each of the plurality of decoding cores approaches for decoding are different from each other. And a decoding start position for each of the plurality of decoding cores is set to have an integer multiple of R / M based on the memory bank start row of the first decoding core, wherein R constitutes the memory area. The number of rows, M is the number of the plurality of decoding cores.

본 발명의 실시 예에 따른 다른 방법은; 이동 통신 시스템에서 복수의 부호화기의 병렬 부호화에 의해 생성된 코드워드를 복수의 복호 코어를 이용하여 복호하는 복호화기의 복호 방법에 있어서, 상기 복수의 복호 코어 각각에서 복호 처리하는 데이터 양을 상기 복수의 복호 코어 각각의 수에 따라 메모리의 행의 수 이내로 최대한 균등하게 분배하는 제 1과정과, 상기 복수의 복호 코어 각각 별로, 동일 위치의 서로 다른 메모리 영역에서 상대적으로 상이한 메모리 접근 시작 시점을 갖도록 복호 시작 시점을 설정하여 메모리 충돌을 방지하는 제 2과정을 포함하며, 상기 복수의 복호 코어 각각에 대한 복호 시작 시점은 첫 번째 복호 코어의 메모리 뱅크 시작 행을 기준으로 R/M의 정수 배를 가지도록 설정되며, 상기 R은 상기 메모리 영역을 구성하는 행의 수이고, 상기 M은 상기 복수의 복호 코어의 개수임을 특징으로 한다.Another method according to an embodiment of the present invention comprises: A decoding method of a decoder which decodes codewords generated by parallel encoding of a plurality of encoders in a mobile communication system using a plurality of decoding cores, the method comprising: decoding the amount of data decoded by each of the plurality of decoding cores. A first process of distributing as evenly as possible within the number of rows of the memory according to the number of decoding cores, and the decoding start to have relatively different memory access start points in different memory regions of the same position for each of the plurality of decoding cores And setting a time point to prevent memory collision, wherein the decoding start time point of each of the plurality of decoding cores is set to have an integer multiple of R / M based on the memory bank start row of the first decoding core. R is the number of rows constituting the memory area, and M is the plurality of decoding codes. That the number of features.

본 발명의 실시 예에 따른 장치는, 이동 통신 시스템에서 복호 장치에 있어서, 복수의 복호 코어를 구비하여 수신된 부호화 데이터를 복호하는 적어도 하나의 요소 복호기와, 인터리빙을 위한 메모리 영역을 상기 복수의 복호 코어 별로 균등하게 분할하고, 상기 복수의 복호 코어 각각이 복호를 위해 접근하는 메모리 뱅크의 시작 위치가 서로 상이하도록 상기 복수의 복호 코어 각각에 대한 복호 시작 위치를 서로 다르게 설정하는 주소 제어기를 포함하며, 상기 복수의 복호 코어 각각에 대한 복호 시작 위치는 첫 번째 복호 코어의 메모리 뱅크 시작 행을 기준으로 R/M의 정수 배를 가지도록 설정되며, 상기 R은 상기 메모리 영역을 구성하는 행의 수이고, 상기 M은 상기 복수의 복호 코어의 개수임을 특징으로 한다.An apparatus according to an embodiment of the present invention is a decoding apparatus in a mobile communication system, comprising: at least one element decoder having a plurality of decoding cores to decode received coded data, and a plurality of decoders to store a memory area for interleaving; And an address controller for dividing evenly by core and setting decoding start positions for each of the plurality of decoding cores differently so that start positions of memory banks to which each of the plurality of decoding cores approaches for decoding are different from each other. The decoding start position for each of the plurality of decoding cores is set to have an integer multiple of R / M based on the memory bank start row of the first decoding core, wherein R is the number of rows constituting the memory area, M is the number of the plurality of decoding cores.

본 발명의 실시 예에 따른 다른 장치는; 이동 통신 시스템에서 복호 장치에 있어서, 복수의 복호 코어를 구비하여 수신된 부호화 데이터를 복호하는 적어도 하나의 요소 복호기와, 상기 복수의 복호 코어 각각에서 복호 처리하는 데이터 양을 상기 복수의 복호 코어 각각의 수에 따라 메모리의 행의 수 이내로 최대한 균등하게 분배하고, 상기 복수의 복호 코어 각각 별로, 동일 위치의 서로 다른 메모리 영역에서 상대적으로 상이한 메모리 접근 시작 시점을 갖도록 복호 시작 시점을 설정하여 메모리 충돌을 방지하는 주소 제어기를 포함하며, 상기 복수의 복호 코어 각각에 대한 복호 시작 시점은 첫 번째 복호 코어의 메모리 뱅크 시작 행을 기준으로 R/M의 정수 배를 가지도록 설정되며, 상기 R은 상기 메모리 영역을 구성하는 행의 수이고, 상기 M은 상기 복수의 복호 코어의 개수임을 특징으로 한다.Another apparatus according to an embodiment of the present invention includes: A decoding apparatus in a mobile communication system, comprising: at least one element decoder having a plurality of decoding cores, and a data amount to be decoded in each of the plurality of decoding cores; It distributes as evenly as possible within the number of rows of memory according to the number, and sets the decoding start time point to have relatively different memory access start time points in different memory areas of the same position for each of the plurality of decoding cores, thereby preventing memory conflicts. And a decoding start time point of each of the plurality of decoding cores is set to have an integer multiple of R / M based on a memory bank start row of a first decoding core, wherein R is the memory area. The number of rows constituting, wherein M is the number of the plurality of decoding cores do.

삭제delete

이하 첨부된 도면을 참조하여 본 발명의 실시 예를 설명하기로 한다.Hereinafter, embodiments of the present invention will be described with reference to the accompanying drawings.

하기에서 본 발명을 설명함에 있어 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략할 것이다. 그리고 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.In the following description of the present invention, a detailed description of known functions and configurations incorporated herein will be omitted when it may make the subject matter of the present invention rather unclear. The following terms are defined in consideration of the functions of the present invention, and may be changed according to the intentions or customs of the user, the operator, and the like. Therefore, the definition should be based on the contents throughout this specification.

본 발명의 실시 예에서는 실제 구현 가능한 낮은 복잡도 요건을 충족하면서 동시에 메모리 충돌을 방지하는 방안을 마련하고자 한다. 예컨대 본 발명의 실시 예에서는 터보 부호와 같은 연결 부호(Concatenated Code)를 병렬 복호화하는 이동 통신 시스템에서, 요소 부호기들 사이의 인터리버 동작에 의한 메모리 접근 충돌을 방지하면서도, 병렬 처리 복호기의 계산 능력에 따라 병렬 처리 개수의 자유도를 제공하도록 한다.In an embodiment of the present invention, a method of preventing a memory conflict while satisfying a low complexity requirement that can be actually implemented is provided. For example, according to an embodiment of the present invention, in a mobile communication system that parallel-decodes a concatenated code such as a turbo code, while preventing a memory access collision due to an interleaver operation between element coders, Provide degrees of freedom for parallel processing.

이하에서는 인터리버 구조 내에 프루닝 영역이 없는 경우에 메모리 충돌이 발생하지 않는 병렬 복호화 장치 및 방법을 설명할 것이다.Hereinafter, a parallel decoding apparatus and method in which a memory collision does not occur when there is no pruning region in the interleaver structure will be described.

이하 설명될 본 발명의 실시 예에서는 행 방향으로 입력된 데이터를 각 행 내에서 퍼뮤테이션한 후, 열 방향으로의 각 행들에 대한 퍼뮤테이션을 수행하는 2 단계 동작을 거쳐 열 방향으로 데이터가 출력되는 인터리버의 구조를 고려한다. 만약 열 방향으로 행들에 대해 수행하는 퍼뮤테이션 동작이 각각의 열에서 임의의 규칙으로 진행된다면, 본 발명에서의 목적 중 하나인 특정 값 이하의 임의의 병렬 복호 특성을 잃게 된다.In an embodiment of the present invention to be described below, the data input in the row direction is permutated in each row, and then data is output in the column direction through a two-step operation of performing permutation on each row in the column direction. Consider the structure of the interleaver. If the permutation operation performed on the rows in the column direction proceeds with an arbitrary rule in each column, any parallel decoding characteristic below a certain value, which is one of the objectives of the present invention, is lost.

이하에서 설명되는 제1실시 예는 인터리버 구조 내에 프루닝 영역이 없는 경우의 메모리 충돌이 없는 병렬 복호 동작이다. 이는 인터리버의 크기 R x C가 전체 입력 정보심볼 개수 K와 동일한 경우를 의미한다.The first embodiment described below is a parallel decoding operation without a memory collision when there is no pruning region in the interleaver structure. This means that the size R x C of the interleaver is equal to the total number of input information symbols K.

도 7은 본 발명의 제1실시 예에 따른 병렬 복호 동작을 보이고 있다. 예컨대 도 7에서는 인터리버 주소의 출력 값을 읽는 일 예를 보이고 있다. 여기서 각 행은 별도의 메모리 뱅크를 의미하며, 각 열은 각 복호 코어의 데이터 인덱스를 의미한다. 도 7에서 메모리에 나타낸 숫자(1 내지 n_M)는 인터리버 동작이 완료되어 각각의 복호 코어가 데이터를 읽어가는 순서를 의미한다. 실제로 데이터 주소는 도 3에서 나타낸 바와 같이 두 단계에 걸친 퍼뮤테이션 과정에 의해 순서가 바뀌어지나, 인터리버 동작이 수행된 후 서로 다른 행의 데이터가 동일한 행으로 섞이지 않으므로, 메모리 충돌 관점에서는 의미가 없게 되어 이에 대한 표현은 생략한다. 7 shows a parallel decoding operation according to the first embodiment of the present invention. For example, Figure 7 shows an example of reading the output value of the interleaver address. Here, each row represents a separate memory bank, and each column represents a data index of each decoding core. The numbers 1 to n_M shown in the memory in FIG. 7 refer to the order in which the decoding cores read data after the interleaver operation is completed. In fact, the data addresses are reversed by a two-step permutation process as shown in FIG. 3, but since the data of different rows are not mixed into the same rows after the interleaver operation is performed, it becomes meaningless from a memory conflict point of view. This expression is omitted.

도 7은 각각의 행이 별도의 메모리 영역으로 구성되는 경우, 행의 수 R보다 작거나 같은 정수 M에 의한 병렬 처리를 하기 위한 방법이다. 도 7에서 각각의 복호 코어 데이터 영역의 크기(701, 703, 705)는 서로 비슷한 크기도 선택될 수 있다. 만일 그 크기가 서로 크게 다르면, 복호 코어 별로 계산 량이 달라지게 된다. 이는 전체 복호에 필요한 시간은 가장 늦게 처리가 완료된 복호 코어에 의해 결정되므로, 가장 비슷한 크기의 선택이 중요하다. 또한 각 복호 코어의 데이터 시작 위치(707, 709, 711)는 모두 서로 다른 행 즉, 서로 다른 메모리 뱅크에서 시작되는 조건이 만족되어야 한다.
도 7에 의해 보이고 있는 바와 같이 각 복호 코어의 시작 위치(707, 709, 711)에 해당하는 행이 서로 다르게 설정되면, 각 복호 코어 영역의 동일 데이터 인덱스는 항상 다른 행에 위치한다. 이는 매 시각 각 복호 코어는 서로 다른 메모리 뱅크를 선택함을 의미한다.FIG. 7 illustrates a method for performing parallel processing by an integer M that is less than or equal to the number of rows R when each row is configured as a separate memory area. In FIG. 7, sizes 701, 703, and 705 of respective decoding core data areas may be selected to have similar sizes. If the sizes differ greatly from one another, the calculation amount is different for each decoding core. Since the time required for total decoding is determined by the decoding core that is processed at the latest, the selection of the most similar size is important. In addition, the data start positions 707, 709, and 711 of each decoding core must satisfy conditions starting from different rows, that is, different memory banks.
As shown in FIG. 7, when the rows corresponding to the start positions 707, 709, and 711 of each decoding core are set differently, the same data index of each decoding core region is always located in a different row. This means that each time each decoding core selects a different memory bank.

만일 복호 코어의 수 M이 인터리버 행의 개수 R의 약수인 경우, 메모리 영역의 구분은 R/M개만 필요함을 쉽게 알 수 있다. 즉 메모리 충돌을 방지하기 위해 각 행을 R/M 단위로 묶은 후 이들을 별도의 메모리 영역으로 설정하고, 코어 별로 서로 다른 메모리 영역을 복호 시작점으로 설정할 수 있다. 단지 메모리 영역의 시작 위치는 첫 번째 행을 기준으로 R/M 정수 배만큼 더해진 위치에서 시작되어야 한다. 예컨대 도 8에서 보이고 있는 바와 같이 (R/M) = 2인 경우, 두 번째 메모리 영역 위치는 3=(1 + 2(R/M))에 상응한 위치이어야 한다.If the number M of the decoding cores is a divisor of the number R of the interleaver rows, it can be easily seen that only R / M is required to distinguish the memory regions. That is, in order to prevent memory conflicts, each row may be grouped in R / M units, and these may be set as separate memory areas, and different memory areas may be set as decoding start points for each core. Only the starting position of the memory area should start at the position added by R / M integer times with respect to the first row. For example, as shown in FIG. 8, when (R / M) = 2, the second memory area location should be a position corresponding to 3 = (1 + 2 (R / M)).

도 7과 도 8에서는 제2 요소 복호기의 각 복호 코어의 영역을 나누는 방법을 제안하고 있다.7 and 8 propose a method of dividing an area of each decoding core of the second element decoder.

도 9는 본 발명의 제1실시 예에서 제1 요소 복호기의 메모리 충돌을 방지하기 위한 영역 선택 예를 보이고 있다. 도 9와 같이 제1 요소 복호기는 행 방향으로 데이터를 읽는다. 따라서 서로 다른 메모리 영역의 임의의 위치에서 각 복호 코어의 데이터 영역에 대한 시작 위치가 설정되면, 메모리 충돌을 방지할 수 있다. 뿐만 아니라 특정 시스템에서 요구하는 메모리 영역 수와 복호 코어의 수에 대해 제2 요소 복호기에서의 메모리 충돌을 방지하였다면, 제1 요소 복호기에서의 메모리 충돌 역시 방지할 수 있다.FIG. 9 shows an example of region selection for preventing memory collision of the first element decoder in the first embodiment of the present invention. As illustrated in FIG. 9, the first element decoder reads data in a row direction. Therefore, when a start position for the data region of each decoding core is set at an arbitrary position in different memory regions, memory collision can be prevented. In addition, if the memory collision in the second element decoder is prevented with respect to the number of memory regions and the number of decoding cores required by a specific system, the memory collision in the first element decoder can be prevented.

도 10은 본 발명의 제1실시 예에 따라 메모리 충돌을 방지하기 위한 메모리 영역 선택을 바탕으로 하는 병렬 복호 시스템에 대한 장치 구성을 보이고 있다. 즉 도 10에서는 본 발명의 제1실시 예에 따른 복호 장치(1000)를 보이고 있다.
도 10을 참조하면, 주소 생성기(1010)는 각 요소 복호기(1020)의 동작에 필요한 외부 정보를 외부정보 저장기(1030)로부터 읽고 쓰는 주소를 제공한다. 상기 주소 생성기(1010)는 인터리버(1011), 디인터리버(1013), 영역 분할기(1015)로 구성되었다. 상기 영역 분할기(1015)는 각각의 복호 코어(1020-1 내지 1020-M)가 동작하는 데이터의 영역을 제공한다. 실제 각 메모리 주소는 인터리버(1011) 혹은 디인터리버(1013)를 통해 생성된다.FIG. 10 is a block diagram of a parallel decoding system based on memory area selection for preventing memory collision according to the first embodiment of the present invention. That is, FIG. 10 shows a decoding apparatus 1000 according to the first embodiment of the present invention.
Referring to FIG. 10, the address generator 1010 provides an address that reads and writes external information required for the operation of each element decoder 1020 from the external information store 1030. The address generator 1010 includes an interleaver 1011, a deinterleaver 1013, and an area divider 1015. The area divider 1015 provides an area of data on which each of the decoding cores 1020-1 through 1020 -M operates. The actual memory addresses are generated through the interleaver 1011 or the deinterleaver 1013.

삭제delete

상기 요소 복호기(1020)가 제1 요소 복호기로 동작할 경우, 각 복호 코어(1020-1 내지 1020-M)는 순차적으로 상기 외부정보 저장기(1030)의 데이터를 불러 들여 복호한 후 다시 순차적으로 외부정보 저장기(1030)에 저장한다. 상기 요소 복호기(1020)가 제2 요소 복호기로 동작할 경우, 상기 요소 복호기(1020)는 인터리버 동작으로 얻어진 순서로 외부정보 저장기(1030)의 데이터를 불러 들여 복호를 수행한다.
모든 복호 코어(1020-1 내지 1020-M)의 복호 동작이 완료되면, 각 복호 코어는 동시에 제2 요소 복호기에 의해 생성된 제2 외부정보를 순차적으로 출력한다. 이때 상기 외부정보 저장기(1030)에는 디인터리버 주소에 의해 얻어진 주소에 대응하여 데이터를 저장한다.When the element decoder 1020 operates as a first element decoder, each of the decoding cores 1020-1 through 1020 -M sequentially loads and decodes the data of the external information storage unit 1030 and then sequentially again. Stored in the external information storage unit 1030. When the element decoder 1020 operates as the second element decoder, the element decoder 1020 reads data from the external information storage unit 1030 and performs decoding in the order obtained by the interleaver operation.
When the decoding operations of all the decoding cores 1020-1 to 1020-M are completed, each decoding core sequentially outputs second external information generated by the second element decoder at the same time. At this time, the external information storage unit 1030 stores data corresponding to the address obtained by the deinterleaver address.

도 11은 본 발명의 제1실시 예에 따른 요소 복호기 별 주소 생성 방법에 있어서의 차이를 보이고 있다. 도 11에서의 복호 장치(1100)는 하나의 예를 보인 것으로 등가적으로 제1 요소 복호기(1110)를 직접 외부정보 저장기(1130)와 연결하고, 제2 요소 복호기(1120)에 인터리버(1140)와 디인터리버(1150)를 제공하여, 메모리 충돌을 방지할 수 있게 된다.11 shows a difference in the method for generating an address for each element decoder according to the first embodiment of the present invention. The decoding device 1100 of FIG. 11 shows an example, and equivalently connects the first element decoder 1110 directly with the external information store 1130, and the interleaver 1140 to the second element decoder 1120. ) And the deinterleaver 1150 to prevent memory conflicts.

도 12는 본 발명의 제1실시 예에 따라 R x C 크기를 가지는 인터리버에서 메모리 충돌을 방지하기 위한 각 복호 코어의 데이터 영역을 보이고 있다. 즉 도 12에서는 M개의 복호 코어로 병렬 처리함에 있어 유사적으로 균등한 크기 배분을 위한 방법을 나타내었다. 본 발명에서는 도 12에 나타낸 바와 같이 각 복호 코어에 의한 데이터 영역들(1201 내지 1207)을 유사적으로 균등하게 분배하여야 한다. 단지 데이터 영역들(1201 내지 1207)을 유사적으로 균등하게 분배하기 위해서는 각 복호 코어에서 첫 번째 데이터의 행 위치는 서로 다르다는 조건을 만족해야 한다.12 illustrates a data area of each decoding core for preventing memory collision in an interleaver having a size of R × C according to the first embodiment of the present invention. 12 illustrates a method for similarly equal size distribution in parallel processing with M decoding cores. In the present invention, as shown in Fig. 12, the data areas 1201 to 1207 by each decoding core should be similarly distributed evenly. In order to distribute the data areas 1201 to 1207 similarly and equally only, the condition that the row positions of the first data in each decoding core are different from each other must be satisfied.

본 발명의 유사 균등 배분의 방법을 설명하기 앞서 몇 가지 파라미터를 미리 정의하면 아래와 같다.Before describing the method of similar equal distribution of the present invention, some parameters are defined in advance.

상기 <수학식1>에서 m은 전체 인터리버의 크기를 복호 코어 M개로 나누었을 때, 각 복호 코어당 할당되는 정보의 개수를 의미한다. 상기 <수학식 2>에서 L은 각 복호 코어(M)에 대해 할당된 정보를 구성하는 열(C)의 개수를 의미한다.
상기 <수학식 3>에서 D는 각 복호 코어(M)에 할당된 정보가 열의 정수 배를 제외하고 몇 개의 정보로 구성되는 지를 의미한다. 마지막으로 상기 <수학식 4>에서 S는 상기 <수학식 1>에 의해 코어 별로 균등히 나눈 후 남은 정보의 개수를 의미한다.In Equation 1, m denotes the number of information allocated to each decoding core when the size of the entire interleaver is divided by the decoding core M. In Equation 2, L means the number of columns C constituting the allocated information for each decoding core (M).
In Equation 3, D denotes how many pieces of information are allocated to each decoding core M except for integer multiples of columns. Lastly, in Equation 4, S denotes the number of remaining information after dividing evenly for each core by Equation 1.

도 13은 앞에서 수학식에 의해 정의한 각 기호의 의미를 보이고 있다. 즉 도 13에서 맨 마지막에 Z(1301)로 표현한 하나의 정보는 상기 <수학식 4>에 표현된 남은 정보가 포함될 경우를 의미한다. 예컨대 최대한 균등 배분을 실행할 경우, 총 M개의 복호 코어 중 S개의 복호 코어가 검정색 부분을 가지게 되며, M-S개의 복호 코어는 검정색 부분이 없게 된다. 이때 <수학식 4>에 의해 S는 M보다 작거나 같게 된다. 따라서 최대 균등 배분에 의해서는 S개의 복호 코어는 (R x L + D + 1)의 데이터 영역을 가지게 되며, M-S개의 복호 코어는 (R x L + D)의 데이터 영역을 갖게 된다.
이는 하기 <수학식 5>에 의해 설명될 수 있다.13 shows the meaning of each symbol defined by the above equation. That is, one piece of information represented by Z 1301 at the end of FIG. 13 refers to a case in which the remaining information represented by Equation 4 is included. For example, when the most even distribution is performed, the S decoding cores of the total M decoding cores have black portions, and the MS decoding cores have no black portions. At this time, according to Equation 4, S is less than or equal to M. Therefore, according to the maximum equal distribution, the S decoding cores have a data area of (R x L + D + 1), and the MS decoding cores have a data area of (R x L + D).
This can be explained by Equation 5 below.

이하 앞에서 <수학식 1> 내지 <수학식 4>에 의해 정의된 기호를 토대로 각 복호 코어가 모두 서로 다른 열에서 시작하는 유사 균등 배분의 방법을 두 가지 실시 예로써 설명한다.
첫 번째 실시 예는 균등 분배로부터 중간 코어의 윈도우 사이즈를 늘려가는 방법이며, 두 번째 실시 예는 균등 분배로부터 중간 코어의 윈도우 사이즈를 줄여가는 방법이다. 이후 윈도우 크기는 각 코어가 복호해야 할 데이터 크기를 의미한다.Hereinafter, a method of similar equal distribution, in which each decoding core starts in different columns, will be described as two embodiments based on the symbols defined by Equations 1 to 4 above.
The first embodiment is a method of increasing the window size of an intermediate core from an even distribution, and the second embodiment is a method of reducing the window size of an intermediate core from an even distribution. The window size then refers to the data size each core needs to decode.

도 14는 본 발명의 제1실시 예에 따른 메모리 균등 분배를 위한 제어 흐름을 보이고 있다.
도 14를 참조하면, 1401단계에서 앞에서 정의된 <수학식>을 기반으로 파라미터 L, D, S를 계산한다. 그 후 1403단계에서 각 복호 코어의 윈도우 크기 W(i)를 모두 (R x L + D)로 설정한다. 이때, i = 1, 2, 3......M이며, M은 복호 코어의 개수이다.
1405단계에서 하기 두 개의 비교 구문에서 사용될 변수 W_1에 W(1)를 저장한다. 상기 1405 단계는 모든 동작을 수행한 후에, W(1)의 값이 최초의 W(1)의 값과 동일해져서는 안됨을 표시하기 위함이다. 이는 메모리 충돌 회피를 위해 W(1)의 크기를 변경했는데, 맨 마지막 동작(남은 비트를 맨 처음과 맨 마지막 윈도우에 배분하는 동작)에 의해 크기가 다시 처음과 같아진다면, 메모리 충돌이 발생하기 때문이다. 14 is a flowchart illustrating a control for equal distribution of memory according to a first embodiment of the present invention.
Referring to FIG. 14, in operation 1401, parameters L, D, and S are calculated based on Equation defined above. Thereafter, in step 1403, the window sizes W (i) of each decoding core are all set to (R x L + D). At this time, i = 1, 2, 3 ...... M, and M is the number of decoding cores.
In operation 1405, W (1) is stored in the variable W_1 to be used in the following two comparison statements. Step 1405 is to indicate that after performing all operations, the value of W (1) should not be equal to the value of the original W (1). This changed the size of W (1) to avoid memory collisions, because if the size is the same again by the last operation (distributing the remaining bits to the first and last window), a memory conflict occurs. to be.

D와 R의 최대 공약수를 A라고 할 때, 1407단계에서 B를 R/A로 정의한다. 단 D=0이면, A=R로 정의한다. 여기서 A는 서브세트(subset)의 개수를 의미하며, B는 각 서브세트(subset) 내의 요소(element) 개수를 의미한다.
1409단계에서 G를 -1로 정의한다. 상기 G는 코어 개수만큼의 파티션을 정의하기 위해 몇 개의 추가 서브 세트가 필요한지를 의미하는 파라미터이다. 상기 1409단계에서 상기 G값을 구하면, 1411단계에서 상기 G 가 '0'보다 큰지 확인한다.When the greatest common divisor of D and R is A, in step 1407, B is defined as R / A. However, if D = 0, it is defined as A = R. Here, A means the number of subsets, and B means the number of elements in each subset.
In step 1409, we define G as -1. G is a parameter indicating how many additional subsets are needed to define as many partitions as the number of cores. When the G value is obtained in step 1409, it is checked whether G is greater than '0' in step 1411.

상기 G는 '0' 또는 양의 정수가 되는데, G가 0 이면 추가의 서브 세트가 필요하지 않음을 의미하므로, 1417단계로 이동한다. 그렇지 않고 G가 0이 아니면, 즉 G가 양의 정수이면 1413단계에서 Q를 B로 설정한 후, 1415단계로 이동한다.G becomes '0' or a positive integer. If G is 0, it means that no additional subset is needed, and therefore, the process moves to step 1417. Otherwise, if G is not 0, that is, G is a positive integer, in step 1413, Q is set to B, and then the process moves to step 1415.

상기 1415단계에서는 W(Q) = W(Q) + 1, S = S - 1, Q = Q + B, G = G - 1로 설정한다. 그런 후 다시 1411단계로 진행하여 G가 0보다 크면 (G>0), 1413단계로 진행한다. 그렇지 않으면, 1417단계로 진행한다.In step 1415, W (Q) = W (Q) + 1, S = S-1, Q = Q + B, G = G-1 is set. Then go back to step 1411 and if G is greater than zero (G> 0), go to step 1413. Otherwise, go to step 1417.

상기 1411단계에서 G가 양의 정수 (G>0)인 조건을 만족하지 못하면, 1417단계로 진행하여 H를 [S/2], T를 [S/2]로 설정한다. 그런 후 상기 W(1)이 Step 2의 W(1)이 되지 않는 조건을 만족하는 다음의 두 가지 경우 중 임의의 하나를 선택한다.If G does not satisfy the condition that G is a positive integer (G> 0) in step 1411, the process proceeds to step 1417 to set H to [S / 2] and T to [S / 2]. Then, any one of the following two cases that satisfy the condition that W (1) does not become W (1) of Step 2 is selected.

Choice 1. W(1) = W(1) + H, W(M) = W(M) + T Choice 1.W (1) = W (1) + H, W (M) = W (M) + T

Choice 2. W(1) = W(1) + T, W(M) = W(M) + H Choice 2.W (1) = W (1) + T, W (M) = W (M) + H

일 예로 W(1)+H와 도 14의 W_1이 같은 경우, 상기 Choice 2가 반드시 선택되어야 하고, W(1)+T와 도 14의 W_1이 같은 경우, 상기 Choice 1이 반드시 선택되어야 한다. 그러나 W(1)+H 혹은 W(1)+T 모두 W_1과 동일하지 않다면, Choice 1과 Choice 2 중 어떠한 것을 선택하여도 된다. 도 14에는 이를 Random()함수로 선택하는 것으로 표기하였다. Random(1)은 0과 1을 각각 1/2의 확률로 출력하는 랜덤 함수를 의미한다.For example, when W (1) + H and W_1 of FIG. 14 are the same, Choice 2 must be selected. When W (1) + T and W_1 of FIG. 14 are the same, Choice 1 must be selected. However, if neither W (1) + H or W (1) + T is equal to W_1, either Choice 1 or Choice 2 may be selected. In FIG. 14, the random () function is selected. Random (1) means a random function that outputs 0 and 1 with 1/2 probability.

도 15는 본 발명의 제2실시 예에 따른 메모리 균등 분배를 위한 제어 흐름을 보이고 있다.
도 15를 참조하면, 1501단계에서 앞에서 정의한 <수학식>을 기반으로 파라미터 L, D, S를 계산한다. 그 후 1503단계에서 각 복호 코어의 윈도우 크기 W(i)를 모두 (R x L + D)로 설정한다. 이때, i = 1, 2, 3......M이며, M은 복호 코어의 개수이다. 1505단계에서는 하기 두 개의 비교 구문에서 사용될 변수 W_1에 W(1)를 저장한다.15 shows a control flow for equal distribution of memory according to the second embodiment of the present invention.
Referring to FIG. 15, in operation 1501, parameters L, D, and S are calculated based on Equation defined above. Thereafter, in step 1503, all window sizes W (i) of each decoding core are set to (R x L + D). At this time, i = 1, 2, 3 ...... M, and M is the number of decoding cores. In step 1505, W (1) is stored in the variable W_1 to be used in the following two comparison statements.

D와 R의 최대 공약수를 A라고 할 때, 1507단계에서 B를 R/A로 정의한다. 단 D가 0이면, A를 R로 정의한다. A는 서브세트(subset)의 개수를 의미하며, B는 각 서브 세트(subset) 내의 요소(element) 개수를 의미한다.
1509단계에서 G를 -1로 정의한다. 상기 G는 코어 개수만큼의 파티션을 정의하기 위해 몇 개의 추가 서브 세트가 필요한지를 의미하는 파라미터이다. 상기 1511단계에서 G가 0이면, 추가의 서브 세트가 필요하지 않음을 의미하므로, 1517단계로 이동한다. 하지만 G가 0이 아니면, 1513단계로 진행하여 Q를 B로 설정한 후 1515단계로 진행한다.When the greatest common divisor of D and R is A, in step 1507, B is defined as R / A. Provided that if D is zero then A is defined as R; A means the number of subsets, and B means the number of elements in each subset.
In step 1509, we define G as -1. G is a parameter indicating how many additional subsets are needed to define as many partitions as the number of cores. If G is 0 in step 1511, it means that no additional subset is needed, and therefore, the process moves to step 1517. However, if G is not 0, go to step 1513, set Q to B, and proceed to step 1515.

상기 1515단계에서 W(Q) = W(Q) -1, S = S+1, Q = Q + B, G = G - 1를 설정한다. 그 후 다시 1511 단계로 진행하여 G가 양의 정수 (G>0) 이면, 1513단계로 진행한다. 하지만 G가 0이면, 1517단계로 진행한다.In step 1515, W (Q) = W (Q) -1, S = S + 1, Q = Q + B, G = G-1 is set. After that, the process proceeds to step 1511 again, and if G is a positive integer (G> 0), the process proceeds to step 1513. If G is 0, however, go to step 1517.

상기 1511단계에서 G가 양의 정수 (G>0)인 조건을 만족하지 못하면, H를 [S/2]로 설정하고, T를 [S/2]로 설정한다. 그 후 상기 W(1)이 Step 2의 W(1)이 되지 않는 조건을 만족하는 다음의 두 가지 경우 중 임의의 하나를 선택한다.If G does not satisfy the condition that G is a positive integer (G> 0) in step 1511, H is set to [S / 2] and T is set to [S / 2]. Thereafter, any one of the following two cases satisfying the condition that W (1) does not become W (1) of Step 2 is selected.

예컨대 W(1)+H와 도 15의 W_1가 같은 경우, 상기 Choice 2가 반드시 선택되어야 하고, W(1)+T와 도 15의 W_1과 같은 경우, 상기 Choice 1이 반드시 선택되어야 한다. 그러나 W(1)+H 혹은 W(1)+T 모두 W_1과 동일하지 않다면, Choice 1과 Choice 2 중 어떠한 것을 선택하여도 된다. 도 15에는 이를 Random()함수로 선택하는 것으로 표기하였다. Random(1)은 0과 1을 각각 1/2의 확률로 출력하는 랜덤 함수를 의미한다.For example, if W (1) + H and W_1 in FIG. 15 are the same, Choice 2 must be selected, and if W (1) + T and W_1 in FIG. 15, Choice 1 must be selected. However, if neither W (1) + H or W (1) + T is equal to W_1, either Choice 1 or Choice 2 may be selected. In FIG. 15, this is indicated by the Random () function. Random (1) means a random function that outputs 0 and 1 with 1/2 probability.

상술한 제 1 및 제 2실시 예에서의 동작에 따른 결과로 H와 T는 각각 R을 벗어나지 않게 된다. 이는 상기 1411단계 및 1511단계의 동작이 최대 R회 이내임을 상기하면 쉽게 알 수 있다. 따라서 본 발명의 실시 예에서 제안한 유사 균등 배분 방법에 의한 최대 편차는 R이내가 된다. 특히 1411단계 및 1511단계에서의 동작에 의해 복호 코어 2에서 복호 코어 M-1 사이에서의 편차는 1 이내가 됨을 알 수 있다.As a result of the operation in the above-described first and second embodiments, H and T do not leave R, respectively. This can be easily seen by recalling that the operations of steps 1411 and 1511 are within a maximum of R times. Therefore, the maximum deviation by the similar equal distribution method proposed in the embodiment of the present invention is within R. In particular, it can be seen that the deviation between the decoding core 2 and the decoding core M-1 is within 1 by the operations in steps 1411 and 1511.

도 16은 본 발명의 실시 예에 따른 메모리의 균등 배분 방법을 종합적으로 설명한 제어 흐름을 보이고 있다.
도 16을 참조하면, 1601단계에서는 인터리버의 크기를 넘지 않는 최대의 크기로 각 복호 코어의 윈도우 크기를 동일하게 초기화한다. 1603단계에서는 인터리버 크기에서 각 복호 코어의 윈도우 크기의 합을 뺀 값을 S로 설정한다. 그 후 1605단계에서 각 윈도우의 크기를 행의 수로 나눈 나머지를 D로 설정한 후 1607단계에서 복호 코어 1의 초기 윈도우 크기를 저장한다.
1609단계에서 D와 행의 수가 서로 소의 관계를 가지는 지를 확인한다. 만약 상기 D와 행의 수가 서로 소의 관계가 아니라면, 1611단계에서 몇 개의 그룹으로 나뉘는 지와 각 그룹 내에 몇 개의 요소가 있는지를 확인한다. 이때 각 요소는 서로 다른 행에서 시작하는 조건을 만족하여야 한다. 만일 D가 '0'인 경우 그룹을 행의 수로 설정하고, 그룹 내 요소는 하나만 있는 것으로 설정한다. FIG. 16 is a control flow diagram illustrating a method of equally distributing memory according to an exemplary embodiment of the present invention.
Referring to FIG. 16, in step 1601, the window size of each decoding core is initialized equally to the maximum size not exceeding the size of the interleaver. In step 1603, the value obtained by subtracting the sum of the window sizes of each decoding core from the interleaver size is set to S. Thereafter, in step 1605, the remainder obtained by dividing the size of each window by the number of rows is set to D. In step 1607, the initial window size of the decoding core 1 is stored.
In step 1609, it is determined whether D and the number of rows have a small relation with each other. If the number of D and the row is not a small relationship with each other, it is checked in step 1611 how many groups are divided and how many elements are in each group. Each element must satisfy the condition starting from different line. If D is '0', the group is set to the number of rows, and there is only one element in the group.

1613단계에서 복호 코어의 수와 요소의 수를 비교하여 몇 개의 그룹이 필요한지를 결정한다. 그 후 1615단계에서 필요한 그룹 내에서 마지막 요소에 윈도우 사이즈를 단위 크기만큼 증가 혹은 감소한다. 그리고 상기 증가 혹은 감소된 양을 S에서 빼게 된다. 상기 단위 크기는 행의 수를 메모리 뱅크의 수로 나눈 수이다.In step 1613, the number of decoding cores and the number of elements are compared to determine how many groups are needed. Thereafter, in step 1615, the window size is increased or decreased by the unit size in the last element in the required group. And the increased or decreased amount is subtracted from S. The unit size is the number of rows divided by the number of memory banks.

1617단계에서 상기 S를 2로 나누어 생긴 두 정수 값 각각을 맨 앞 복호 코어의 윈도우 크기와 맨 마지막 복호 코어의 윈도우 크기에 더한다. 이때 더한 이후 맨 앞 복호 코어의 윈도우 크기는 초기 복호 코어 1의 값과 동일하지 않아야 한다.In step 1617, the two integer values obtained by dividing S by 2 are added to the window size of the first decoding core and the window size of the last decoding core. At this time, the window size of the first decoding core after addition should not be equal to the value of the initial decoding core 1.

상술한 바와 같이 동작하는 본 발명은 서로 다른 행의 데이터가 동일한 행의 데이터로 섞이지 않는 조건을 만족하는 임의의 인터리버에 대해 간단한 방법으로 최대한 각 복호 코어에 동일한 크기의 윈도우를 만족하는 조건을 가능하게 하는 효과가 있다.The present invention operating as described above enables a condition that satisfies a window of the same size in each decoding core as much as possible in a simple manner for any interleaver that satisfies the condition that data in different rows do not mix with data in the same row. It is effective.

Claims

A decoder decoding method for decoding codewords generated by parallel encoding of a plurality of encoders in a mobile communication system using a plurality of decoding cores,

Dividing the memory area for interleaving evenly by the plurality of decoding cores;

Setting different decoding start positions for each of the plurality of decoding cores so that starting positions of the memory banks to which each of the plurality of decoding cores approaches for decoding are different from each other;

The decoding start position for each of the plurality of decoding cores is set to have an integer multiple of R / M based on the memory bank start row of the first decoding core among the plurality of decoding cores.

R is the number of rows in the memory area, and M is the number of the plurality of decoding cores.

delete

According to claim 1, Decoding start position for each of the plurality of decoding cores,

Decoding method characterized in that it is set so that the starting position is different from each other with at least one offset.

The method of claim 1, wherein each of the plurality of decoding cores,

A decoding method characterized by selecting different memory banks at the same time every time.

A first step of distributing the amount of data decoded in each of the plurality of decoding cores as equally as possible within the number of rows of the memory according to the number of each of the plurality of decoding cores;

A second process of setting a decoding start time point to have a relatively different memory access start time point in a different memory area at the same location for each of the plurality of decoding cores;

A decoding start time point of each of the plurality of decoding cores is set to have an integer multiple of R / M based on a memory bank start row of a first decoding core among the plurality of decoding cores.

The method of claim 5, wherein the first process,

Setting the same window size of each of the plurality of decoding cores to a maximum size not exceeding the size of the memory;

Setting a predetermined group by comparing the number of rows of the memory with the remaining size divided by the number of rows of the memory in the window size of each of the plurality of decoding cores;

If the predetermined group is additionally required, calculating a window size by a unit size from the last group to the first element in the required group.

In the decoding device in a mobile communication system,

At least one element decoder having a plurality of decoding cores for decoding the received encoded data;

The memory area for interleaving is equally divided for each of the plurality of decoding cores, and a decoding start position for each of the plurality of decoding cores is different so that the starting positions of the memory banks to which each of the plurality of decoding cores approaches for decoding are different from each other. Includes different address controllers,

Wherein R is the number of rows in the memory area and M is the number of the plurality of decoding cores.

The method of claim 7, wherein the address controller,

And a decoding start position for each of the plurality of decoding cores is a different row having at least one offset and the starting positions are not the same.

The method of claim 7, wherein each of the plurality of decoding cores,

A decoding device characterized by selecting different memory banks at the same time every time.

In the decoding device in a mobile communication system,

The amount of data decoded by each of the plurality of decoding cores is distributed as evenly as possible within the number of rows of the memory according to the number of each of the plurality of decoding cores, and for each of the plurality of decoding cores, different memory areas at the same position And an address controller that sets a decoding start time point to have a relatively different memory access start time point in, and prevents a memory conflict.

The method of claim 10, wherein the address controller,

Set the same window size of each of the plurality of decoding cores to a maximum size not exceeding the size of the memory, and the remaining size divided by the number of rows of the memory in the window size of each of the plurality of decoding cores and the row of the memory And a predetermined group is set by comparing the number of times, and if the predetermined group is additionally needed, the window size is calculated by the unit size from the last group to the first element in the required group.