ES2275508T3 - Aparato y metodo de intercalado turbo. - Google Patents
Aparato y metodo de intercalado turbo. Download PDFInfo
- Publication number
- ES2275508T3 ES2275508T3 ES00927908T ES00927908T ES2275508T3 ES 2275508 T3 ES2275508 T3 ES 2275508T3 ES 00927908 T ES00927908 T ES 00927908T ES 00927908 T ES00927908 T ES 00927908T ES 2275508 T3 ES2275508 T3 ES 2275508T3
- Authority
- ES
- Spain
- Prior art keywords
- information
- row
- bits
- turbo
- interleaving
- 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.)
- Expired - Lifetime
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/27—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 using interleaving techniques
- H03M13/2771—Internal interleaver for turbo 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/27—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 using interleaving techniques
- H03M13/2703—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 using interleaving techniques the interleaver involving at least two directions
- H03M13/271—Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column 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/27—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 using interleaving techniques
- H03M13/2703—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 using interleaving techniques the interleaver involving at least two directions
- H03M13/271—Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
- H03M13/2714—Turbo interleaver for 3rd generation partnership project [3GPP] universal mobile telecommunications systems [UMTS], e.g. as defined in technical specification TS 25.212
-
- 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/27—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 using interleaving techniques
- H03M13/276—Interleaving address generation
-
- 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/27—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 using interleaving techniques
- H03M13/276—Interleaving address generation
- H03M13/2764—Circuits therefore
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2957—Turbo codes and decoding
-
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
- G11B2220/00—Record carriers by type
- G11B2220/20—Disc-shaped record carriers
- G11B2220/25—Disc-shaped record carriers characterised in that the disc is based on a specific recording technology
- G11B2220/2537—Optical discs
- G11B2220/2562—DVDs [digital versatile discs]; Digital video discs; MMCDs; HDCDs
-
- 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/27—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 using interleaving techniques
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
- Detection And Correction Of Errors (AREA)
- Ultra Sonic Daignosis Equipment (AREA)
- Transition And Organic Metals Composition Catalysts For Addition Polymerization (AREA)
- Transmission Systems Not Characterized By The Medium Used For Transmission (AREA)
- Container Filling Or Packaging Operations (AREA)
- Complex Calculations (AREA)
- Television Systems (AREA)
- Radar Systems Or Details Thereof (AREA)
- Control Of Positive-Displacement Air Blowers (AREA)
Abstract
Turbo codificador que comprende: un primer codificador (111) dispuesto para codificar una trama de bits K de información de entrada para generar primeros símbolos codificados; un dispositivo (112) de intercalado dispuesto para escribir secuencialmente los bits K de información de entrada en una matriz rectangular R x C fila por fila comenzando en la primera columna de la primera fila, permutar dentro de la fila las posiciones de los bits de información en la matriz rectangular R x C en cada fila según una regla de intercalado dada, en el que dicha permutación dentro de la fila deja las posiciones de los bits en la última columna de dicha matriz sin cambiar después de dicha permutación, intercambiar la posición del bit de información en la última columna de la última fila con una posición dentro de la última fila que precede a la última columna, realizar permutaciones entre filas de la matriz rectangular R x C, y leer los bits de información desde la matriz rectangular R x C permutada columna por columna comenzando en la primera fila de la primera columna; y un segundo codificador (113) dispuesto para codificar los bits de información leídos para generar segundos símbolos codificados, en el que la matriz rectangular R x C tiene R filas y C columnas, K = R x C y especifica el número de bits de información de entrada en la trama, y K > R >1.
Description
Aparato y método de intercalado turbo.
La presente invención se refiere generalmente a
un turbo codificador usado para sistemas de comunicación por radio
(que incluyen sistemas satélites, RDSI, celulares digitales,
W-CDMA e IMT-2000), y en particular
a un dispositivo de intercalado interno de un turbo
codificador.
En general un dispositivo de intercalado
utilizado para un turbo codificador aleatoriza una dirección de
palabra de información de entrada y mejora una propiedad de
distancia de una palabra de código. En particular, se ha decidido
que un turbo codificador se utilizará en un canal suplementario (o
canal de transmisión de datos) de interfaces aéreas
IS-95C e IMT-2000 (o
CDMA-2000) y en un canal de datos del UMTS
("Universal Mobile Telecommunication System", sistema
universal de telecomunicaciones móviles) propuesto por el ETSI
("European Telecommunication Standards Institute", instituto
europeo de estándares de telecomunicaciones). Por tanto, para este
fin se requiere un método para poner en práctica un dispositivo de
intercalado. Adicionalmente la invención se refiere a un código de
corrección de errores que afecta en gran medida a la mejora del
rendimiento de los sistemas de comunicación digital existentes y
futuros.
Para un dispositivo de intercalado interno
existente para un turbo codificador (en lo sucesivo, se hace
referencia a un dispositivo de intercalado turbo) se han propuesto
diversos dispositivos de intercalado tales como dispositivos de
intercalado aleatorio PN ("Pseudo Noise", pseudo ruido),
dispositivos de intercalado aleatorios, dispositivos de intercalado
a bloques, dispositivo de intercalado no lineal y dispositivo de
intercalado aleatorio S. Sin embargo, hasta ahora, tales
dispositivos de intercalado eran simples algoritmos diseñados para
mejorar sus rendimientos en términos de investigaciones científicas
más que de implementación. Por tanto, cuando se implementa un
sistema real, debe tenerse en cuenta la complejidad de la
implementación de hardware. Ahora se realizará una descripción de
propiedades y problemas asociados al dispositivo de intercalado
convencional para el turbo codificador.
El rendimiento del turbo codificador depende de
su dispositivo de intercalado interno. En general, un aumento en el
tamaño de trama de entrada (es decir, el número de bits de
información incluidos en una trama) mejora la eficacia del turbo
codificador. Sin embargo, un aumento en el tamaño del dispositivo de
intercalado provoca un aumento geométrico en los cálculos. Por
tanto, en general no es posible implementar el dispositivo de
intercalado para el tamaño grande de trama.
Por tanto, en general, los dispositivos de
intercalado se implementan determinando las condiciones que cumplen
con varios criterios dados. Los criterios son los siguientes:
Propiedad de distancia: la distancia entre
símbolos de palabras de código adyacentes debería mantenerse hasta
una determinada medida. Esto tiene la misma función que una
propiedad de distancia de palabra de código del código
convolucional, y como un criterio que indica esto, se utiliza una
distancia libre mínima que es un valor del trayecto de palabra de
código o una secuencia de palabra de código con el peso Hamming
mínimo de entre las secuencias de símbolo de código (o trayectos de
palabra de código) emitidos en el enrejado ("trellis"). En
general se prefiere que el dispositivo de intercalado se diseñe para
tener la distancia libre más larga, si es posible.
Propiedad aleatoria: un factor de correlación
entre símbolos de palabras de salida tras el intercalado debería
ser mucho más bajo que un factor de correlación entre símbolos de
palabras de entrada originales antes del intercalado. Es decir,
debería realizarse completamente la aleatorización entre los
símbolos de palabra de salida. Esto afecta directamente a la
calidad de la información extrínseca generada en la decodificación
continua.
Aunque los criterios anteriores puedan aplicarse
a un dispositivo de intercalado turbo general, es difícil analizar
claramente las propiedades cuando el dispositivo de intercalado
aumenta su tamaño.
Adicionalmente, otro problema que se produce
cuando se diseña el dispositivo de intercalado turbo es que la
distancia libre mínima del código de turbo varía según el tipo de la
palabra de código de entrada. Es decir, cuando la palabra de
información de entrada tiene un patrón de secuencia específico
definido como patrón de secuencia de información crítica (CISP) la
distancia libre de los símbolos de código de salida generados desde
el turbo codificador tiene un valor muy pequeño. Si la palabra de
información de entrada tiene un peso Hamming 2, el CISP se produce
cuando la palabra de información de entrada tiene dos bits de
información de "1" y puede producirse también cuando la
palabra de información de entrada tiene 3 o más bits de información
de "1". Sin embargo, en la mayoría de los casos, cuando la
palabra de información de entrada tiene 2 bits de información de
"1" se forma la distancia mínima libre y la mayoría de los
eventos de error se producen en esta condición. Por tanto, cuando
se diseña el dispositivo de intercalado turbo se realiza
generalmente un análisis en el caso en el que la palabra de
información de entrada tenga el peso Hamming 2. Un motivo de la
existencia del CISP es que el turbo codificador utiliza
generalmente codificadores RSC ("Recursiv Systematic Convolutional
Codes", codificadores sistemáticos convolucionales recursivos)
para los codificadores de componentes mostrados en la figura 1
(descritos adicionalmente más adelante). Para mejorar el rendimiento
del turbo codificador debería emplearse un polinomio primitivo para
un polinomio de retroalimentación (gf(x) de la figura 1) de
entre los polinomios de generador para el codificador de
componentes. Por tanto, cuando el número de las memorias del
codificador RSC es m, una secuencia de retroalimentación generada
por el polinomio de retroalimentación repite continuamente el mismo
patrón a un periodo de 2^{m}-1. Por tanto si se
recibe una palabra "1" de información de entrada a la
distancia correspondiente a este periodo, los mismos bits de
información son O exclusivos de manera que el estado del
codificador RSC se convierte en un estado de todo ceros de ahora en
adelante, generando así los símbolos de salida de todo ceros. Esto
significa que el peso Hamming de la palabra de código generada por
el codificador RSC tiene un valor constante después de este evento.
Es decir, la distancia libre del turbo código se mantiene tras este
tiempo, y el CISP se convierte en una causa principal de una
reducción de la distancia libre del turbo codificador, mientras que,
como se observó anteriormente, es deseable una distancia libre
mayor.
En este caso (en el dispositivo de intercalado
turbo de la técnica anterior) para aumentar la distancia libre, el
dispositivo de intercalado turbo dispersa aleatoriamente la palabra
de información de entrada CISP para impedir un descenso en la
distancia libre en el símbolo de salida del otro codificador RSC de
componentes.
Las propiedades expuestas anteriormente son
características fundamentales del dispositivo de intercalado turbo
conocido. Sin embargo, para el CISP es conveniente que la palabra de
información tenga el peso Hamming mínimo, cuando la palabra de
información de entrada tenga el peso Hamming 2. En otras palabras,
no se tuvo en cuenta el hecho de que el CISP pueda generarse
incluso cuando la palabra de información de entrada tiene el peso
Hamming 1 (es decir cuando la palabra de información de entrada
tiene un bit de información de "1") cuando la entrada de la
palabra de información al turbo codificador tenía el tipo de un
bloque compuesto de tramas.
Por ejemplo, un dispositivo (PIL) de intercalado
principal diseñado como el modelo de trabajo del dispositivo de
intercalado de turbo código especificado mediante el estándar UMTS
presente muestra tales problemas, presentando una propiedad de
distancia libre degradada. Es decir, el algoritmo de implementación
del modelo de dispositivo de intercalado turbo PIL incluye 3
etapas, de las cuales la segunda etapa que juega el papel más
importante, realiza la permutación aleatoria en los bits de
información de los grupos respectivos. La segunda etapa se divide
en tres casos caso A, caso B y caso C, y el caso B siempre invoca el
caso en el que la distancia libre disminuye debido al evento en el
que la palabra de información de entrada tiene el peso Hamming 1.
Adicionalmente incluso el caso C implica una posibilidad de que tal
evento ocurrirá. Los problemas detallados se describirán
posteriormente con referencia al
PIL.
PIL.
Como conclusión, cuando se requieren varios
tamaños de dispositivos de intercalado y la complejidad de la
implementación del hardware está limitada al sistema
IMT-2000 o UMTS, el dispositivo de intercalado turbo
debería diseñarse para garantizar el rendimiento óptimo del
dispositivo de intercalado teniendo en cuenta las limitaciones. Es
decir, el dispositivo de intercalado requerido debería poder
garantizar el rendimiento uniforme para los diversos tamaños del
dispositivo de intercalado mientras que cumple las propiedades
expuestas anteriormente. Más recientemente, se han propuesto varios
tipos de dispositivos de intercalado para un dispositivo de
intercalado turbo PCCC ("Parallel Concatenated Convolutional
Codes", códigos convolucionales concatenados en paralelo) y un
dispositivo de intercalado turbo LCS ("Linear Congruential
Sequence", de secuencia congruente lineal) se ha establecido
provisionalmente como el dispositivo de intercalado turbo en las
especificaciones IS-95C e IMT-2000
(o CDMA-2000). Sin embargo la mayoría de estos
dispositivos de intercalado turbo tienen los problemas del CSIP con
el peso Hamming 1., y los detalles de la implementación de estos
dispositivos de intercalado turbo todavía no están definidos. Por
tanto, la presente invención propone una solución de los problemas
de los dispositivos de intercalado turbo, y un nuevo método para
implementar el dispositivo de intercalado turbo. Adicionalmente, la
invención muestra el dispositivo de intercalado turbo PIL que es una
hipótesis de trabajo del dispositivo de intercalado turbo UMTS, y
propone una solución del problema de este dispositivo de
intercalado.
Como resumen, la técnica anterior tiene las
desventajas siguientes.
- (1)
- El dispositivo de intercalado turbo está diseñado para el tamaño de trama infinito basándose en el CISP para el que la palabra de información de entrada tiene el peso Hamming 2, sin considerar el hecho de que la determinación del CISP según el tipo de palabra de información de entrada está limitada al tamaño de trama. Sin embargo, en un sistema real, la trama tiene un tamaño finito, provocando así una disminución de la distancia libre del turbo código.
- (2)
- Al diseñar el dispositivo de intercalado turbo existente, no se consideró el hecho de que la palabra de información de entrada pudiera tener el peso Hamming 1. En otras palabras, para el tamaño de trama finito, debería determinarse la regla para el diseño del dispositivo de intercalado turbo considerando el hecho de que la distancia libre mínima generada en el turbo codificador PCCC se determina mediante el CISP que tiene el peso Hamming 1. Sin embargo esto no se consideró totalmente para los dispositivos de intercalado turbo existentes.
- (3)
- El dispositivo (PIL) de intercalado primario diseñado como la hipótesis de trabajo del dispositivo de intercalado de turbo código definido mediante la especificación UMTS implica problemas de este tipo, presentando así un rendimiento de distancia libre degradada.
S. Dolinar et al., "Weight
Distributions for Turbo Codes Using Random and Nonrandom
Permutations", TDA, Progress Report 42-122,
páginas 56 a 65, 15-08-1995 es una
publicación que trata las distribuciones de peso que pueden
conseguirse para códigos turbo utilizando permutaciones aleatorias,
permutaciones diseñadas tales como permutaciones no aleatorias
basadas en el intercalado a bloques o en el desplazamiento circular
y permutaciones semi-aleatorias. El documento
describe adicionalmente que debido a la propiedad de excursión de
los codificadores, es importante distinguir entre las secuencias de
entrada de terminación automática y de terminación no automá-
tica.
tica.
El documento TS25.212 V1.0.0
(1999-04) es una especificación técnica del grupo de
especificaciones técnicas 3GPP para la red de acceso por radio (RAN
WG1) que se refiere a la multiplexación y a la codificación de
canal. En este método de intercalado, los datos se escriben en una
matriz RXC, implicando el intercalado un intercalado dentro de la
fila, después el intercalado entre filas seguido columna por columna
leído desde la matriz. Esta especificación técnica también se
refiere a la turbo codificación y por tanto al intercalado. Los
detalles de esta especificación se describirán más adelante en
relación con las características de la presente invención.
Por tanto es un objeto de la presente invención
proporcionar un dispositivo y método de intercalado que considera
las propiedades de un dispositivo de intercalado turbo y una
propiedad de un patrón de secuencia de información crítica (CISP)
que mejora el rendimiento de distancia libre del dispositivo de
intercalado turbo.
El problema se soluciona mediante el objeto de
las reivindicaciones independientes. Las realizaciones preferidas
son el objeto de las reivindicaciones dependientes.
Es un aspecto de la presente invención
proporcionar un dispositivo y método de intercalado para mejorar el
rendimiento de la distancia libre de un turbo codificador para el
caso en el que una palabra de información de entrada tiene un peso
Hamming 1 cuando la entrada de palabra de información a un
dispositivo de intercalado turbo tiene un tipo de bloque
comprendido por tramas.
Es un aspecto adicional de la presente invención
proporcionar un dispositivo y método de intercalado para solucionar
el problema de que la distancia libre disminuye cuando una palabra
de información de entrada tiene un peso Hamming 1 en un dispositivo
(PIL) de intercalado principal que es el dispositivo y método de
intercalado especificado en la especificación UMTS.
Para conseguir los aspectos anteriores, se
proporciona un método de intercalado bidimensional que comprende la
división de una trama de bits de información de entrada en una
pluralidad de grupos y almacenar secuencialmente los grupos
divididos en una memoria: permutar los bits de información de los
grupos según una regla determinada y desplazar un bit de
información existente en la última posición del último grupo a una
posición anterior a la última posición; y seleccionar los grupos
según un orden predeterminado, y seleccionar uno de los bits de
información en el grupo seleccionado.
Los anteriores y otros aspectos, características
y ventajas de la presente invención resultarán más evidentes a
partir de la siguiente descripción detallada cuando se considera en
conjunción con los dibujos acompañantes en los que:
la figura 1 es un diagrama que ilustra un turbo
codificador paralelo general,
la figura 2 es un diagrama que ilustra un
dispositivo de intercalado general,
la figura 3 es un diagrama que ilustra un
dispositivo de desintercalado general,
la figura 4 es un diagrama que ilustra un método
para generar un patrón de secuencia de información crítica (CISP)
en un dispositivo de intercalado turbo,
la figura 5 es un diagrama que ilustra otro
método para generar el CISP en el dispositivo de intercalado
turbo,
la figura 6 es un diagrama que ilustra un método
para resolver un problema que se produce cuando se genera el CISP
de la figura 4,
la figura 7 es un diagrama que ilustra un método
para resolver un problema que se produce cuando se genera el CISP
de la figura 5,
la figura 8 es un diagrama que ilustra otro
método para resolver un problema que se produce cuando se genera el
CISP en el dispositivo de intercalado turbo;
la figura 9 es un diagrama que ilustra un método
para generar el CISP en un dispositivo de intercalado turbo
bidimensional,
la figura 10 es un diagrama que ilustra un
método para resolver un problema que se produce cuando se genera el
CISP de la figura 7,
la figura 11 es un diagrama de bloques que
ilustra un dispositivo de intercalado para eliminar el CISP según
una realización de la presente invención, y
la figura 12 es un diagrama de flujos para
explicar un proceso de intercalado de un PIL modificado (dispositivo
de intercalado principal) según una realización de la presente
invención.
Ahora se describirá una realización preferida de
la presente invención en la presente memoria más adelante con
referencia a los dibujos acompañantes. En la siguiente descripción
no se describen en detalle las funciones o construcciones muy
conocidas ya que impediría ver claramente la invención con detalles
innecesarios.
Antes de describir la invención, la
especificación presentará los problemas que se producen cuando una
palabra de información de entrada, que es uno de los criterios de
diseño utilizados en el dispositivo de intercalado/desintercalado
turbo existente se procesa basándose en una unidad de trama, y
después se analiza un efecto que tiene el CISP con un peso Hamming
1 en el peso Hamming de los símbolos de código de salida. A
continuación, la especificación propondrá un método para resolver
los problemas y verificar la diferencia de rendimiento a través del
análisis de la distancia libre mínima.
La figura 1 muestra una estructura de un turbo
codificador paralelo general que se describe detalladamente en la
patente estadounidense nº 5.446.747, publicada el 29 de agosto de
1995 que se incorpora a modo de referencia en la presente
memoria.
Con referencia a la figura 1, el turbo
codificador incluye un primer codificador 111 de componentes para
codificar datos de trama de entrada, un dispositivo 112 de
intercalado para intercalar los datos de trama de entrada y un
segundo codificador 113 de componentes para codificar una salida del
dispositivo 112 de intercalado. Un codificador RSC (códigos
convolucionales sistemáticos recursivos) conocido se utiliza
normalmente para los codificadores 111, 113 de componentes primero
y segundo. En lo sucesivo, al primer codificador 111 de componentes
RSC se hará referencia como RSC1 y al segundo codificador 113 de
componentes se hará referencia como RSC2. Además el dispositivo 112
de intercalado tiene el mismo tamaño que la trama de bits de
información de entrada y reordena la secuencia de los bits de
información proporcionada al segundo codificador 113 de componentes
para reducir una correlación entre los bits de información.
Las figuras 2 y 3 muestran estructuras
fundamentales del dispositivo de intercalado/desintercalado general
respectivamente.
Con referencia a las figuras 2 se describirá un
dispositivo de intercalado para intercalar datos de trama emitidos
desde el primer codificador de componentes. Un generador 211 de
direcciones genera una dirección de lectura para cambiar la
secuencia de bits de datos de entrada según un tamaño L de datos de
trama de entrada y un reloj de entrada, y proporciona una memoria
212 de dispositivo de intercalado con la dirección de lectura
generada. La memoria 212 de dispositivo de intercalado almacena
secuencialmente datos de entrada en un modo de operación de
escritura, y emite los datos almacenados según la dirección de
lectura proporcionada desde el generador 211 de direcciones en un
modo de operación de lectura. Un contador 213 cuenta el reloj de
entrada y proporciona el valor de contador de reloj a la memoria
212 de dispositivo de intercalado como una dirección de escritura.
Tal como se describe anteriormente, el dispositivo de intercalado
almacena secuencialmente datos de entrada en la memoria 212 de
dispositivo de intercalado en el modo de operación de escritura y
emite los datos almacenados en la memoria 212 de dispositivo de
intercalado según la dirección de lectura proporcionada desde el
generador 211 de direcciones en el modo de operación de lectura.
Alternativamente también es posible cambiar la secuencia de los
bits de datos de entrada antes de almacenarlos en la memoria del
dispositivo de intercalado en el modo de operación de escritura, y
secuencialmente leer los datos almacenados en el modo de operación
de lectura.
Con referencia a la figura 3 se describirá un
dispositivo de desintercalado. Un generador 311 de direcciones
genera una dirección de escritura para restaurar la secuencia de los
bits de datos de entrada a la secuencia original según un tamaño L
de datos de trama de entrada y un reloj de entrada, y proporciona
una memoria 312 de dispositivo de desintercalado con la dirección
de lectura generada. La memoria 312 de dispositivo de desintercalado
almacena datos de entrada según la dirección de escritura
proporcionada desde el generador 311 de direcciones en el modo de
operación de escritura, y emite secuencialmente los datos
almacenados en el modo de operación de lectura. Un contador 313
cuenta el reloj de entrada y proporciona el valor de contador de
reloj a la memoria 312 de dispositivo de desintercalado como una
dirección de lectura. Tal como se describe anteriormente, el
dispositivo de desintercalado tiene la misma estructura que el
dispositivo de intercalado pero tiene el funcionamiento inverso del
dispositivo de intercalado. El dispositivo de desintercalado se
diferencia solamente del dispositivo de intercalado en que los
datos de entrada tienen secuencias diferentes tanto en el modo de
escritura como en el de lectura. Por tanto, por conveniencia, la
descripción siguiente se hará con referencia solamente al
dispositivo de intercalado.
En general, dado que el turbo código es un
código de bloque lineal, una palabra de información nueva obtenida
añadiendo una palabra de información no cero a una palabra de
información de entrada tiene la misma propiedad de distribución de
palabras de código. Por tanto aunque la propiedad se desarrolle
basándose en la palabra de información de todo ceros, se
proporcionará el mismo rendimiento comparando con el rendimiento
determinado que emplea la palabra de información no cero. Así, se
realizará una descripción más adelante con referencia al caso en el
que la palabra de información de entrada es la palabra de código de
todo ceros. Es decir, se analizará el rendimiento del turbo código
suponiendo que la palabra de información de entrada tenga bits de
todo ceros y solamente un bit de información dado sea "1".
Para mejorar el rendimiento del turbo
codificador, puede usarse un polinomio primitivo para un polinomio
de retroalimentación de un generador de polinomios para el
codificador de componentes. El polinomio de retroalimentación se
proporciona por la derivación de expresión que sufre la
retroalimentación en los codificadores 111, 1113 de componentes RSC
de la figura 1 en un polinomio, y el polinomio de retroalimentación
se define como gf(x). Si en la figura 1, gf(x) =
1+x^{2}+x^{3}. Es decir, el orden más elevado indica la
profundidad de una memoria, y la conexión más a la derecha
determina si el coeficiente x^{3} de gf(x) es 0 o 1. Por
tanto, cuando el número de las memorias para el codificador RSC es
m, una secuencia de retroalimentación generada por el polinomio de
retroalimentación repite continuamente el mismo patrón en un periodo
de 2^{m}-1. Así cuando se recibe una palabra de
información de entrada "1" en el momento que corresponde a este
periodo (por ejemplo para m = 3, cuando se recibe una palabra de
información de entrada de "10000001...") los mismos bits de
información son O exclusivos de manera que el estado del codificador
RSC se convierte en un estado de todo ceros de ahora en adelante,
generando así los símbolos de salida de todo ceros. Esto significa
que el peso Hamming de la palabra de código generada por el
codificador RSC tiene el valor constante de 1 después de este
evento. Es decir, la distancia libre del turbo código se mantiene
tras este tiempo, y el CISP se convierte en una causa principal de
una reducción de la distancia libre del turbo codificador.
En este caso para aumentar la distancia libre,
el dispositivo de intercalado turbo dispersa aleatoriamente la
palabra de información de entrada CISP para impedir un descenso en
la distancia libre en el símbolo de salida del otro codificador RSC
de componentes. La tabla 1 a continuación muestra una secuencia de
retroalimentación generada desde gf(x) = 1+x^{2}+x^{3}.
En la tabla 1, X(t) indica un bit de información de entrada
en un tiempo t de la palabra de información de entrada. Además,
m(t), m(t-1) y
m(t-2) indican 3 estados de memoria del
codificador RSC respectivamente. En este caso, dado que el número de
memorias es 3, el periodo es 2^{3}-1 = 7.
\vskip1.000000\baselineskip
Desde la tabla 1 se observa que si X(t) =
1, en el tiempo t = 7, entonces m(t),
m(t-1) y m(t-2) se
convierten en estados de todo ceros de aquí en adelante. Por tanto
el peso Hamming de los siguientes símbolos de salida se convierte
siempre en cero. En este caso, si el dispositivo de intercalado
turbo proporciona el RSC2 con la secuencia de información de
entrada "10000001000..." como es, el peso Hamming de los
símbolos de salida en el tiempo siguiente de t = 7 no cambiará a
partir de aquí incluso en el RSC2 que emplea el mismo polinomio de
retroalimentación por la misma razón. Esto provoca una disminución
en la distancia libre de todos los símbolos de salida del turbo
codificador. Para impedir esto, el dispositivo de intercalado turbo
cambia la secuencia de información de entrada original
"10000001000" a una secuencia de información de un patrón
diferente (por ejemplo, cambia una posición del bit "1" de
información tal como 110000000...) y proporciona la secuencia
resultante al RSC2. Por tanto aunque se detenga un aumento en el
peso Hamming en el RSC1, el peso Hamming aumenta continuamente en
el RSC2 de manera que aumenta la distancia libre total del turbo
codificador. Esto es porque el polinomio de retroalimentación que
tiene el tipo de filtro de respuesta de impulso infinita (IIR)
genera continuamente el símbolo "1" de salida infinito incluso
para un bit "1" de información de entrada. La ecuación 1
muestra a continuación la relación entre el RSC1 y el RSC2 en
términos del peso Hamming o la distancia libre del turbo
codificador.
Ecuación
1
HW \
(secuencia \ de \ código \ de \ salida) = HW \ (secuencia \ de \
código \ RSC1) + HW \ (secuencia \ de \ código \
RSC2)
en la que HW es el peso
Hamming.
Desde la ecuación 1 se observa que es muy
importante un equilibrio del peso Hamming entre RSC1 y RSC2. En
particular, se observa que la distancia mínima libre del turbo
código se genera para el peso Hamming mínimo de la palabra de
información de entrada cuando se considera la característica IIR
("Infinite Impulse Response", de respuesta de impulso
infinita) del codificador RSC. En general, la distancia libre mínima
se proporciona cuando la palabra de información de entrada tiene el
peso Hamming 2 tal como se mencionó anteriormente.
Sin embargo, tal como se describió
anteriormente, la distancia libre mínima se produce cuando la
palabra de información de entrada tiene el peso Hamming 3, 4,
5,..., así como cuando la palabra de información de entrada tiene
el peso Hamming 2. Esto se produce cuando la palabra de información
de entrada se recibe basándose en la unidad de trama, como
sigue.
Por ejemplo, cuando solamente el bit de
información situado en la última posición de la palabra de
información de entrada, es decir, la última posición de la trama,
es "1" y todos los demás bits de información son ceros, el
peso Hamming de la palabra de información de entrada se convierte en
1. En este caso, el número de los símbolos "1" emitidos desde
el RSC1 se vuelve muy pequeño porque no hay más palabras de
información de entrada. Naturalmente, cuando se usan bits de cola
cero existen dos símbolos pero aquellos se usan de manera
independiente más que someterse al intercalado turbo. Por tanto, en
la presente memoria se supone que el peso aumenta ligeramente. Dado
que se añade el peso constante, esto se excluirá de un análisis del
dispositivo de intercalado. En este caso, se observa de la ecuación
1 que el RSC2 debería generar un gran número de símbolos "1" de
salida para aumentar la distancia libre
total.
total.
Ahora con referencia a las figuras 4 a 10, se
realizará una descripción de manera comparativa con respecto a los
problemas de la técnica anterior y las soluciones a los
problemas.
En las figuras 4 a 10, las partes sombreadas
indican las posiciones en las que el bit de información de entrada
es "1", y las otras partes indican las posiciones en las que el
bit de información de entrada es "0".
Si, tal como se muestra en la figura 4, el
dispositivo de intercalado turbo desplaza (o permuta) la posición
de la palabra de información de entrada, en la que el símbolo
original del RSC1 es "1" a la última posición de la trama tras
el intercalado, el número de los símbolos "1" de salida
generado desde RSC2 será muy pequeño. En este caso, dado que el
RSC1 y el RSC2 generan un número muy pequeño de los símbolos de
salida "1" según la ecuación 1, la distancia libre total
disminuye drásticamente. Sin embargo, si tal como se muestra en la
figura 5, el dispositivo de intercalado turbo desplaza la posición
de la palabra de información de entrada, en la que el símbolo
original del RSC1 es "1" a la primera posición o a una posición
cercana a la posición de cabeza de la trama tras el intercalado, el
número de los símbolos "1" de salida generados desde el RSC2
aumentará. Esto es porque una pluralidad de símbolos "1" se
emiten a través de transiciones de estado (N (tamaño del
dispositivo de intercalado)-h (un número de
"1") del codificador RSC2. En este caso, el RSC2 genera un
gran número de símbolos "1" de salida, incrementando de este
modo la distancia libre total.
Adicionalmente a la disminución de la distancia
libre que se produce cuando el dispositivo de intercalado interno
desplaza el bit "1" de información de entrada situado en la
última posición de la trama a la última posición de la trama tal
como se muestra en la figura 4, si uno de dos bits de información
"1" situado en la parte final de la trama está situados
todavía en (o cerca de) la posición final de la trama incluso
después del intercalado, tal como se muestra en la figura 6, la
distancia libre total disminuirá.
Por ejemplo, si las operaciones del dispositivo
de intercalado interno en el modo de trama mostrado en la figura 6,
en la que dos símbolos situados en la posición final de la trama son
unos, y los otros símbolos son todos ceros, entonces el peso
Hamming de la palabra de información de entrada es 2. Incluso en
este caso, el número de los símbolos "1" de salida generados
desde el RSC1 se vuelve muy pequeño dado que no hay más bit de
información de entrada. Por tanto, según la ecuación 1, el RSC2
debería generar un gran número de los símbolos "1" de salida
para aumentar la distancia libre total. Sin embargo, si tal como se
muestra en la figura 6, el dispositivo de intercalado tubo desplaza
la posición de los dos símbolos anteriores a la posición final (o
en algún lugar cerca de la posición final) de la trama incluso
después del intercalado, el RSC2 generará también un número pequeño
de los símbolos "1" de salida. Sin embargo, si tal como se
muestra en la figura 7, el dispositivo de intercalado turbo
desplaza la posición de los dos símbolos anteriores a la posición de
cabeza (o en algún lugar cerca de la posición de cabeza) de la
trama, el RSC2 generará un gran número de símbolos "1". Esto
es, el codificador RSC2 emite una pluralidad de símbolos "1" a
través de las transiciones de estado (N-h) (N =
tamaño del dispositivo de intercalado, h = un número del símbolo
"1"). En este caso, por tanto, el RSC2 genera el número
aumentado de símbolos "1" de salida, incrementando así la
distancia libre total.
Este principio puede expandirse al caso en el
que el dispositivo de intercalado turbo funciona en el modo de
trama mostrado en la figura 8 en el que existe una pluralidad de
bits "1" de información en el periodo final (o duración) de la
trama y los demás bits de información son todos ceros. Incluso en
este caso, la distancia libre total se aumenta mediante el
desplazamiento de los bits de información que existen en la posición
final de la trama a la posición de cabeza de la trama o a
posiciones más cercanas a la posición de cabeza, tal como se
muestra en la figura 8. Naturalmente, dado que el turbo código es el
código de bloque lineal, incluso la nueva palabra de información
obtenida al añadir una palabra de información no cero a una palabra
de información de este tipo tiene la misma propiedad. Por tanto, se
realizará una descripción más adelante basándose en la palabra de
información de todos ceros.
En conclusión, cuando se diseña el dispositivo
de intercalado turbo, deberían cumplirse las condiciones siguientes
así como la propiedad aleatoria y la propiedad de distancia para
garantizar el rendimiento del turbo decodificador y la distancia
libre del turbo codificador.
Condición 1: cuando se diseña cada dispositivo
de intercalado turbo, los bits de información correspondientes a un
periodo específico desde la última posición de la trama deberían
desplazarse a la primera posición de la trama mediante el
intercalado para aumentar la distancia libre del turbo código.
Condición 2: los bits de información
correspondientes a la última posición de la trama deberían
desplazarse a una posición anterior a la última posición (si es
posible a la posición de cabeza de la trama) mediante el
intercalado para aumentar la distancia libre del turbo código.
Estas condiciones pueden aplicarse a un
dispositivo de intercalado turbo bidimensional así como al
dispositivo de intercalado unidimensional anteriormente descrito.
El dispositivo de intercalado unidimensional realiza el
intercalado, con respecto a la trama de información de entrada como
un grupo, tal como se muestra en las figuras 4 a 8. El dispositivo
de intercalado bidimensional realiza el intercalado dividiendo la
trama de información de entrada en una pluralidad de grupos. La
figura 9 muestra el intercalado bidimensional en el que la palabra
de información de entrada tiene el peso Hamming 1.
Tal como se ilustra, los bits de información de
entrada se escriben secuencialmente en los grupos respectivos (o
filas). Es decir, los bits de información de entrada se escriben
secuencialmente en los grupos (o filas) r0, r1,...,
r(R-1). En cada grupo, los bits de
información de entrada se escriben secuencialmente de izquierda a
derecha. Por tanto, un algoritmo de intercalado turbo cambia
aleatoriamente la posición de los elementos RxC (es decir, bits de
información de entrada) en la que R es el número de filas, C es el
número de columnas o, de manera equivalente, el número de bits de
información en un grupo. En este caso, es preferible diseñar el
algoritmo de intercalado turbo de tal manera que el bit de
información situado en la última posición (o la posición más a la
derecha) del último grupo debería situarse en la posición primera,
si es posible durante la salida. Naturalmente, en función del orden
de selección de grupos, el bit de información de entrada situado en
la última posición puede desplazarse a la posición primera (o
cercana a la misma) del grupo correspondiente. Adicionalmente, la
condición 1 y la condición 2 pueden normalizarse en un dispositivo
de intercalado turbo de dimensión k (en el que k > 2) así como
el dispositivo de intercalado bidi-
mensional.
mensional.
La figura 10 muestra un caso en el que la
palabra de información de entrada tiene el peso Hamming superior a
2. Tal como se muestra, los bits de información situados en la
última posición del último grupo se desplazan a las posiciones de
cabeza del último grupo mediante el intercalado. Naturalmente la
regla de desplazamiento detallado (o intercalado) se determina
según un algoritmo para un dispositivo de intercalado específico. La
invención presenta la condición 1y la condición 2 que deberían
cumplir necesariamente la determinación de la regla de
intercalado.
intercalado.
A continuación se realizará una descripción del
dispositivo PIL de intercalado que tiene los problemas de la
técnica anterior, y después se realizará una descripción adicional
de una solución de los problemas que tiene el dispositivo PIL de
intercalado.
Primera etapa (1) determinar un número de fila
tal que
R = 10 en el caso de que el número del bit K de
información de entrada sea de 481 a 530 y
R = 20 en el caso de que el número del bit K de
información de entrada sea cualquier otra longitud de bloque
excepto de 481 a 530, (2) determina un número C de columna tal que
el caso 1 es C = p = 53 en el que p = número primo mínimo y el
caso 2 es
- (i)
- encontrar un número primo mínimo p que cumpla 0 = <(p+1)-K/R
- (ii)
- si (0<p-K/R) ir entonces a (iii) sino C = p+1
- (iii)
- si 0 = <(p-1-K/R), entonces C = p-1, sino C = p
En primer lugar se describirá una segunda etapa,
caso -B, si C = p+1 a partir de un algoritmo de intercalado para el
dispositivo PIL de intercalado que se determinó provisionalmente
como el dispositivo de intercalado de turbo UMTS. En la ecuación 2
siguiente, R indica el numero de grupos (o filas) y tiene el valor
de R = 10 o R = 20. Adicionalmente C indica el tamaño de cada grupo
y se determina mediante el número primo p que cumple 0 < (p+1) -
K/R tal como se determina en la etapa 1 según un valor K/R en el que
K es el tamaño de los bits de información de entrada reales de una
trama. En el caso -B, es siempre que C = p+1. Por tanto el tamaño
real del dispositivo PIL de intercalado se convierte en un valor
determinado por RxC, que es mayor que K. Adicionalmente,
Cj(i) indica una posición de los bits de información
obtenidos mediante la permutación aleatoria de la posición de los
bits de información de entrada en el grupo basándose en un grupo de
orden i, en el que i = 0, 1, 2, 3...., p. Adicionalmente Pj indica
un valor semilla inicial para un vector de fila de orden j, y se
proporciona inicialmente mediante el algoritmo.
Ecuación
2
B-1) Se selecciona una raíz g0
primitiva a partir de una tabla de constantes de inicialización
aleatoria dada (3GPP TS 25.212 tabla 2, tabla de un primo p y raíz
primitiva asociada) de tal manera que g0 es una raíz primitiva de
un campo basado en el primo p.
B-2) Construir una secuencia
C(i) de base a utilizar para la aleatorización de los
vectores de fila, se genera utilizando la fórmula siguiente.
C(i)=[g0 \ x \
C(i-1)] \ mod \ p, \ i = 1, \ 2, \ 3, ..., \
p-2,\
C(0)=1
B-3) Seleccionar el conjunto de
números enteros primos mínimo {q_{j}, j = 0, 1, 2, ...,
R-1} de tal manera que g.c.d{q_{j},
p-1} = 1, q_{j} > 6 y q_{j} >
q_{(j-1)}, en el que g.c.d ("greatest common
divider"), es un máximo común divisor y q_{0} = 1.
B-4) {p_{j}, j = 0, 1, 2, ...,
R-1} que es un conjunto nuevo de números primos se
calcula a partir de {q_{j,} j = 0, 1, 2, ...,
R-1} de tal manera que p_{p(j)} = q_{j},
en el que j = 0, 1, ... R-1 y p_{(j)} es el patrón
de permutación entre filas definido en la tercera etapa.
B-5) Elementos de la permutación
dentro de una fila de orden j como método siguiente
C_{j}(i)=C(i \ x \ p_{j}]
\ mod \ (p-1)), \ i=1, \ 2, \ 3, ..., \
p-2,
C_{j}(p-1)=0
y
C_{j}(p)=p
Una tercera etapa,
Realizar la permutación de filas basada en los
siguientes patrones p_{(j)} (j = 0, 1, 2, R-1) en
los que p_{(j)} es la posición de fila original de la fila
permutada de orden j. El uso de estos patrones es el siguiente,
cuando el número del bit K de información de entrada es de 320 a 480
bit realizar el patrón p_{A} de selección de grupo, cuando el
número del bit K de información de entrada es de 481 a 530 bit
realizar el patrón p_{C} de selección de grupo, cuando el número
del bit K de información de entrada es de 531 a 2280 bit realizar
el patrón p_{A} de selección de grupo, cuando el número del bit K
de información de entrada es de 2281 a 2480 bit realizar el patrón
p_{B} de selección de grupo, cuando el número del bit K de
información de entrada es de 2481 a 3160 bit realizar el patrón
p_{A} de selección de grupo, cuando el número del bit K de
información de entrada es de 3161 a 3210 bit realizar el patrón
p_{B} de selección de grupo, y cuando el número del bit K de
información de entrada es de 3211 a 5114 bit realizar el patrón
p_{A} de selección de grupo. El patrón de selección de grupo es
como sigue;
- p_{A}: {19, 9, 14, 4 0, 2, 5, 7, 12, 18, 10, 8, 13, 17, 3, 1, 16, 6, 15, 11} para R = 20
- p_{B}: {19, 9, 14, 4 0, 2, 5, 7, 12, 18, 16, 13, 17, 15, 3, 1, 6, 11, 8, 10} para R = 20
- p_{C}: { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0} para R = 10
Debería observarse en la presente memoria que la
última operación de B-5) se define como
C_{j}(p) = p. Es decir, esto significa que cuando la
posición del bit de información de entrada antes del intercalado es
p, la posición del bit de información de entrada se mantiene en la
posición p incluso después del intercalado PIL. Por tanto para el
último grupo (j = 19), los bits C_{R-1}(P)
= C_{19}(p) de información existentes en la última
posición mantienen la misma posición i = P que es la última posición
del grupo de orden 19. Por tanto, la condición 2 para diseñar el
dispositivo intercalado turbo no se cumple.
Es decir, para resolver el problema del
dispositivo PIL de intercalado puede modificarse la etapa
B-5) de algoritmo de la manera siguiente. La
invención presenta seis métodos de
B-5-1) a
B-5-6) a modo de ejemplo. Entre
estos, un rendimiento óptimo puede determinarse a través de
simulaciones a la luz de las propiedades del dispositivo de
intercalado turbo.
Se selecciona uno de los 6 métodos
siguientes.
B-5-1) Se
intercambian las posiciones de C_{R-1}(0) y
C_{R-1} (p). R = 10 o 20
B-5-2) Se
intercambian las posiciones de
C_{R-1}(p-1) y
C_{R-1} (p). R = 10 o 20
B-5-3) Para cada
j se intercambian las posiciones de C_{j}(0) y
C_{j}(p). j = 0, 1, 2, ..., R-1
B-5-4) Para cada
j se intercambian las posiciones de
C_{j}(p-1) y C_{j}(p). j = 0, 1,
2, ..., R-1
B-5-5) Para cada
j se busca una posición k de intercambio óptima para el algoritmo de
intercalado utilizado para intercambiar posiciones de
C_{j}(k) y C_{j}(p).
B-5-6) Para una
fila de orden (R-1) se busca una posición k de
intercambio óptima para el algoritmo de intercalado utilizado para
intercambiar posiciones de C_{R-1}(k) y
C_{R-1}(p).
Las figuras 11 y 12 muestran un diagrama de
bloques y un diagrama de flujo según una realización de la presente
invención respectivamente.
Con referencia a la figura 11, un bloque 912 de
permutación de vectores de fila (o generador de índices de
permutación de vectores de fila) genera un índice para seleccionar
un vector de fila según el conteo de un contador 911 de fila, y
proporciona el índice generado a una memoria intermedia de
direcciones altas de la memoria 918 intermedia de direcciones. El
bloque 912 de permutación de vectores de fila es un seleccionador
de grupo para seleccionar secuencialmente o de manera aleatoria,
cuando la palabra de información de entrada está dividida en una
pluralidad de grupos, los grupos divididos. Un bloque 914 de
permutación de vectores de columna (o generador de índices de
permutación de elementos de vector de columna) genera, en función de
un logaritmo 915 PIL modificado, un índice para permutar las
posiciones de los elementos en el vector (o grupo) de fila
correspondiente según un conteo de un contador 913 de columna, y
proporciona el índice generado a una memoria intermedia de
direcciones bajas de la memoria 918 intermedia de direcciones. El
bloque 914 de permutación de vectores de columna es un dispositivo
de aleatorización para permutar la posición de los bits de
información en el grupo, que se almacenaron secuencialmente en el
orden de entrada según una regla determinada. Una memoria 917 RAM
("Random Access Memory", memoria de acceso aleatoria) almacena
datos temporales generados en el proceso del programa. Una tabla
916 de consulta almacena parámetros para el intercalado y la raíz
primitiva. Las direcciones obtenidas mediante permutación de fila y
permutación de columna (es decir, las direcciones almacenadas en la
memoria 918 intermedia de dirección) se usan como direcciones para
el intercalado.
La figura 12 muestra un diagrama de flujo del
algoritmo PIL modificado. Una descripción a continuación se refiere
a la segunda etapa, caso-B, en el algoritmo PIL. Con
referencia a la figura 12 se selecciona una raíz g0 primitiva a
partir de una tabla de constantes de inicialización aleatoria
determinada, en la etapa 1011. Después, en la etapa 1013 se genera
una secuencia C(i) de base para aleatorizar los elementos (o
bits de información) del grupo empleando la fórmula siguiente.
C(i)=[g0 \ x \
C(i-1)] \ mod \ p, \ i=1, \ 2, \ 3, ..., \
p-2, \
C(0)=1
Después en la etapa 1015 se calcula un conjunto
de números primo mínimo {q_{j}, j = 0, 1, 2, ...,
R-1} dado para el algoritmo. Entonces, en la etapa
1017 se calcula un conjunto de números primo {p_{j}, j = 0, 1, 2,
..., R-1} a partir del conjunto de números primo
mínimo calculado. A continuación, en la etapa 1019, los elementos de
un grupo de orden j se aleatorizan en el siguiente método.
C_{j}(i)=c([i
\ x \ p_{j}] \ mod \ (p-1), \ i=0, \ 1, \ 2, \ 3,
..., \
p-2
C_{j}(p-1)=0
\vskip1.000000\baselineskip
En este caso, para incrementar la distancia
libre mínima del turbo codificador mientras se aleatorizan los
elementos del grupo, uno de B-5-1) a
B-5-6) se selecciona para permutar
(o desplazar) los bits de información existentes en la última parte
de la trama a otras posiciones tras el intercalado.
B-5-1) significa
que las posiciones del primer bit de información y el último bit de
información en el último grupo se intercambian entre sí.
B-5-2) significa que los dos últimos
bits de información en el último grupo se intercambian entre sí.
B-5-3) significa que para cada
grupo, el bit de información existente en la última posición y el
bit de información existente en la primera posición se intercambian
entre sí. B-5-4) significa que para
cada grupo, se intercambian las posiciones de los dos últimos bits
de información. B-5-5) significa
que para cada grupo se busca una posición k óptima para una regla de
intercalado dada para intercambiar una posición del bit de
información existente en la última posición de cada fila con una
posición del bit de información existente en la posición k.
Finalmente, B-5-6) significa que
para el último grupo, se busca una posición k óptima para una regla
de intercalado dada para intercambiar una posición del bit de
información existente en la última posición con una posición del
bit de información existente en la posición k.
Aplicando el algoritmo modificado al dispositivo
PIL de intercalado es posible impedir una disminución en la
distancia libre del turbo codificador. La tabla 2 a continuación
muestra un espectro de peso del dispositivo PIL de intercalado
antes de la modificación y la tabla 3 a continuación muestra un
espectro de peso del dispositivo PIL de intercalado después de la
modificación.
En las tablas 2 y 3, K indica el tamaño de la
trama de información de entrada, Dlibre(1) indica una
distancia libre calculada con el CISP para el que la palabra de
información de entrada tiene el peso Hamming 1, y Dlibre(2)
indica una distancia libre calculada con el CISP para el que la
palabra de información de entrada tiene el peso Hamming 2. Por
ejemplo, para K = 600, Dlibre(1) del dispositivo PIL de
intercalado original se indica mediante 25/39/49/53/57/... en la
tabla 2, y esto significa que la distancia libre mínima es 25 y la
siguiente distancia libre mínima es 39. De manera similar,
Dlibre(2) = 38/38/42/... significa que la distancia libre
mínima es 38. Por tanto se observa que la distancia libre mínima se
determina según la distancia libre mediante el CISP con el peso
Hamming 1. Para impedir una disminución en la distancia libre
mediante el CISP con el peso Hamming 1, la invención utiliza el
método B-5-1) en este ejemplo. Es
decir, se mejora Dlibre(1) eliminando el CISP con el peso
Hamming 1.
La tabla 2 a continuación muestra un espectro de
peso del dispositivo PIL de intercalado antes de la
modificación.
La tabla 3 muestra a continuación un espectro de
peso del dispositivo PIL de intercalado después de la
modificación.
Tal como se ha descrito anteriormente, el turbo
codificador novedoso suprime una disminución en la distancia libre
provocada por uno o más bits de información de "1" situados en
el último periodo de una entrada de trama de datos al codificador
de componentes, utilizando el dispositivo de intercalado interno,
contribuyendo así a la implementación de un turbo codificador con
alto rendimiento.
Claims (3)
1. Turbo codificador que comprende:
un primer codificador (111) dispuesto para
codificar una trama de bits K de información de entrada para generar
primeros símbolos codificados;
un dispositivo (112) de intercalado dispuesto
para escribir secuencialmente los bits K de información de entrada
en una matriz rectangular R x C fila por fila comenzando en la
primera columna de la primera fila, permutar dentro de la fila las
posiciones de los bits de información en la matriz rectangular R x C
en cada fila según una regla de intercalado dada, en el que dicha
permutación dentro de la fila deja las posiciones de los bits en la
última columna de dicha matriz sin cambiar después de dicha
permutación, intercambiar la posición del bit de información en la
última columna de la última fila con una posición dentro de la
última fila que precede a la última columna, realizar permutaciones
entre filas de la matriz rectangular R x C, y leer los bits de
información desde la matriz rectangular R x C permutada columna por
columna comenzando en la primera fila de la primera columna; y
un segundo codificador (113) dispuesto para
codificar los bits de información leídos para generar segundos
símbolos codificados,
en el que la matriz rectangular R x C tiene R
filas y C columnas, K = R x C y especifica el número de bits de
información de entrada en la trama, y K > R > 1.
2. Turbo codificador según la reivindicación 1,
en el que el turbo codificador se dispone adicionalmente para
almacenar los bits de información de entrada en una memoria, para
realizar el intercalado de los bits de información en la matriz
rectangular R x C basándose en direcciones de lectura generadas
correspondientes a la matriz rectangular R x C permutada, y para
emitir los bits de información desde la memoria mediante las
direcciones de lectura generadas.
3. Turbo codificador según la reivindicación 1,
en el que el turbo codificador se dispone adicionalmente para
intercambiar una posición de un bit de información en la última
columna de la última fila con una posición de un bit de información
en la primera columna de la última fila.
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR19990018928 | 1999-05-19 | ||
| KR99-018928 | 1999-05-19 | ||
| KR19990018560 | 1999-05-21 | ||
| KR99-018560 | 1999-05-21 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2275508T3 true ES2275508T3 (es) | 2007-06-16 |
Family
ID=26635221
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES03019290T Expired - Lifetime ES2408118T3 (es) | 1999-05-19 | 2000-05-19 | Aparato y método de intercalado turbo. |
| ES00927908T Expired - Lifetime ES2275508T3 (es) | 1999-05-19 | 2000-05-19 | Aparato y metodo de intercalado turbo. |
Family Applications Before (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES03019290T Expired - Lifetime ES2408118T3 (es) | 1999-05-19 | 2000-05-19 | Aparato y método de intercalado turbo. |
Country Status (14)
| Country | Link |
|---|---|
| US (2) | US6598202B1 (es) |
| EP (6) | EP1097516B1 (es) |
| JP (1) | JP3359912B1 (es) |
| CN (6) | CN1271796C (es) |
| AT (1) | ATE349108T1 (es) |
| AU (1) | AU752231B2 (es) |
| CA (1) | CA2337918C (es) |
| CY (2) | CY1105921T1 (es) |
| DE (2) | DE20023169U1 (es) |
| DK (2) | DK1367726T3 (es) |
| ES (2) | ES2408118T3 (es) |
| IL (2) | IL140661A (es) |
| PT (2) | PT1097516E (es) |
| WO (1) | WO2000070771A1 (es) |
Families Citing this family (40)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE20023169U1 (de) | 1999-05-19 | 2003-04-24 | Samsung Electronics Co., Ltd., Suwon, Kyonggi | Turbo-Verschachtelungsvorrichtung |
| US6789218B1 (en) * | 2000-01-03 | 2004-09-07 | Icoding Technology, Inc. | High spread highly randomized generatable interleavers |
| US7302621B2 (en) * | 2000-01-03 | 2007-11-27 | Icoding Technology, Inc. | High spread highly randomized generatable interleavers |
| JP2001285077A (ja) * | 2000-03-31 | 2001-10-12 | Mitsubishi Electric Corp | 通信装置および通信方法 |
| US6854077B2 (en) * | 2000-08-05 | 2005-02-08 | Motorola, Inc. | Apparatus and method for providing turbo code interleaving in a communications system |
| FR2823923A1 (fr) * | 2001-04-18 | 2002-10-25 | Koninkl Philips Electronics Nv | Procede et ensemble d'interconnexion sans fil pour etablir une communication bidirectionnelle entre deux dispositifs audio et/ou video |
| US7085969B2 (en) * | 2001-08-27 | 2006-08-01 | Industrial Technology Research Institute | Encoding and decoding apparatus and method |
| JP3624874B2 (ja) * | 2001-11-19 | 2005-03-02 | 日本電気株式会社 | インターリービング順序発生器、インターリーバ、ターボエンコーダ、及びターボデコーダ |
| US7586993B2 (en) * | 2001-12-06 | 2009-09-08 | Texas Instruments Incorporated | Interleaver memory selectably receiving PN or counter chain read address |
| JP3669433B2 (ja) * | 2001-12-25 | 2005-07-06 | ソニー株式会社 | インターリーブ装置及びインターリーブ方法、符号化装置及び符号化方法、並びに復号装置及び復号方法 |
| CN1324811C (zh) * | 2002-02-06 | 2007-07-04 | 三星电子株式会社 | 通信系统中的交织器和交织方法 |
| RU2292654C2 (ru) * | 2002-08-13 | 2007-01-27 | Нокиа Корпорейшн | Символьное перемежение |
| US7620111B2 (en) | 2002-08-13 | 2009-11-17 | Nokia Corporation | Symbol interleaving |
| WO2004030225A1 (en) * | 2002-09-25 | 2004-04-08 | Koninklijke Philips Electronics N.V. | Circuit for recursively calculating data |
| US20040103359A1 (en) * | 2002-11-27 | 2004-05-27 | Molina Robert Jose | Dynamic real time generation of 3GPP turbo decoder interleaver sequence |
| KR100518295B1 (ko) * | 2003-03-14 | 2005-10-04 | 삼성전자주식회사 | 디지털 통신 시스템의 디인터리빙장치 및 그의디인터리빙방법 |
| EP1770892A3 (en) * | 2003-08-29 | 2007-04-18 | Mitsubishi Electric Information Technology Centre Europe B.V. | Method for transmitting in an optimal manner interleaved data in a MIMO telecommunication system |
| US8077743B2 (en) * | 2003-11-18 | 2011-12-13 | Qualcomm Incorporated | Method and apparatus for offset interleaving of vocoder frames |
| JP4539107B2 (ja) * | 2004-02-12 | 2010-09-08 | 富士通株式会社 | 送信装置、ビット配置方法 |
| JP4909498B2 (ja) | 2004-02-27 | 2012-04-04 | 日本電気株式会社 | インターリーブパラメータ演算方法／プログラム／プログラム記録媒体／装置、携帯電話機 |
| TWI237448B (en) * | 2004-04-12 | 2005-08-01 | Benq Corp | Method for interleaving data frame and circuit thereof |
| KR20060004198A (ko) * | 2004-07-08 | 2006-01-12 | 삼성전자주식회사 | 이동통신 시스템에서 블록 디인터리버 버퍼의 운용 방법및 장치 |
| KR101131323B1 (ko) * | 2004-11-30 | 2012-04-04 | 삼성전자주식회사 | 이동통신 시스템에서 채널 인터리빙 장치 및 방법 |
| WO2006082923A1 (ja) * | 2005-02-03 | 2006-08-10 | Matsushita Electric Industrial Co., Ltd. | 並列インターリーバ、並列デインターリーバ及びインターリーブ方法 |
| US20070011557A1 (en) * | 2005-07-07 | 2007-01-11 | Highdimension Ltd. | Inter-sequence permutation turbo code system and operation methods thereof |
| KR100708474B1 (ko) * | 2005-09-15 | 2007-04-18 | 삼성전자주식회사 | 선형 합동 인터리버의 매개변수 결정 방법 및 그를 이용한 선형 합동 인터리버 |
| DE102006026895B3 (de) * | 2006-06-09 | 2007-11-08 | Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. | Interleaver-Vorrichtung, Empfänger für ein von der Interleaver-Vorrichtung erzeugtes Signal, Sender zum Erzeugen eines Sendesignals, Verfahren zum Verarbeiten eines Codeworts, Verfahren zum Empfangen eines Signals und Computer-Programm |
| US8379738B2 (en) | 2007-03-16 | 2013-02-19 | Samsung Electronics Co., Ltd. | Methods and apparatus to improve performance and enable fast decoding of transmissions with multiple code blocks |
| US8386878B2 (en) | 2007-07-12 | 2013-02-26 | Samsung Electronics Co., Ltd. | Methods and apparatus to compute CRC for multiple code blocks |
| US8296627B2 (en) * | 2007-07-20 | 2012-10-23 | Electronics And Telecommunications Research Institute | Address generation apparatus and method of data interleaver/deinterleaver |
| CN101359977B (zh) * | 2007-08-02 | 2012-09-26 | 财团法人工业技术研究院 | 适用于数据切换多路复用的方法及装置 |
| US8555148B2 (en) * | 2007-09-18 | 2013-10-08 | Samsung Electronics Co., Ltd. | Methods and apparatus to generate multiple CRCs |
| US8161360B1 (en) * | 2007-10-31 | 2012-04-17 | Link—A—Media Devices Corporation | Integrated interleaved codes |
| US8200733B1 (en) | 2008-04-15 | 2012-06-12 | Freescale Semiconductor, Inc. | Device having interleaving capabilities and a method for applying an interleaving function |
| US8982832B2 (en) * | 2008-04-28 | 2015-03-17 | Qualcomm Incorporated | Wireless communication of turbo coded data with time diversity |
| US20110047434A1 (en) * | 2008-04-28 | 2011-02-24 | Qualcomm Incorporated | Wireless communication of turbo coded atsc m/h data with time diversity |
| US8612820B2 (en) * | 2009-04-11 | 2013-12-17 | Qualcomm Incorporated | Apparatus and methods for interleaving in a forward link only system |
| CN101931419B (zh) * | 2009-06-24 | 2013-04-03 | 中兴通讯股份有限公司 | 一种turbo码内交织器的计算方法及装置 |
| DE102011006112B4 (de) * | 2011-03-25 | 2024-01-18 | Siemens Aktiengesellschaft | Elektrischer Schalter und Überstromauslösemodul |
| US9160370B2 (en) * | 2014-01-02 | 2015-10-13 | Oracle International Corporation | Single component correcting ECC using a reducible polynomial with GF(2) coefficients |
Family Cites Families (27)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| NL186790C (nl) | 1980-07-14 | 1991-02-18 | Philips Nv | Werkwijze voor het coderen van een reeks van blokken tweetallige databits in een reeks van blokken van tweetallige kanaalbits, alsmede modulator, demodulator en registratiedrager te gebruiken bij de werkwijze. |
| US4802170A (en) * | 1987-04-29 | 1989-01-31 | Matrox Electronics Systems Limited | Error disbursing format for digital information and method for organizing same |
| FR2675971B1 (fr) | 1991-04-23 | 1993-08-06 | France Telecom | Procede de codage correcteur d'erreurs a au moins deux codages convolutifs systematiques en parallele, procede de decodage iteratif, module de decodage et decodeur correspondants. |
| US5483541A (en) * | 1993-09-13 | 1996-01-09 | Trw Inc. | Permuted interleaver |
| US5548775A (en) * | 1993-12-30 | 1996-08-20 | International Business Machines Corporation | System and method for adaptive active monitoring of high speed data streams using finite state machines |
| US5446474A (en) | 1994-01-19 | 1995-08-29 | Lockheed Missiles & Space Company, Inc. | Redeployable furlable rib reflector |
| US5537420A (en) * | 1994-05-04 | 1996-07-16 | General Instrument Corporation Of Delaware | Convolutional interleaver with reduced memory requirements and address generator therefor |
| KR970036265A (ko) | 1995-12-29 | 1997-07-22 | 한승준 | 무릎 보호용 완충 패드가 장착된 자동차의 인스트루먼트 패널 |
| KR0176888B1 (ko) | 1996-01-24 | 1999-04-15 | 구자홍 | 광디스크 기록재생기의 서보 제어 장치 |
| US5996104A (en) | 1996-09-13 | 1999-11-30 | Herzberg; Hanan | System for coding system |
| US6035434A (en) * | 1997-06-12 | 2000-03-07 | Advanced Micro Devices, Inc. | System and method for bit interleaving of half-rate speech data |
| US6101465A (en) * | 1997-06-12 | 2000-08-08 | Advanced Micro Devices, Inc. | System and method for bit interleaving of full-rate speech data |
| KR19990012821A (ko) * | 1997-07-31 | 1999-02-25 | 홍성용 | 전자기파 흡수체 조성물과 이의 제조 방법, 전자기파 흡수용도료 조성물과 이의 제조 방법 및 이의 도포 방법 |
| WO1999012265A1 (en) | 1997-09-02 | 1999-03-11 | Sony Corporation | Turbo-coder/decoder and turbo-coding/decoding method |
| US6437714B1 (en) | 1998-04-18 | 2002-08-20 | Samsung Electronics, Co., Ltd. | Channel encoding device and method for communication system |
| EP0963049B1 (en) * | 1998-06-01 | 2007-08-01 | Her Majesty The Queen In Right Of Canada as represented by the Minister of Industry | Interleaving with golden section increments |
| US6007995A (en) | 1998-06-26 | 1999-12-28 | Isis Pharmaceuticals Inc. | Antisense inhibition of TNFR1 expression |
| DE69936626T2 (de) | 1998-08-06 | 2008-05-21 | Samsung Electronics Co., Ltd., Suwon | Kanalkodierung und -dekodierung für ein kommunikationssystem |
| KR100373965B1 (ko) * | 1998-08-17 | 2003-02-26 | 휴우즈 일렉트로닉스 코오포레이션 | 최적 성능을 갖는 터보 코드 인터리버 |
| BR9906704A (pt) * | 1998-08-20 | 2000-08-08 | Samsung Electronics Co Ltd | Dispositivo de turbo codificação, e, processo para inserir um bit especìfico em um turbo codificador |
| US6704370B1 (en) * | 1998-10-09 | 2004-03-09 | Nortel Networks Limited | Interleaving methodology and apparatus for CDMA |
| KR100453605B1 (ko) | 1998-10-13 | 2004-10-20 | 인터디지탈 테크날러지 코포레이션 | 터보 코드용 하이브리드 인터리버 |
| US6304991B1 (en) | 1998-12-04 | 2001-10-16 | Qualcomm Incorporated | Turbo code interleaver using linear congruential sequence |
| FI106493B (fi) | 1999-02-09 | 2001-02-15 | Nokia Mobile Phones Ltd | Menetelmä ja järjestelmä pakettimuotoisen datan luotettavaksi siirtämiseksi |
| DE20023169U1 (de) | 1999-05-19 | 2003-04-24 | Samsung Electronics Co., Ltd., Suwon, Kyonggi | Turbo-Verschachtelungsvorrichtung |
| KR100393608B1 (ko) * | 2000-09-29 | 2003-08-09 | 삼성전자주식회사 | 유.엠.티.에스시스템내 터보부호화기의 내부 인터리버 및인터리빙 수행 방법 |
| EP1576735B1 (en) * | 2002-12-16 | 2016-04-06 | Telecom Italia S.p.A. | Address generation for interleavers in turbo encoders and decoders |
-
2000
- 2000-05-19 DE DE20023169U patent/DE20023169U1/de not_active Expired - Lifetime
- 2000-05-19 WO PCT/KR2000/000504 patent/WO2000070771A1/en not_active Ceased
- 2000-05-19 CN CNB2003101043218A patent/CN1271796C/zh not_active Expired - Lifetime
- 2000-05-19 DE DE60032441T patent/DE60032441T2/de not_active Expired - Lifetime
- 2000-05-19 EP EP00927908A patent/EP1097516B1/en not_active Expired - Lifetime
- 2000-05-19 US US09/575,084 patent/US6598202B1/en not_active Ceased
- 2000-05-19 CN CNB008014299A patent/CN1171393C/zh not_active Expired - Lifetime
- 2000-05-19 EP EP03019292.6A patent/EP1367730B1/en not_active Expired - Lifetime
- 2000-05-19 DK DK03019290.0T patent/DK1367726T3/da active
- 2000-05-19 CN CNB2003101043186A patent/CN100442679C/zh not_active Expired - Lifetime
- 2000-05-19 JP JP2000619112A patent/JP3359912B1/ja not_active Expired - Lifetime
- 2000-05-19 PT PT00927908T patent/PT1097516E/pt unknown
- 2000-05-19 EP EP03019290A patent/EP1367726B1/en not_active Expired - Lifetime
- 2000-05-19 CN CNB2003101043190A patent/CN1271795C/zh not_active Expired - Lifetime
- 2000-05-19 ES ES03019290T patent/ES2408118T3/es not_active Expired - Lifetime
- 2000-05-19 EP EP03019291A patent/EP1367729A1/en not_active Ceased
- 2000-05-19 CN CNB2003101043203A patent/CN1274096C/zh not_active Expired - Lifetime
- 2000-05-19 ES ES00927908T patent/ES2275508T3/es not_active Expired - Lifetime
- 2000-05-19 CN CNB2003101043171A patent/CN100574116C/zh not_active Expired - Lifetime
- 2000-05-19 DK DK00927908T patent/DK1097516T3/da active
- 2000-05-19 AU AU46213/00A patent/AU752231B2/en not_active Expired
- 2000-05-19 CA CA002337918A patent/CA2337918C/en not_active Expired - Lifetime
- 2000-05-19 EP EP03019289A patent/EP1367728A1/en not_active Ceased
- 2000-05-19 AT AT00927908T patent/ATE349108T1/de active
- 2000-05-19 IL IL140661A patent/IL140661A/en not_active IP Right Cessation
- 2000-05-19 PT PT3019290T patent/PT1367726E/pt unknown
- 2000-05-19 EP EP03019293A patent/EP1367731A1/en not_active Ceased
-
2004
- 2004-10-25 US US10/973,100 patent/USRE43212E1/en not_active Expired - Lifetime
-
2005
- 2005-06-30 IL IL169471A patent/IL169471A/en not_active IP Right Cessation
-
2007
- 2007-01-11 CY CY20071100045T patent/CY1105921T1/el unknown
-
2013
- 2013-05-16 CY CY20131100397T patent/CY1114077T1/el unknown
Also Published As
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| ES2408118T3 (es) | Aparato y método de intercalado turbo. | |
| JP3359913B1 (ja) | 移動通信システムの直列鎖状コンボルーション符号化器に使用するためのインタリーバ及びそのインタリービング方法 | |
| US6334197B1 (en) | Turbo code interleaver with near optimal performance | |
| US6591381B1 (en) | 2-dimensional interleaving apparatus and method | |
| KR100330234B1 (ko) | 터보 인터리빙 장치 및 방법 | |
| RU2212103C2 (ru) | Устройство и способ для турбоперемежения | |
| KR100645730B1 (ko) | 매직 매트릭스를 이용한 인터리빙 방법 | |
| KR100362557B1 (ko) | 이차원 인터리빙 장치 및 방법 |