baja complejidad

SECTOR TÉCNICO

La invención se refiere a comunicaciones digitales, en particular a sistemas -y métodos asocia-dos a. la decodiiteación iterativa basada en el algoritmo SOYA ($&β Quípui Viterhi Aigor km que pueden ser aplicados a estándares- de eomimicaeiorjes móviles como- 3GPP { ré Gemr ion P rtmship -Pr j ct%. LTE (Long Term Evt>iuti n}-y UMTS (ÍJmvers l MobHe Tekcommtm atí m S íem Más- particularmente, la J&veiKáóa s refiere a sistemas y métodos para íurh decodiiseaeión iterativa paralela para los que ríese requiere el sola amiento entre sub- loques adyacentes, reduciendo así la latericia de deeodillcacíón de forma drástica. t&m miA TÉCNICA

Los iirtbo códigos m. sido aíuplíataeate: usados en estándares de comunicaciones móviles modernos debido a su enorme capacidad correctiva qu permite transmisío»es de datos fiables- cercanas a la capacidad ergódka del sistema. El ^' turbo codificador consiste en la concatenación en paralelo de dos codificadores RSC (Reeursive Systematic Convoiniional) separados por un entrelazador que aporta aleaioriedad al código. La deeodifieáción consiste en un proceso iterativo en el que se genera (en cada iteración) la ínfercnaeió extónseca, que es usada como info iaeión a-pr rí en la siguiente iteración. Esto permite asar un criterio MAP ( ximu Á-Posteriorí) que minimiza la tasa de error o BER (Bit Error Raíe El turbo deeodiicador clásico usa «n decodiicador SISO- (Soft n S ^' ofi O t}qu genera información extrínseca en la roana de valores LL (Log LikelihowÍ ilo) dos entrelazadores, uno para ios. datos recibidos del canal y otro par la información extrínseca, La Fig. 1 Ilustra el diagrama tuoeional -de un turbo decodilkador clásico. En diefea ligara, el elemento SISO 1 decodiíica el mensaje mientras que el elemento SISO 2 decodiíic el mensaje entrelazado. Se dice que keraeiones completas deeodífíeao, e! mensaje mientras que las seral-ilcraeiones decodiSean el mensaje entrelazado. El diagrama funcional de la Fig, I puede ser ímpleraentado d diferentes íbrtnas que se identifican en este documento como; (.1) turbo decorticación en serie, (2) turbo decodifícación concurrente y (3) turbo deeodífieacíóo barajada.

En la Vig. 2 se muestra un diagrama, funciona! de turbo decíxilfieación en serie, donde la línea horizontal representa el tiempo. Nótese que, debido al hecho de que SISO S 2 tiene que esperar hasta que SISO ! haya decodíficado ef bloque completo, esta arquitectura se puede irnplemeníar usando sólo un decodiikador SISO. L i . 3 es un esquema funcional de la turbo decodifícación concurrente. Mótese que en la literatur el termino turbo decodiñeaeién paralela es comúnmente osado para referirse ai método que hemos denominado aquí turbo decodifícación concurrente; sin embargo en. este0 documento hemos preferido reservar el termino "pajtalek' ^*' para otro tipo de arquitectura que va a ser explicada posteriormente. En la turbo decodífíeación concurrente las iteraciones completas y semi-iteraeiones se realizan ai mismo tiempo por un deeodillcador SISO distinto: uno decodifica el mensaje y el otro el mensaje entrelazado _* Por tanto se increment la velocidad de convergencia de l deeodiileación, ElS intercambio de información extrínseca está representado con flechas negras en dicha figura. En la Fig. 4 se representa otra arquitectura conocida como turbo deeodiScaeién barajada. Esta ar uitectura requiere dos decodifícadores SISO como en la arquitectura concurrente, Sin embargo en esto caso se permite que la información a-prior sea intercambiada entre ambos decodifícadores en la misma iteración siempre que dicha0 infoonación esté disponible. Dicha arquitectura acelera la velocidad de convergencia aun más que la turbo deeodlicaekVn concurrente, si embargo requiere un mecanismo de acceso a memoria ^' bastante complejo. En Juntan hang y otros "Shuffled. iterative decoding" trabajo publicado en la revista IEEE Transactíons on (Communications,, vol 53, 2005 y en las referencias presentes en dicho trabajo se puede obtener más5 información acerc de esta arquitectura para la decodifícación con turbo códigos.

Debido al hecho de qué la turbo decodiñeaeión en serie e la m s extendida normal-mente nos referiremos a est arquitectura en el presente documento.

Existen esencialmente dos familias de algoritm SISO par la turb decodifícación: MAP (M ximum A Posteriori) y SOVA (Soft Ootput Viterbi0 Al orithm). Una descripción detallada de estos algoritmos se puede encontrar en "Comparative study of turb decoding techniques: an overvie * publicada fa revista IEEE Iransaet oBon Vehicular Technology, vol 49, 2( 00 por Woodard y otros. El algoritm MAP ofrece una gananci de decodifícación de aproximadamente 0.6 dB sobre el SOVA a expensas de tene mayor laíencia y mayor consumo de área del ehip incluso en sus versiones simplificadas Max-Log-MAP y Log-MAP. Se han realizado algunas propuestas con el fin de reducir esta diferencia en. ganancia de deeodífícaeión debido a las atractivas características del algoritmo SOVÁ para iniple eátaeión eficiente en el chip. En concreto, Possorier otros presentaron en el articulo titulado "On ihe .equivalente between SOVA and max-log-MAF decodings", publicado en ía revista IEEE Gommunícatlon Leííers, yol. 2. 1998 una modificación, del algoritmo SOYA que lo hace equivalente al algoritmo Max-Log-MAP. Desai rtimada ente el algoritmo propuesto es significativamente más complejo que d algoritmo SOVA original En el artículo "Adapn ^' ve SOVA. for 3GPP-LTE. eceivers" de Bianquez- Gasado y otros, publicado en la revista IEEE Coíamankatíons Le ters, voLl S, junio 2014 se presenta una modi ^' fica ión del algoritmo SOYA que mejor significativamente la capacidad correctiva, especialmente cuando se emplean altas tasas de modulación y codificación. Sin embargo el algoritmo propuesto requiere emplear un ventana de actualizació de pesos de tamaño variable que hace difícil su impiementaelón en un chíp.

Una alternativa la constituye el algoritmo conocido com BÍSOVA (B ireetional SOVA) e el que dos decodifeadores SOVA ¿«codifica» la secuencia recibida en cada iteración haciendo que la capacidad correctiva sea similar á la del algoritmo MAP; no obstante la complejidad se duplica también, lista propuesta fue presentada por primera vez por Chen y otros con el artículo titulado "Bi-directlonal SOVA decoding í r turbo- eodes" publicado en la revista IEEE Co murtication Letters, vol. 4, 2000, Una arquitectura par impleroentar dicha- algoritmo que es eficiente desde el punto de vista del uso de la memoria &e presentada por Bfirnóy y oíros en la patente titulada "HlGS-í- TRWmEWT ME ORY-EEFÍG1E T 81-S0 A BECOPER AECHITECTURE US 2008/0152043 Al, No obstante esta arquitectura al esta basada en el algoritmo BISOVA sigue presentando mayor complejidad que las basadas en el algoritmo SOVÁ.

BÍSOV A requiere dos ¿«codificadores SOYA, o dos bancos de decodificadores SOVA en el caso paralelo trabajando a la vez en cada iteración. La idea clave detrás del algoritmo BISOVA es que realizar el algoritmo SOVA en. diferentes direcciones pertHite obtener una información distinta que ayuda a mejorar la. turbo deeodificaclón. En. el algoritmo SOVA existe m proceso de actualización que persigue mejorar la calidad de ios pesos, o medidas de ñabiHdad, asociadas a cada bit deeodificado para la etapa k coa el fui de obtener las medidas a-posteriori LLR finales, liste proceso de actualización compara fiabilidades o pesos asociadas al camino ML (Máximum Likelihood) en k etapa k con las iiabilidades de los caminos competidores a! camino MI, que se unen a él y son descartados en etapas posteriores a k. Sin embargo, hay caminos que no se tienen en. cuenta en el proceso de actualización porque son descartados antes de mezclarse con- el canino ML. Este hecho d lugar a una sobrestimacíón de las medidas a-posterioá ea SO¥A que reduce su capacidad correctora. No obstante, algunos caminos que son descartados antes de unirse al camino ML en una dirección pueden no ser descartados antes de unirse a dicho camino ML en la otra dirección, Por tanto, realizar el algoritmo SOYA en ambas direcciones puede mejorar la turbo decodifícaeión, Bn el algoritmo BiSOVA, en la iteración i, uno de los dec difícadores calcula las medidas LLR a-posterior! hacía adelante, identificadas con el símbolo L ^U {% mientras que el otro las calcula hacia atrás, identificadas con el símbolo L ^<J ' (Uk). Entonces, las medidas a-posteriori finales en BISOVA puedes ser calculadas como

mejorando notablemente la capacidad correctora a sosia de doblar el consumo de áre del ehip.

La naturaleza iterativa de la turbo decodificación tiene asociada una lateada considerable que hace diñeil cumplir los requisitos de régimen binario asociado con estándares modernos como LXE (Long Term Evolution). Debido a esto la deeodifkactén paralela se hace imprescindible. En la decodíiicaeíón paralela cada bloque a decddificar es dividido en varios sub-bl q es que son decodificados al mismo tiempo por un decodiíkado SISO diferente. pesa de que esta estrategia permite reducir l lateada effcl nteajente, la paralelizacié tiene do grandes inconvenientes; (I) el consumo de área del circuito integrado es mayor y (2) hay .una pérdida no despreciable en capacidad correctiva debido a la incertidumbre que existe en los bordes entre sub-bloques. Con el propósito de aliviar esta degradación de prestaciones, algunas técnicas se lian propuesto en la literatura _» estando l mayoría de ellas centradas en el algoritmo MAP. Un solape entre sub-bloques es propuesto por Hsii y otros en "A parallel decoding scheme t r turbo codes", publicado en el congreso de IEEE International Svmpósiorn on Circuits and Systems de 1998. Desafortunadamente esta técnica también aumenta la latericia de deeoddleaeión. On método para l decod caeión paralela basada en el algoritmo MAP qu usa la infonnacién de borde entre sub~bloques fue propuesto por Yoon en "A parallei MAP algorithrn fot Jow latency turbo deeoding". publicado en l resista IEEE Coniinimieaíkms Lettem, en 2002. Este método paralelo, conocido como SBI (Sub-block Boundary I¾fo.fmaíÍo») _f consigue para el algoritmo- MAP simulares capacidades correctivas que la versión no paralela sin ningún impacto en la lateada; cosa que no ocurre en las alternativas basadas en solape, ^: o obstante ai estar basado en el algoritmo MAP no ofrece las ventajosas características de bajo consumo de recursos que presenta el algoritmo SOYA.

Como con la decodífieación paralela el consumo de área resulta »« tema crítico el al oritmo SO VA se hace muy «Iraeti vo.

Turbo ^■ decodífieación clásica parale Ία con í&p

En la F ig. 5 se ilustra una. descripción, funcional de la decodifíeación paralela usando solape entre sub~bioques. S ^' e asume» códigos con terminación trellis como es el caso del código de LTE, es decir, el. estado inicial y final es conocido, siendo comúnmente el estado cero. La longitud del bloque a deeodrfiear es K+T donde es la longitud del mensaje y T el número dé etapas requeridas para volver al estado cero. En el caso de tener P deeodificadores SISO trabajando en paralelo cada siib-bioque tiene una longitud de M~HL etapas except el ultimo sub»bloque que tien una longitud de M- L 2*T etapas y el primer sub-bloqne de siendo M- P y L el número de etapas de solape. La secuencia decodiíkada por cada deeodifieador tiene una longitud de M bits,

Se define el lado izquierdo del sub-bloque n, identificado con el símbolo k^, como ja etapa en la qm deberían hricializarse las métricas de camino o FMs (Fath Metncs), El lado dere no, identificado con el símbolo k _TiKí se define como la etapa e la que el último recorrido hacia atrás o TB (Trace Baek) debería ser iniciado. El in4i.ee de bloque n va de 1 a P. La í ciaíkación de las P s se realiza como sigue

( !ogfl Λ'), n≠ l

(2)

\ (S(s}\. n~l donde §( ^♦ } representa la ñineión de Kronecker y PM- ^><e íi ) ^' es la PM para el sab- bloque n, estado s\ iteración i y etapa k _\# y N es el número de estados con ¿V ~ilj. La etapa en la que se realiza la iaicializacidii de las PMs usand solape es k\„ ^::: 0 par n~í y kí,fl™(n-Í )M-L/2 para n>l. La ecuación anterior significa que para el primer sti - bloque (n^l } el estado inicial es conocido, siendo el estado cero, mientras que para el resto de sub-blo ues el estado inicial es desconocido con lo que se realiza un solape de S L/2 etapas para obtener PMs üabies.

El estado S ⁽ - _R desde el que se inicia el último TB en l etapa k,„ es el estado cero para el sub-bkxjue n~P, y cualquier estado para n P, siendo k, W y k _f!Í j ^:: ¾ L 2 para n<i\ Las etapas de solape- garantizan que los estados generados al hacer los recorridos haci atrás converjan al camino ML,

0 En el caso del algoritmo SO¥Á _f las PMs iesdráa valores fiables cerc de los bordes de sub-bloque por el lado derecho siempre que la longitud de los sub4 io ues se mayor qne la ventana de decodifícaeióo. Sin embargo, cuando los recorridos haci atrás o TB empiezan desde el lado derecho, la. Mceiiídimibre en el estado d sde el que se arranca el TB causa muchos errores en la secuencia decodiíkada en el lado derecho del5 snb-bloque. Como l s PMs cercanas al lado derecho del snlvbjoque son fiables, los valores a~posteriori L(%). tomarán valores grandes, indicando gra Habilidad, para- bits íncon-ecíaffiente desedificados. Esta sobre-estimación provoc que aparezcan errores en los limites entre sub-bloques inde^ndientemente de la SNR (Signal o Noise atio) que se tenga> la particular, las PMs por el lad derecho de los sub-bÍ í ues so» Sables0 mientras que los estados usados para iniciar el proceso de TB, que se inicia por la derecha de los sub«bloques, no lo son. Por la parte dereeba de los sub-bloque l situación es la contraría, SC PCÍÓN E LA I E CIÓ

$

AISOKA:

Un primer aspecto de la presente invención se refiere un modificación del algoritmo SOVA que, diferencia de las propuestas mencionadas anteriormente, mejora suü capacidad correctora cuando se aplica a la turb decodifieación sin ningún incremento en el consumo de área ni de iatencia. Esta modificación denominada ÁLSQVA (ALternated dírection SO VA) mejora la capacidad correctiva del algoritmo SOV A sin ningún íncre enío en área consumida del ehip ni de latencia. Por tant este método puede aplicarse a la turbo decodiñeacibn siguiendo diferentes arquitecturas como la arquitectura en serie, la concurrente y la barajada usando realizaciones paralelas y no paralelas de! banco de decodifiea ores SOVA. El algoritmo ALSOVA también puede aplicarse a la ecuallzacíón iterativa _. , de la misma form que los alg oritrnos ÁP y SOVA son usados e» est campo.

El algoritmo ALSOVA se basa en el mismo principio que el algoritmo BISOVA, esto es _? lleva a cabo el proceso de actoaÍÍL¾¾eión en d foreníes direcciones de forma que se reduce la sobrestimaeión de las medite a-¡)osteríorí al tener en cuenta más caminos. Sin embargo, al contrario que el algoritmo BISOVA, el algoritmo ALSOVA. no realiza la decodiíicaolón en ambas direcciones durante la misma iteración. En cambio, e! algoritmo ÁLSÓVA eonipara las med das LLR a-posteriori calculadas hacia delante y hacia atrás a lo largo de distintas iteraciones mediante el iníere&nbio de la iníbraiacíén extrínseca entre iteraciones. Esto permite utilizar un único decodiflcado SOVA en lugar de dos. El decodifieado SOVA tiene que ser capaz de realizar la deeodílieadón tanto hacia adelante como hacia atrás; sin embargo, esta cuestión tiene un impact mínimo en el consum de áre ya que la mayoría de las unidades que forman el decodificador no resultan afectadas. Por tanto, la invención propone calcular la medidas ^' LLR hacia adelante en las iteraciones Impares, y las medidas LLR hacia atrás en las iteraciones pares como se indica a continuación:

siendo I ! la función suelo. En la expresión previa se considera que en na iteraci n completa el mensaje es decodi vcado,. mientras que en cada sexni-iíeración el mensaje entrelazad es deeodlfícado. Las iteraciones comienzan en i ^« =l _? mientras que las se nil - iteraciones comienzan en í ^::: 1.5.

La- sobf estimación de bits erróneamente deeodí fícados tiene -u« considerable efecto en la turbo decodiñeaeión porque puede propagar errores a lo largo de iteraciones. Nuestro enfoque propone realizar la decodificaclón hacia adelante y hacia atrás en ejecuciones impares y pares del deeodifícador, respectivamente. Por tanto, si e la etapa k. un bit decodiflcado erróneamente tiene una LLR sobrestiniada. esta sobrestimación puede propagarse hasta la siguiente semi-iteración. Sin embargo, debido a que la otra iteración va en la dirección contraría, otros caminos pueden ser considerados, mitigando la sobrestinmción y evitando ^' la propagación del error.

El algoritmo ALSOVA propuesto puede implementarse en turbo decodi caeión en serie, paralela o barajada usando tanto una iniplemeniacíó» so paralela de cada decodííieador SISO constituyente: corno una realización paralela de cada deeodiík-ao r SISO constituyente, En el último caso tenemos de hecho un banco de deeodiflcadores SISO, El algoritmo ALSOVA puede usarse también en turbo ee alización: el algoritmo ALSOVA requiere la smpleraentaeión de un deeod cador SOVA hacia adelante/atrás, o- fw b del ingles fonvard back ard,. el cual pueda realizar la deeodifícación eu ambas direcciones en diferentes iteraciones. En este documento se proporciona una realizaci n de dicho deeodifícador. Además se proooreiona una posible realización de mi turbo dee&diSeador usando el algoritmo ALSOVA para las arquitecturas en serie paralela y concurrente paralela. PMSBx

Un se uid aspecto de la presente invención se refiere una nueva a uitectura para h turbo deeodifieáeién en paralelo, identifioada con el acrónimo PMSBx que viene del inglé Path Metríe Síate Border Exchange. Dicha- arquitectura mitiga la degradación de prestaciones en términos de BER (Bit Error Rale) o tasa de error de bit asociada a la deeodiñeació en paralelo. PMSBx emplea el hecho de que las métricas de camino so fiables en el borde derecho de los su -bloques y por tarto pueden ser usadas como métricas de inic lizaeíón para el siguiente sub-bioque de la siguiente iteración,

PMSBx consigue mejores prestaciones que los métodos clásicos basados en solapamlento de sub-bloques. Ai contrario que otros enfoques, PMSBx no requiere solapamiento entre sub-bloques. por tanto reduce la latericia de la decodifícación. El solapamiento tiene la desventaja de que incrementa la iatencia de la decodificación, reduciendo la tasa binaria alcanzahle. Por otra parte» la BER de l turbo decodifícación en paralel sin soiapamiento sufre un degradación significativa debido a la mcettidumbre en los bordes de los sub-bloques,

PMSBx aprovecha Ja diferente fiabi ad. de las PMs ¥ los estados del camino ML para mejorar las prestaciones de la deeodiñeaesón y se basa principalmente en dos premisas: * Convergencia de las métricas de camino; e ido a que el borde izquierdo de un sub-bloque se corresponde con el borde derecho del sub-bloque previo- las PMs del borde derecho de ur¡ sub-bloque pueden ser usadas como PMs iniciales para los ^' siguientes sub~bloques en la siguiente iteración. Esto aprovecha el hecho de que dichas PMs son fiables» Est idea fue explotada por Yooa, "A. patailei MAP aigorithm for lew laíéncy turbo decodíng IEEE Communications Letters, 2002, donde se presenta un método para el algoritmo MAP parálelo que consigue alcanzar la misma, capacidad correctiva que en el caso no paralelo pero sin ningún incremento en iatencia. Este método es identificado en este documento como SB!. En el caso del algoritmo SO VA, las PMs son fiables en el borde derecho de un sub-hkxpe. Por tanto, éstas métricas pueden ser usadas como métricas de inielalización para el siguiente sub-bloque en la siguiente iteración para el caso del algoritmo SOYA.

* ^' Convergencia de los estados para el camino ME: Haciend la inicialización con valores de métrica fiables, los estados del camino ML serán fiables en el borde iz uie d de los süb-bloq es, Estos estados producidos por un decodificador SOVÁ pueden ser -usados, par hacer el último recorrido baoia atrás- o- TB desde un estado fiable del decodificador SOYA, previo, ^: .reá¾é1endo- eon detableniisnte la sob estimacion de los valores LLR a-p sieriori, la cual degrad las prestaciones en términos de BER. Debido a que los estados e el sub-borde izquierdo están disponibles ante de que se lleve a cab el TB en el borde izquierdo, estos estados se pueden Intercambiar en la misma Iteración. Hay que tener en cuenta que esto no es aplicable para, las métricas de camino ya que éstas son intercambiadas entre iteraciones completas,

La combinación de ALSOVÁ y PMSBx permite alcanzar unas prestaciones en términos de BEil cercanas a las que se consiguen con los deeodiík adores basados en el algoritmo MAP y a la ez mantienen, el beneficio de la b t cornple idad asociad al algoritmo SOYA..

La invención también se refiere a (I) programas de ordenador adaptados para, o que comprenden código software adaptado par- , llevar a cabo los métodos de la invención; (íí> medios de almacenamiento legibles en computador que comprenden dichos programas Informáticos o que comprenden instrucciones para hacer que un aparato de procesamiento de datos lleve a cabo los métodos de la invención; _, (ai) medios portadores de grabación con dichos programas informáticos grabados en ellos; (iv) ondas portadoras de seña! portando señales qm Incorporan dichos programas informáticos.. BREVE EXPLICACIÓN ^' I>E LAS FIGURAS

La Fig, I ilustra el diagrama, fisjdonai de la turbo deeodirleaeíón.

La Fig. 2 muestra un diagrama de tiempos de ia turbo decodiikación es sede.

La Fig, 3 mu sc un diagrama de tiempos de la turbo deeodifieación corícoi-rente.

La Fig. 4 muestra u diagrama de tiempos de la turbo decodífieacíón barajada.

La Fig, 5 ilustra un diagrama funcional de deeodifieación paralela usando solape entre su -bíoques.

La f ig. 6 muestra, un diagrama de tiempos de la arquitectura propuesta de turbo. deeodificador en serie usando ALSOVA.

La Fig. 7 ilustra un posible realización de la invención usando la arquitectura serie paralela de turbo decodificación con el algoritmo propuesto ALSOVA.

La Fig, 8 ilustra una posible realización de los deeodíñeadores SO VA íw bw.

La Fig. ilustra una posible realización de la Unidad de Recursión fwá del decodiñeador SOYA fw/¾ .

La Fig, 10 proporciona un diagrama temporal asociado a la arquitectura concurrente usando el algoritmo propuesto ALSOVA.

La Fig. 11. ilustra una posible realización de la invención usando la arquitectura concurrente paralela de turbo deeodifieación con el algoritmo propuesto ALSOVA, La Fig. 12 ilustra la estructura propuesta de P S x adecuada para ei algoritmo ALSOVA,

La Fig. 13 ilustra la estructura propuesta de PMSBx adecuada para los algoritmos SO Ay BiSOVA.

La Fig, 14 ilustra una posible realización de la invención usando la arquitectura serie paralela, de turbo deeodifieación con el métod propuesto PMSBx adecuado para el algoritmo SOYA.

La Fig. í 5 ilustr una posible realización do la invención usando la arquitectura serie paralela de turbo deeodifieación con el método propuesto PMSBx adecuado para el algoritmo BtSOVA. OBOS m REALIZACIÓN DE LA INVENCIÓN

En esta solicitud se re.feren.olan varias publicaciones. Los contenidos y revelaciones inclu das en éstas, asi como en l totalidad, de. las- referencias citadas por dichas publicaciones* se incorporan en la presente solicitud, co el fin de describir de una maner complet y detallada el estado del arte al que- pertenece esta invenc ón. La terjniftología que se emplea en adelante es empleada con el propositó de describir de manera precisa determinado conceptos, y no debe considerarse como limitante. á Ú á

Este primer aspecto de la presente invención mejora la capacidad correctora de errores de un turbo decodiílcador basado en el algoritmo SOYA clásico sin ningún incremento en la complejidad. Est invención puede usarse con turbo decodificación paralela: y no paralela, ^' En la Fig. 5 se ilustra una descripción finicional de la deeodificación paralela usando sol pe entre sub~bloques. Se asumen códigos con terminación trellis como es el caso del código de LTE, es decir, el estado inicial y final es conocido, siendo comúnmente el estado cero. La longitud del bloque a decodifiear es K- ^' T donde K es la longitud del mensaje y T el número de eta as requerida para volver al estado cero. En, el caso de tener P ¿©codificadores SISO trabajando en paralelo cada sub- ioque tiene una longitud de M+L etapas excepto el ultimo siib-bloque que tiene «na longitud de -tL 2-t-T etapas el primer sub-bloque de M-HL 2, siendo -K P y L el numero de etapas de solape, La secuencia decodilicada por cada ¿«codificador tiene- .una longitud de M bife.

AUSÜ- pa a turbo deeodificación en serie paralela

En la Fig. ó se muestra un diagrama de tiempos del método AL-SOYA, propuesto, para deeodifieaeion serie de turbo códigos. Ets concreto se muestran dos iteraciones completas del algoritmo, aunque el proceso de deeodificación puede extenderse a enakrnier número de iteraciones según el criterio de patada determinado.

En la Fig, 7 se presenta una posible realización de la invención siguiendo l arquitectura de un turbo decodificador en serie paralelo. El diagram de bloques de dic&a figura muestra las medidas LLR del canal asociadas con un turbo código de tasa 1/3 con ua bit sistemático y dos bits de paridad como es ei caso del empleado e la tecnología LTE. Estas métricas LLR se representan en ia ligara wm Ls _» Lf>l y Lp2 respeciivarnente. Las métricas Ls y Lpl están relacionadas con el mensaje, mientras que la métrica Ls2 está relacionada con ei mensaje entrelazado. Estas métricas se almacenan 5 en el Banco de Memoria de Entrada 701,. Picha unidad es capas de entregar a cada deeodifieadot paralelo dentro del banco de decodifícadores paralelos ei sub-bloque correspondiente. Además, el Banco de Memoria de Entrada 701 entrelaz las métricas Ls cuando lleva a cabo una semi-iteraeión, pudiendo asi entregar dichas métricas al Banco de Oecodifícadores SOYA í ihaeia delante) bw (hacia airas} 704,

10 El Banco de Deeodiicadores S0VÁ fw b 704 calcul métricas a-posteriori en la dirección hacia delante (iteraciones impares) y hacía atrás (iteraciones pares), respectivamente. De este modo, tanto el Banco de Memoria de Entrada 701 como el Banco de Memoria Extrínseca 705 pueden entregar datos ai Banco de Decodiíkadotes SOVA íw/b 704 en ambas direcciones. La Unidad de Control 702 determin el

15 comportamiento de las diferentes unidades dependiendo de la í temcíon o semi-iteracián que se lleve a cabo en cada momento. La Unidad de <¾íc« Extrínseca 7Θ& calcula l int rmacíón extrínseca utilk do las métricas ^' LLR del cana! y las métricas a-pos teriorf. Esta unidad lleva a cabo una resta, aunque también puede llevar cabo una multiplicación por cierto factor de escala, y/o una compresió o cuantifieación de las

20 métricas. En la figura, los bases que entregan P métricas LL por cielo se identifican con la letra P<

Nótese que a partir de la arquitectura representada en la Fig. 7 se puede obtener fácilmente ia de un turbo deeodíficador en serie no paralelo: En tul caso (deeodif cador e serie no paralelo) P sería igual a L y por tanto el elementó 704 contendría tan sólo un

2S decodifieador SOVA twíbw 703; además ios elementos 701 y 5 iendrían que entregar mfermación relativa a un solo oque, en lugar d entregar inrbm aeión simultánea de vario sub-hloquesj es decir, lo bases- que aparecen en la figura conectando a ios elementos 7(11 y 705 con 7(14 solo entregarían una métrica por bus (P~l ); por último _» , como en la decodiílcación no paralela se tiene un bloque a deeodificar cuyos estados de

^■ 50 Inicio y -fia son conocidos, no hay que aplicar ningún tipo de -solape lo cual simplifica el comportamiento de lo elementos 701 y 70S _*

Cada «no de los decodiicadores par-alelo SOVA í bw 703 tiene la estructura que se muestra en la Fig. 8. La Unidad Recnisiv ftv w801 lleva a cabo las siguientes ranclones: (i) calcular la métrica d camino o PM para cada uno de los N estados; (a) seleccionar el camino superviviente y (iíí) obtener el peso de esta decisión corno diferencia <ie las FMs ente los caminos s¾peni ientes. La decisión relativa a los caminos supervivientes los pesos correspondientes para cada estado se usa par construir los vectores Y y W, de longitud N, corno se muestra en la Fig, 8. Esta unidad se encarga de realizar las funciones mencionadas anteríon«entt% tanto en la dirección hacia delante como .ca la dirección hacia atrás.

L Unidad d Control 80 implemenía una máquina de estados finitos que activa las señales de control apropiadas para el resto de unidades presentadas en la Fig. 7, pemiiíiendo a dichas unidade el realizar su función en la dirección hacia delante o hacia atrás, dependiendo dé la iíénteión en la que se eiieucntjre. Las decisiones se entregan a la Unidad de Memoria de Supervivientes fw/bw 8( . Est unidad yealfza el recorrido hacia atrás o TB para encontrar el camino ML. Como esta unidad debe llevar a cabo el cálculo del recorrido haci atrás, la lógica combínaeional que calcula e! estado previo para un estado determinado debe ser diferente dependiendo de la dirección. Una considera la máquina de estados haci adelante y la otra la máquina de estados haci atrás. Los estados de este camin se Introduce a. la Unida de Proceso d Actualización fw bw Como el eleirsenío $83 requiere cierto numero de cíelos de reloj para obtener los estados de dicho camino, el elemento retardado* 802 aplica a los pesos W (diferencias entre la FMs) el mismo retardo m cíelos de reloj. Dicha unidad se encarga de la actualización d los pesos calculados por la Unidad eéursíva fw/bw $01. Para llevar a cabo este proceso de actualiaación, hay que realizar un doble recorrido hacia atrás o IB: im TB obtiene el camino ML, mientras que el otro obtiene el caori.no c m etidor. En cada etapa e la que el bit decidido para ambos caminos difiere, se lleva a cabo una ac unlización. Dicha acinalí¾ición consiste en la selección del peso mteno entre el camino competidor y lo caminos ML. Esta unidad también debe trabajar tanto en la dirección hacia delante corno hacia atrás al llevar cabo el TB. finalmente, tras el proceso de actualización, se obtienen las métricas LLR a-posteriori en las direcciones hacia delante o hacía atrás dependiendo de la iteració actual,.

En la Fig. 9 se ii t la estructur de la Unidad Recia'slva f bw SOI. Esta unidad se compone de N Elementos dé ecuóión 902,· que calculan la P y llevan a cabo las tareas (i)-(iií} para cad estado. Para ello, cad Eieinenío de Reearsióri 9§2 necesita conocer las medidas Ls, L y La. En el caso de un iteración completa, Lp es Lpl - En el caso de una es Lp2 y Ls ha sido entrelazado por el Banco de Memoria de Entrada 701, Por otro fado. La es la informaclórí a príorí, o de manera eqrñvaiente las métricas extrínsecas de la semí-iteración previa,

Para calcular jas PMs para cada estado Si en ta etapa k, se neces tan las PM de los caminos que confluyen en Sí m !s. etapa pre ia fc-1. Uno de dichos caminos, el asociado con i¾~ 1 , se identifica como PMj(Si), Mientras que el oto,, asociado cor. ¾==·0>, se identifica como PM ₉ (Si) Corno ios caminos que confluyen en cada estado seo diferentes en las direcciones hacía delante y hacía a rás, se requiere una red de interconexién. Est tarea es realizada por la Unidad de Conexión fw/bw 901. Dicha anidad entrega el PM adecuado de la etapa previa cada Elemento de eeursión 902, dependien o de l dirección (hacia delante o hacia atrás). Una posible manera de inipl.ementar este elemento es medíaríte iva banco de mnltipíexores y registros para almacenar la PM previa. ISOVApara la turbo deeodifkacián concurrent paralela

La Eig. 1.0 muestra un diagram de tiempos del método ÁLSOV'Á propuesto, para ¿«codificación concurrente paralela, mientras que la Fíg, 11 muestra una posible impiemeníacióii de la misma. En esta implementación, el Banco de Memoria de Entrad 110! debe alimentar simultáneamente dos Bancos de deeodíñeadóres S0VA rw/hvv. De esta form s éste debe proporcionar t métrica Ls tanto de forma entrelazada como no entrelazada. Existen dos bancos de información extrínseca, Por mi lado, el Banco de ínfofjnación Extrínseca 1 1103 siempre dese»trela¾a las medidas extrínsecas. Si enfoargo, en las iteraciones impares se lee y escribe hacia adelante mientras que en las iteraciones pares se lee y escribe bacía atrás, Por otro lado, el Banco de información Extrínseca 2 1104 siempre entrelaz las medidas extrínsecas.; Este banco trabaja hacia adelante en iteraciones impares hacia atrás en las pares. Las Unidades de Calculo Bxtrinseeo 706 y el. Banc de deeodíficadores SOYA ñv/bw 704 son equivalentes ai caso mostrado en la sección anterior, Por último, la Unidad de Control 1102 se encarga de asegura que la lectura y escritura en las unidades 1101, 1103 y 1104 se realice de forma, correcta.

PM Bx El segando aspecto de k presente invención, arquitectura propuesta para deeodiíieación paralela denominada PMSBx, puede ser usado con los algoritmos SOYA, ALSOVA y B1S0YA. L½ el caso de BlSOVA-FMSíix y ALSOVA-P SB existen dos tipos distintos de métricas de camino y de recorridos hacia atrás; unos para la decodifíeación hacia delante y oíros hacia detrás _* Para el caso de BíSÜVA este hecho no da lugar a ninguna modificación con respecto SOVA-PMSBx y que la iryeializaeión se lleva a cabo en dos bancos independietííés de decodiíkadores SOYA. Sin embargo, para ALSOVA-PMSBx no es posible Intercambiar las PMs entre dos iteraciones consecutivas ya que éstas se han calculado en direceiones opuestas. Por tanto, en e! caso de ALSOVA, e! iniercamhlo de PMs se realiza catre dos iteraciones en lugar de una com ocurre con SOYA y B1SOVA, De manera más formal la inki lización de PMs se puede describir con l siguiente ecuación

donde el símbolo D representa el retardo en Iteraciones que se aplic a las PMs que se iníeream an entre decodificadores paralelos. Para el caso de SOYA y B1SOVÁ ! ^: 1 rnieníras que para ALSOVA i ^:: 2, L etapa en l que se realka la iniciali aeión para el s«h~bloque n es kjj-O paran-i y ¾ _?Β ^: =( ^Ώ ~0^ para n>L

La ffiicialkaeión de estados de caía a hacer los TBs es l que sigue

donde el estado desde el que se realiza el último TB es ¾, tl para n~P y k^fiM para n< La ecuación anterior es válida para SOYA-PMSBx, BISOVA-PMSBx, y ALSOVA-PMSBx ya que los estados se -intercambian en la misma iteración.

ÁLSOVÁ-PMSBx para turbo éeco ificackm en serie paralela La arquitectura propuesta para un turbo decodlfícador serie r lelo usando ALSOVA- PMSBx se muestra en l Fig, 7, La dirección de decodifíeación se cambia a lo largo de las iteraciones (como se describió anteriormente) con objeío de mejorar la capacidad correctora sin aumentar significativamente Ja latericia o el consumo de área. El Banco de Memoria a la Entrada 701 y el Banco de Memoria Extrínseco 705 sos capaces de alimentar el Banco de decodífteadores SISO 7(14 en la direcciones hacia adelante y hacia atrás. .La Unidad, de Control 7( 2 determina el comportamiento de la diferentes ^' unidades dependiendo de la iteración (o media Iteración) a realizar en cada momento. No obstante, el caso del Basco de deeodifieadotes SISO paralelo H tiene otra arquitectura que se muest a e la Fig, 1.2, conforme a la cuál dicho Banco de decodiñeadores SISO paralelo 704 c mprendes entre otros, una Unidad de Control I3 , Como se puede .observar, las conexiones entre los decddi ^' fíeadores SOVA í bw 703 permiten el intercambio de iníomiación para paliar la incertidurnbre en el borde de los sub- oques. El intercambio de ΨΜ se realiza gracias a la unidad .1.303, la cual aplica un retardo a las PMs de dos iteraciones completas (D~2), o lo que es lo mismo, a cuatro medias iteraciones. El intercambio de estados se realiza gracias a registros de memoria 130 que almacenan dicha Información durante l iteració en la que es requerida. Además, ios decodifieadore 703 son decoditlcadores íw bw con una arqtóectnra como la mostrada en la Ftg, Estos decodífteadores son capaces de realizar la decodixleaeióu SOVA tanto bacía adelante como ^' hacia atrás, dependiendo de l iteración en cuestión.. SO Vá~PMSBx para turbo ee&éificúcién en serie paralela

La Fig. 14 ilustra l estructur de la turbo dccoáífícación en. serle paralela, la cual se puede aplicar al caso de SOVA-PMSBx. La arquitectura es l de un turbo decodi lcador serié pa ^r alelo. Este caso incluye a su vez el caso de un turbo decodiñea or en serie no- paralelo. El diagrama de bloques muestra las medidas LLR del canal asociadas con un. turbo código de tasa 1/3 con un bit sistemático y dos bits de paridad como es el caso del empleado en la tecnología LTE. Estas métricas LLR se p esenta» en l figura como Ls, Lpl y Lp2 respectivamente, Las métricas Ls y Lpl están relacionadas con el mensaje, mientras que la métrica Ls2 está relacionad con el mensaje entrelazado. Estas méír lea se almacenan en el Banco de Memoria dé Entrada í 4 1. Dicha unidad e capaz de entregar a cad decodirleador paralelo dentro del banco de deeodificá^óres paralelos el sub-bloque correspondiente. Además, el Banco de Memoria de Entrada .140.1 entrelaza las métricas Ls cuando lleva a cabo una seml-iteración, pudiendo así entregar diebas métricas al Banco de Decoditlcadores SOVA 1404, El Banco de Deeodillcadores SOYA 1404 calcula métricas a-posteriori (sólo hacia delante). La llnidad de Control 1402 determina el comportamiento de las diferentes unidades dependiendo de Ja iteración o semi-iteradó que se lleve a cabo e cada momento. La U nidad de Cálculo Extrínseca 14(6 calcula la información extrínseca utilizando las métricas LLR y las métricas a-posteriori Esta anidad lleva a cabo una resta, aunque íamhié® puede llevar a cabo una /multiplicación por cierto faetor de escala, y/o una compresión o etmntiñeación de las métricas. La infamación extrínseca generada por el elemento Í4 se almacena en el elemento 1405. Este último elemento se encarga de entregar l inibrmaeión extrínsec que se calculé e» la semi-iteración anterior y de entrelazarla o desentrelazarla según se trate de una seini-íf eraeíón o de una Iteración completa. En la figura _d los bases qne entregan P métricas LLR por ciclo se identifican con l letra P. La estructura del Banco .Paralela- de Decodifie adores SQVA 1404 se presenta en la Fíg> 13. En este caso se usa el parámetro 1 . Esto implica que las PMs son retrasadas por las unidades 1003 una iteración completa, es decir dos serráiteraciones. Bn este caso cada elemento WM es un deeodiíleador SOVA convencional que se ejecut sólo en la dirección hacia delante. El element .1082. es im registro que almacena el estado desde el que se arranca el último TB en la iteración actual. La tJnidad de Control .1084 garantiza que el intercambio de estados y PMs se realice acorde con el método SOVA-F SBx,

BISQFA-PMSBx para turbo éecedificüciénm serie paralela

La arquitectura de un turbo decodifícador en serie paralelo usando el algoritmo BíSOVA P S ^' Bx- se ilustra en la P%. 15. Esta arquitectura sigue la Irnplementación directa del algoritmo BÍSO A presentada po Chen en el año 2000. En el algoritmo BISO Y A en la iteración i, un banco de deeodifieadorss SO VA calcula las medidas a~ posteriori hacia delante, identificadas por el símbolo L ^! ¾%} -mientras que el otro calcula las medidas a-posteriori bacía atrás. Identificadas como

Este método mejora gniieativarnente la capacidad correctiva pero dobla el área ocupada por los bancos de decodificadores. El Banco de Memoria de Entrada 1201 de e proporcionar las medidas Ls y L en la dirección hacia delante y hacia atrás simultáneamente. Por este moti vo hay cuatro buses a la salida d esta unidad. La unidad Í2 está formada por dos bancos paralelos de deeodiíleadores SISO, que aparecen en la figirra como elementos 1283 y 1204, La unidad 1203 se corresponde con un banco de deeodiíleadores que -trabaja en la dirección bacía delante. Esta unidad tiene la estructura que aparece eft la Fig. 13 donde el retardo aplicado a ks.PMs es de una i eraciÓB completa (D™1 }, Por otro lado la unidad 1204 es ¾» ^■ banco de decodíñeadore SOVA paralelos que trabaja e ia dirección hacia atrás. Esta unidad tambi n tiene la estructur que se presenta en k Fí.g. 13 donde el retardo aplicado las PMs es de una iteración (D ^~ l }. Las medidas LL a-posíeríorí calculadas en las direcciones bacía delante y hacia atrás se almacena en ia unidad 1206, Esta unidad tiene dos bloques de memoria con dos puertos. Para alimentar cada banco de deeodiíleadores al mismo tiempo, la unidad í2Mi lee las correspondientes medidas LLft á-pósté ort hacia delante y hacía atrás y calcula las medidas LLR a-posterion ímales siguiendo la ecuación (5). Posteriormente calcula la íní½nraeíón extrínseca que será usada como información a-priori por ambos bancos de deeodificadores en la siguiente semí-iteracíóü. La unidad d control 1202 asegura que el f ckmámie o del resto de unidades sea el correcto.