PT1550219E

PT1550219E - Procedimento e disposição para a codificação e descodificação aritmética de estados binários e suporte de memória de leitura informática

Info

Publication number: PT1550219E
Application number: PT03725141T
Authority: PT
Inventors: Detlef Marpe; Thomas Wiegand
Original assignee: Fraunhofer Ges Forschung
Priority date: 2002-05-02
Filing date: 2003-05-02
Publication date: 2009-03-05
Also published as: ES2439996T3; JP2006050605A; SI1550219T1; ES2442174T3; EP1571755A2; HK1130372A1; ATE421802T1; HK1157948A1; EP2326013A2; EP2068448A2; JP4054345B2; PT2326013E; EP2290612B1; ES2442190T3; DK2296282T3; JP3989485B2; EP1571755A3; EP2326013B1; EP2068448B1; EP2037412A2

Description

DESCRIÇÃO

PROCEDIMENTO E DISPOSIÇÃO PARA A CODIFICAÇÃO E DESCODIFICAÇÃO ARITMÉTICA DE ESTADOS BINÁRIOS E SUPORTE DE MEMÓRIA DE LEITURA INFORMÁTICA 0 invento refere-se a um procedimento e a uma disposição para a codificação e descodificação aritmética de estados binários, bem como um programa informático correspondente e um suporte de memória de leitura informática que pode ser utilizado, em especial, na compressão de dados digitais. 0 presente invento descreve um novo procedimento eficaz para a codificação aritmética binária. A necessidade de existir uma codificação aritmética binária surge nas mais variadas áreas de aplicação da compressão de dados digital. A este nível destacam-se, como apresentando um interesse, a título de exemplo, as aplicações nas áreas da codificação digital de imagens. Em inúmeros standards para a codificação de imagens, como por exemplo, JPEG, JPEG-2000, JPEG-LS e JBIG, foram definidos procedimentos para a codificação aritmética binária. As actividades de estandardização mais recentes apresentam também a utilização futura de técnicas de codificação do mesmo tipo na área da codificação de vídeo (CABAC em H. 264/AVC) [1].

As vantagens da codificação aritmética (CA) relativamente à codificação de Huffman [2] que, na prática, é utilizada com frequência até aos dias de hoje, podem ser caracterizadas essencialmente por três características: 1. Com a utilização da codificação aritmética é possível obter, por meio de mecanismos de adaptação simples, uma adaptação dinâmica à estatística de origem existente (adaptabilidade). 1 2. A codificação aritmética permite a atribuição de uma quantidade de números não inteiros de bits por símbolo a ser codificado e é, assim, adequada para obter resultados de codificação que representam uma aproximação da entropia como sendo o limite inferior teoricamente existente (aproximação de entropia) [3]. 3. Mediante a utilização de modelos de contexto adequados, com a codificação aritmética torna-se possível beneficiar das ligações estatísticas entre símbolos visando posteriores reduções de dados (redundância inter-símbolo) [4].

Como desvantagem de uma aplicação da codificação aritmética, poderá considerar-se, quando em comparação com a codificação de Huffman, o esforço de cálculo geralmente mais elevado. 0 conceito de codificação aritmética remonta aos trabalhos basilares da teoria de informação de Shannon [5]. Os primeiros métodos de construção concepcionais foram publicados em [6], pela primeira vez, por Elias. Uma primeira variante de LIFO (last in, first out) da codificação aritmética foi concebida por Rissanen [7] e foi posteriormente modificada, por diferentes autores, relativamente a concepções de FIFO (first in, first out) [8] [9] [10].

Em comum a todos estes trabalhos está o princípio básico da decomposição do intervalo parcial recorrente. De acordo com as probabilidades indicadas P ("0") e P ("1"), de dois eventos {"0", "1"} de um alfabeto binário, um intervalo inicialmente existente, por exemplo, o intervalo [0, 1], é decomposto, de forma recorrente, em intervalos parciais, de acordo com a ocorrência de eventos. Assim sendo, o tamanho do intervalo parcial resultante como produto das probabilidades individuais dos eventos ocorridos é proporcional à probabilidade da sequência dos eventos individuais. Dado que cada evento S± com a probabilidade P (S±) contribui com H (Si) = - log (P (S±)) do 2 conteúdo de informações teórico H (S±) de S± para a taxa global, surge uma relação entre o número NBit dos bits para representação do intervalo parcial e a entropia da sequência de eventos individuais, que é indicada pelo lado direito da equação que se segue NBit = - log ΓΊ1 P (Si) = - Σί log P (Si)

Contudo, o principio básico requer, em primeiro lugar, uma precisão (teoricamente) ilimitada na representação do intervalo parcial resultante e tem, além disso, a desvantagem de só após a codificação do último evento se poderem emitir os bits para representação do intervalo parcial resultante. Para fins de aplicação prática foi, então, decisivo o desenvolvimento de mecanismos para a emissão incremental de bits, perante uma representação simultânea com números de exactidão fixa predefinida. Tal foi proposto pela primeira vez nos trabalhos [3] [7] [11].

Na figura 1 estão esquematizadas as operações principais para a codificação aritmética binária. Na implementação representada o intervalo parcial actual está representado pelos dois valores L e R, sendo que L designa o ponto inicial e R designa a abrangência (amplitude) do intervalo parcial, e que ambos os valores são representados com, respectivamente, números inteiros b-bit. Por conseguinte, a codificação de um bit e {0, 1} ocorre, essencialmente, em cinco etapas parciais: na primeira etapa, com base na estimativa de probabilidades, determina-se o valor do símbolo menos provável. Para este símbolo, também conhecido como LPS (least probable symbol), em contraposição ao MPS (most probable Symbol), a estimativa de probabilidades PLPS é utilizada na segunda etapa para o cálculo da amplitude RLPS do intervalo parcial correspondente. De acordo com o valor do bit (bit) a ser codificado, os valores L e R são actualizados na terceira etapa. Na quarta etapa, a estimativa de probabilidades é actualizada de acordo com o valor do bit que acabou de ser 3 codificado e, por fim, o intervalo de codificação R é submetido a uma denominada renormalização, isto é, o valor R será, por exemplo, reescalado de forma a que a condição Re (2 b“2, 2 b_1) seja preenchida. Para tal, em cada operação de escalamento será emitido um bit. Para obter mais detalhes consultar [10]. A desvantagem essencial de uma implementação como a citada acima consiste em que o cálculo da amplitude do intervalo RLPS requer uma multiplicação por cada símbolo a ser codificado.

Normalmente, as operações de multiplicação, em particular se forem realizadas em hardware, são onerosas e dispendiosas. Em vários trabalhos de pesquisa foram, assim, analisados procedimentos para substituir esta operação de multiplicação por uma aproximação adequada [11] [12] [13] [14]. Os processos publicados sobre este tema podem ser divididos, por alto, em três categorias. 0 primeiro grupo de propostas para uma codificação aritmética, binária e isenta de multiplicações, baseia-se no princípio de aproximar as probabilidades estimadas PLPS de forma a que a multiplicação, na segunda etapa da figura 1, possa ser substituída por uma operação (ou mais) de adição e de deslocamento [11] [14] . Neste sentido, e no mais simples dos casos, as probabilidades PLPS são aproximadas por valores no formato 2-q com q > 0 número inteiro. e proposto de valores | k > 0, k

Na segunda categoria de procedimentos aproximativos que se aproxime a área de valores de R por meio discretos no formato (½ - r), em que r e {0} u (2 ~k número inteiro] [15] [16]. A terceira categoria de procedimentos caracteriza-se pelo facto de, nela, se substituírem as mesmas operações aritméticas por utilizações de tabelas. A este grupo de procedimentos pertencem, por um lado, o codificador Q (Q-Coder) utilizado na norma JPEG e 4 os procedimentos ligados, tais como o codificador QM e MQ (QM-Coder e MQ-Coder) [12], e, por outro lado, o codificador quase-aritmético [13]. Enquanto o último procedimento mencionado efectua uma restrição drástica do número b de bits utilizado para a representação de R, para obter tabelas de dimensões aceitáveis, no codificador Q a renormalização de R é efectuada de forma a que o valor R possa ser aproximado por 1, mesmo que seja, de facto, apenas por aproximação.

Desta forma, a multiplicação para a determinação de RLPS é evitada. Adicionalmente, a estimativa de probabilidades é efectuada por meio de uma tabela no formato de uma máquina de estados finitos (Finite State Machine). Para obter mais detalhes sobre este tema, consultar [12]. A US5592162 descreve um processo para a execução de uma codificação aritmética, em que o número de amplitudes do intervalo possíveis é delimitado.

Mediante a utilização de um índice que se refere a estas amplitudes do intervalo, é possível obter-se uma codificação aritmética isenta de multiplicações, com um consumo de memória reduzido.

Um processo para a codificação e descodificação aritmética de estados binários é vantajosamente executado de forma a que, em uma primeira etapa, uma área de valores a ser indicada seja dividida, para a especificação da amplitude do intervalo R, em K amplitudes do intervalo representativas [Ql, ..., QK}, que uma área de valores a ser indicada para a especificação das probabilidades seja dividida em N estados de probabilidade representativos [PI, ..., PN], e que sejam indicadas as regras de atribuição que atribuem a cada amplitude do intervalo R um Qk (1 < k ^ K) e a cada probabilidade um Pn (1 < η ^ N) . Em uma segunda etapa ocorre a codificação ou a descodificação dos estados binários, sendo que o cálculo da nova amplitude de 5 intervalo a ser derivada no processo de codificação ou de descodificação, é executado por meio da utilização de uma amplitude do intervalo representativa Qk (1 < k ^ K) , e um estado da probabilidade representativo Pn (1 ^ n á N) e por meio de operações aritméticas diferentes de multiplicação e divisão, sendo que a amplitude do intervalo representativa Qk é determinada por meio do intervalo base de referência da amplitude R, e sendo que o estado da probabilidade representativo Pn é determinado por meio da estimativa de probabilidade que está na base do símbolo a ser codificado ou do símbolo a ser descodificado, de acordo com as regras de atribuição indicadas.

Uma outra forma de execução preferencial do processo é caracterizada pelo facto de, a partir do intervalo que está presentemente a ser analisado com a amplitude R, para a determinação da amplitude do intervalo atribuída Qk, se determinar um índice q_index por meio de uma operação de mascaramento de bits e de deslocamento aplicada na representação interna/binária de R.

Como vantagem salienta-se também o facto de, a partir do intervalo que está presentemente a ser analisado com a amplitude R, para a determinação da amplitude do intervalo atribuída Qk, se determinar um índice q_index por meio de uma operação de mascaramento de bits e de deslocamento aplicada na representação interna/binária de R com utilização subsequente de uma tabela Qtab, sendo que a tabela Qtab contém os índices de amplitudes do intervalo, índices esses que correspondem aos valores de R que foram pré-quantifiçados por meio da operação de deslocamento.

Revela-se como sendo especialmente vantajoso, quando a estimativa de probabilidade que está na base do símbolo a ser codificado ou descodificado é atribuída, com a ajuda de um índice p_state, a um estado da probabilidade Pn. 6 É igualmente uma vantagem se a determinação da amplitude do intervalo RLPS correspondente ao LPS for efectuada por meio de uma utilização da tabela Rtab, sendo que a tabela Rtab contém os valores da amplitude do intervalo RLPS como valores de produto (Qk * Pn) que correspondem a todos os K valores quantificados de R e aos N estados de probabilidades diferentes. 0 esforço de cálculo fica particularmente reduzido quando a determinação da amplitude do intervalo RLPS correspondente ao LPS ocorre por meio de uma utilização da tabela Rtab, sendo que, para a análise da tabela, é utilizado o índice de quantificação q_index e o índice do estado da probabilidade p_state.

Está ainda previsto que para os N diferentes estados de probabilidade representativos sejam predefinidas regras de transição, sendo que essas regras de transição indicam o novo estado, tendo em conta o actual símbolo codificado ou descodificado, a ser utilizado para o próximo símbolo a ser codificado ou descodificado. Neste sentido, revela ser uma vantagem se for criada uma tabela Next_State_LPS que contenha, para além do índice n do estado da probabilidade actualmente existente Pn, o índice m do novo estado da probabilidade Pm, na ocorrência de um símbolo menos provável (LPS), e/ou se for criada uma tabela Next_State_MPS que contenha, para além do índice n do estado da probabilidade actualmente existente Pn, o índice m do novo estado da probabilidade Pm, na ocorrência de um símbolo mais provável (MPS).

Uma optimização do processo para a codificação e descodificação aritmética binária sustentada por tabela é obtida, em especial, porque os valores da amplitude do intervalo RLPS que correspondem a todas as K amplitudes do intervalo e a todos os N estados de probabilidade são gravados em uma tabela Rtab como valores de produto (Qk * Pn). 7

Uma outra optimização obtém-se quando o número K de valores de quantificação e/ou o número N dos estados representativos é seleccionado em função da exactidão da codificação predefinida e/ou em função do espaço de memória disponível.

Uma forma de execução especial da codificação abrange as seguintes etapas:

1. Determinação do LPS 2. Quantificação de R: q_index = Qtab [R»q] 3. Determinação de RLPS e R: RLPS = Rtab [q_index, p_state]

R = R - RLPS 4. Cálculo do novo intervalo parcial:

if (bit = LPS) then L 4- L + R R 4- RLPS p_state - Next_State_LPS [p_state]

if (p_state = 0) then valMPS <- 1 - valMPS else p_state <- Next_State_MPS [p_state], 5. Renormalização de L e de R, gravação de bits, sendo que q index descreve o índice de um valor de quantificação lido de Qtab, p_state descreve o estado actual,

Rlps descreve a amplitude do intervalo correspondente

ao LPS

valMPS descreve o bit correspondente para o MPS.

A descodificação numa forma de execução especial abrange as seguintes etapas: 1. Determinação do LPS 8 2. Quantificação de R: q_index = Qtab [R»q] 3. Determinação de RLPS e R:

Rlps = Rtab [q_index, p_state] R = R ~ Rlps 4. Determinação de bit, de acordo com o posicionamento do intervalo parcial: if (V > R) then bit «- LPS V - V - R R <- Rlps

if (p_state = 0) valMPS ^ 1 - valMPS p_state — Next_State_LPS [p_state] else

bit «- MPS p_state - Next_State_MPS [p_state], 5. Renormalização de R, leitura de um bit e actualização de V, sendo que q_index p_state Rlps descreve o índice de um valor de quantificação lido de Qtab, descreve o estado actual,

descreve a amplitude do intervalo correspondente ao LPS valMPS descreve o bit correspondente para o MPS e V descreve um valor abrangido pelo intervalo parcial actual.

Em uma forma de execução do processo de acordo com o invento está previsto que, durante a codificação e/ou a descodificação, o cálculo do índice de quantificação q_index ocorra na segunda etapa de acordo com as regras de cálculo: q_index = (R >> q) & Qmask em que Qmask representa uma máscara de bit seleccionada de forma adequada em função de K. 9

Apresenta-se ainda como uma vantagem se a inicialização do modelo de probabilidade ocorrer em dependência de um parâmetro de quantificação SliceQP e dos parâmetros modelo predefinidos m e n, em que SliceQP descreve os parâmetros de quantificação predefinidos no início de um segmento (slice), e m e n descrevem os parâmetros modelo. É igualmente uma vantagem se a inicialização dos modelos de probabilidades abranger as seguintes etapas: 1. preState = min (Max(l, ((m * SliceQP)>>4)+n), 2*N) 2. if (preState <= N) then p_state = N + 1 - preState valMPS = 0 else

p_state = preState - N valMPS = 1, em que valMPS descreve o bit correspondente ao MPS, SliceQP descreve os parâmetros de quantificação predefinidos no início de um segmento, e m e n descrevem os parâmetros modelo.

Uma disposição para a codificação e descodificação aritmética de estados binários engloba no minimo um processador que está (estão) preparado (preparados) para que seja possível executar um processo para a codificação e descodificação aritmética, sendo que em uma primeira etapa, uma área de valores a serem indicados para a especificação da amplitude do intervalo R seja dividida em K amplitudes do intervalo representativas {Q1, ..., QK} e uma área de valores a serem indicados para a especificação das probabilidades seja dividida em N estados de probabilidade representativos {Plr ..., PN}, e que sejam indicadas as regras de atribuição que atribuem a cada amplitude do intervalo R um Qk (1 < k > K) e a cada probabilidade um Pn (1 d η > N) . Em uma segunda etapa ocorre a codificação ou a descodificação dos estados binários, sendo que o cálculo da nova amplitude de 10 intervalo a ser derivada no processo de codificação ou de descodificação, é executado por meio da utilização de uma amplitude do intervalo representativa Qk (1 < k > K) , e um estado da probabilidade representativo Pn (1 < η > N) e por meio de operações aritméticas diferentes de multiplicação e divisão, sendo que a amplitude do intervalo representativa Qk é determinada por meio do intervalo base de referência da amplitude R, e sendo que o estado da probabilidade representativo Pn é determinado por meio da estimativa de probabilidade que está na base do símbolo a ser codificado ou do símbolo a ser descodificado, de acordo com as regras de atribuição indicadas.

Um programa informático para a codificação e descodificação aritmética de estados binários permite a um computador, depois de ter sido transferido para a memória do computador, executar um processo para a codificação e descodificação aritmética, sendo que, em uma primeira etapa, uma área de valores a serem indicados para a especificação da amplitude do intervalo R seja dividida em K amplitudes do intervalo representativas {Ql, ..., QK} e uma área de valores a serem indicados para a especificação das probabilidades seja dividida em N estados de probabilidade representativos {Pi, ..., PN}, e que sejam indicadas as regras de atribuição que atribuem a cada amplitude do intervalo R um Qk (1 < k > K) e a cada probabilidade um Pn (1 d η ^ N) . Em uma segunda etapa ocorre a codificação ou a descodificação dos estados binários, sendo que o cálculo da nova amplitude de intervalo a ser derivada no processo de codificação ou de descodificação, é executado por meio da utilização de uma amplitude do intervalo representativa Qk (1 < k > K) , e um estado da probabilidade representativo Pn (1 < η > N) e por meio de operações aritméticas diferentes de multiplicação e divisão, sendo que a amplitude do intervalo representativa Qk é determinada por meio do intervalo base de referência da amplitude P, e sendo que o estado da probabilidade representativo Pn é determinado por meio da estimativa de 11 probabilidade que está na base do simbolo a ser codificado ou do símbolo a ser descodificado, de acordo com as regras de atribuição indicadas. A título de exemplo, este tipo de programa informático pode ser disponibilizado (seja mediante uma taxa/pagamento ou gratuitamente, seja de acesso livre ou protegido por uma palavra-passe) para ser transferido para uma rede de dados ou de comunicações. Os programas informáticos assim disponibilizados podem, então, ser utilizados por meio de um processo pelo qual um programa informático é transferido de uma rede para transferência de dados, como, por exemplo, da Internet, para um dos dispositivos de processamento de dados ligados à rede.

Para a execução de um processo para a codificação e descodificação aritmética de estados binários, é utilizado vantajosamente um suporte de memória de leitura informática, no qual se encontra gravado um programa que permite a um computador, depois de ter sido transferido para a memória do computador, executar um processo para a codificação e descodificação aritmética, sendo que, em uma primeira etapa, uma área de valores a serem indicados para a especificação da amplitude do intervalo R seja dividida em K amplitudes do intervalo representativas {Ql, ..., QK} e uma área de valores a serem indicados para a especificação das probabilidades seja dividida em N estados de probabilidade representativos {Pl, ..., PN}, e que sejam indicadas as regras de atribuição que atribuem a cada amplitude do intervalo R um Qk (1 ^ k b K) e a cada probabilidade um Pn (1 < η > N) . Numa segunda etapa ocorre a codificação ou a descodificação dos estados binários, sendo que o cálculo da nova amplitude de intervalo a ser derivada no processo de codificação ou de descodificação, é executado por meio da utilização de uma amplitude do intervalo representativa Qk (1 < k > K) , e um estado da probabilidade representativo Pn (1 < η > N) e por meio de operações aritméticas diferentes de multiplicação e divisão, sendo que a amplitude do intervalo 12 representativa Qk é determinada por meio do intervalo base de referência da amplitude R, e sendo que o estado da probabilidade representativo Pn é determinado por meio da estimativa de probabilidade que está na base do simbolo a ser codificado ou do símbolo a ser descodificado, de acordo com as regras de atribuição indicadas. 0 novo processo caracteriza-se pela combinação de três características. Em seguida é efectuada, à semelhança do que acontece no Q-Coder, a estimativa de probabilidades por meio de uma máquina de estados finitos (FSM: Finite State Machine) , sendo que a geração dos N estados representativos da FSM ocorre offline. As regras de transferência correspondentes são, por conseguinte, arquivadas com o formato de tabelas. A segunda característica do invento é uma pré-quantificação da amplitude do intervalo R em um número de K valores de quantificação previamente definidos. Isto permite, com um dimensionamento adequado de K e N, a criação de uma tabela que contenha todas as combinações de K x N dos valores de produto R x Plps previamente calculados para uma determinação isenta de multiplicações de Rlps-

Para a utilização do invento exposto em um ambiente no qual são utilizados diferentes modelos de contexto, incluindo também aqueles de divisão de probabilidade (quase) uniformes, está previsto um elemento adicional (opcional) de um ramo separado na máquina de codificação, reduzindo-se claramente, partindo de uma repartição uniforme, a determinação dos valores L e R, bem como a renormalização do esforço de cálculo.

As figuras mostram:

Figura 1 Representação das operações essenciais para a codificação aritmética binária; 13

Figura 2

Figura 3

Figura 4

Figura 5

Figura 6

Esquema modificado para codificação aritmética sustentada por tabela; Princípio de descodificação aritmética sustentada por tabela; Princípio de codificação e de descodificação para dados binários com repartição uniforme; Realização alternativa de codificação e de descodificação para dados binários com repartição uniforme. Inicialização dos modelos de probabilidade em função de um parâmetro de quantificação SliceQP e de parâmetros modelo m e n predefinidos.

Em seguida, passa-se a esclarecer, mais em pormenor, as bases teóricas:

Estimativa de probabilidade sustentada por tabelas

Tal como já foi descrito pormenorizadamente mais acima, a eficácia da codificação aritmética tem como fundamento a estimativa, o mais correcta possível, da probabilidade de ocorrência dos símbolos a serem codificados. Para permitir uma adaptação a estatísticas de origem variáveis, esta estimativa tem de ser actualizada no decorrer do processo de codificação. Em regra, são utilizados aqui os processos habituais que funcionam com a ajuda de contadores de ocorrência, escalonados, dos eventos codificados [17]. Sendo designados os contadores CLPS e CMps para a frequência da ocorrência de LPS e de MPS, é possível efectuar, por meio deste contador, a estimativa P lps = _Clps_

Clps + Cmps (1) e, dessa forma, executar a operação de subdivisão cujo esboço consta da Figura 1. Do ponto de vista prático, considera-se desvantajosa a divisão requerida na equaçao (1). Contudo, com 14 bastante frequência se revela adequado e necessário efectuar, no caso de se ultrapassar um valor limiar Cmax predefinido do contador total CTotai = CMps + CLPS, um reescalonamento dos estados do contador. (Deve ser considerado, neste contexto, que em uma representação b-bit de L e R, a probabilidade mais reduzida que ainda pode ser representada de forma correcta, é de 2 ~b+2, sendo que, para evitar que estes limites mais baixos sejam excedidos, se torna necessário, eventualmente, o reescalonamento dos estados do contador.) Em uma selecção adequada de Cmax, é possível tabelar os valores recíprocos de CTotai, de forma a que a divisão requerida na equação (1) possa ser substituída por uma utilização de tabela ou por uma operação de multiplicação ou de deslocamento. Contudo, para evitar também essas operações aritméticas, no presente invento é utilizado um processo completamente sustentado por tabela para a estimativa de probabilidade.

Com este intuito, são previamente seleccionados, Numa fase de treino, estados de probabilidade representativos {Pk | 0 < k <

Nmax}, em que a selecção dos estados depende, por um lado, da estatística dos dados a serem codificados e, por outro lado, da sub condição do número máximo predefinido de estados.

Adicionalmente são definidas regras de transição que indicam qual o novo estado, partindo do actual símbolo codificado, que deve ser utilizado para o próximo símbolo a ser codificado. Estas regras de transição estão disponibilizadas na forma de duas tabelas: {Next_State_LPSk | 0 < k < Nmax}, e {Next_State_MPSk I 0 < k < Nmax}, sendo que as tabelas para o índice n do estado de probabilidade actualmente existente Pn fornece o índice m do novo estado de probabilidades Pm, quando ocorre um LPS ou um MPS. A ser destacado, está o facto de, para a estimativa de probabilidades no codificador ou descodificador aritmético, tal como aqui foi proposto, não se tornar necessária uma elaboração de tabelas explícita dos estados de probabilidade. Mais ainda, os estados só serão endereçados de forma implícita com base nos respectivos índices, tal como o 15 descrito na secção que se segue. Adicionalmente às regras de transição, tem de se especificar em que estados de probabilidade se torna necessário trocar o valor de LPS e o de MPS. Por norma, só se indica um desses estados especificados, o qual pode ser identificado, então, com base no respectivo índice p_state.

Divisão de intervalo sustentada por tabela A Figura 2 mostra o esquema modificado para a codificação aritmética sustentada por tabela, tal como aqui proposta. Após a determinação do LPS, em primeiro lugar é representada a amplitude do intervalo R predefinida em um valor quantificado Q, por meio de uma representação Qtab em tabela e uma operação de deslocamento apropriada (por q bit) . Em alternativa, e em casos especiais, também é possível efectuar a quantificação sem a ajuda de uma representação Qtab em tabela, utilizando apenas uma combinação de operações de deslocamento e mascaramento. Normalmente, neste caso, é efectuada uma quantificação relativamente grosseira em K = 2 ... 8 valores representativos. Também aqui não se efectua, em semelhança ao que acontece na estimativa de probabilidade, uma determinação explícita de Q, sendo apenas transferido um índice q_index para Q. Este índice é utilizado, juntamente com o índice p_state, para a caracterizaçao do estado de probabilidade actual para a determinação da amplitude do intervalo Rlps. Para tal, é utilizada a respectiva entrada da tabela Rtab. Aí encontram-se gravados os valores de produto R x PLPS (K . Nmax), como valores de número inteiro, que correspondem a todos os K valores quantificados de i? e Nmax estados de probabilidades diferentes, com uma exactidão de, em geral, b-2 bits. Na implementação prática existe aqui uma possibilidade de ponderar entre a necessidade de memória para o tamanho da tabela e a exactidão aritmética, o que, em última análise, determina a eficiência da codificação. 16

Ambos os valores de destino dao determinados pela granularidade da representação de R e PLps-

Na quarta etapa da Figura 2 é mostrado o modo como é efectuada a actualização do estado de probabilidade p_state, em função do evento bit que acabou de ser codificado. Para tal, são utilizadas as tabelas de transição Next_State_LPS e

Next_State_MPS que já foram mencionadas na secção anterior "Estimativa de probabilidade sustentada por tabelas". Estas operações correspondem ao processo de actualização descrito na Figura 1, etapa 4, mas que não está especificado ao pormenor. A Figura 3 mostra o esquema de processamento correspondente da descodificação aritmética sustentada por tabelas. Para a caracterização do intervalo parcial actual são utilizados, no descodificador, a amplitude do intervalo Re um valor V. Este último encontra-se abrangido pelo intervalo parcial e é sucessivamente aperfeiçoado a cada da leitura de bits. Tal como se pode verificar na Figura 3, as operações para a estimativa de probabilidade e determinação da amplitude do intervalo R são executadas em conformidade com as operações do codificador.

Codificação com distribuição uniforme da probabilidade

Em aplicações, nas quais devem der codificados, por exemplo, valores com sinal positivo/negativo, cuja distribuição de probabilidade está disposta de forma simétrica à volta do valor zero, será possível, normalmente, partir de uma distribuição uniforme para a codificação da informação de sinal positivo/negativo. Dado que, por um lado, esta informação deve ser incluída no fluxo aritmético de bits mas, por outro lado, no caso de uma probabilidade de P ~ 0.5, não é relevante utilizar todo o aparato da estimativa de probabilidade sustentada por tabelas, ainda relativamente trabalhoso, e da divisão de intervalo, é proposta, para esta situação especial, a opção da 17 utilização de um processo especial de codificador/descodificador, que será representado como se segue.

No codificador é possível determinar, para este caso especial, a amplitude do novo intervalo parcial, através de uma operação de deslocamento simples que corresponde à redução de 50% da amplitude do intervalo inicial R. Em dependência do valor do bit a ser codificado, será seleccionada a metade superior ou inferior de R como sendo o novo intervalo parcial (ver Figura 4) . A renormalização e a saída de bits que se seguem são efectuadas tal como no caso da solução sustentada por tabelas acima descrita.

No descodificador correspondente, as operações necessárias resumem-se à determinação do bit a ser descodificado por meio de uma simples operação de comparação, tendo em conta o valor de V em relação à amplitude do intervalo actual R. No caso de ser definido o bit descodificado, V deverá ser reduzido pelo montante de R. Tal como mostrado na Figura 4, a descodificação é concluída pela renormalização e pela actualização de V com o próximo bit a ser importado.

Uma realização alternativa da codificação de eventos com uma distribuição uniforme de probabilidade está representada na Figura 5. Nessa implementação de exemplo, a amplitude do intervalo actual R não é modificada. Em vez disso, no codificador o valor de V é duplicado através de uma operação de deslocamento. Em dependência do valor do bit a ser codificado, e em semelhança ao exemplo anterior, será seleccionada a metade superior ou inferior de R como sendo o novo intervalo parcial (ver Figura 5) .

A renormalização e a saída de bits que se seguem são efectuadas tal como no caso da solução sustentada por tabelas, acima descrita, com a diferença de não ser efectuada a duplicação de R 18 e L, e de a respectiva operaçao de comparaçao ser efectuada com valores limiares duplicados.

No respectivo descodificador da realização alternativa, em primeiro lugar, é lido um bit e é actualizado o valor U. A segunda etapa decorre da mesma forma que a etapa 1 na Figura 4, ou seja, o bit a ser descodificado é determinado por meio de uma simples operação de comparação, tendo em conta o valor de 1/ em relação à amplitude do intervalo actual R e, no caso de o bit descodificado ser definido, o valor 1/ deve ser reduzido pelo montante R (ver Figura 5).

Endereçamento e inicialização dos modelos de probabilidade

Cada modelo de probabilidade, tal como utilizado no invento apresentado, é caracterizado por meio de dois parâmetros: 1) o indice p_state, que caracteriza o estado de probabilidade de LPS, e 2) o valor valMPS do MPS. Cada um destes dois valores tem de ser inicializado logo no início da codificação ou descodificação de uma unidade de codificação encerrada (em aplicações de vídeo codificação trata-se de um segmento (slice)). Os valores de inicialização podem ser derivados de uma informação de controlo, por exemplo do parâmetro de quantificação (de um segmento (slice)), tal como exemplificado na Figura 6.

Processo de inicialização controlado em uma só direcção

Uma outra possibilidade de adaptação das distribuições iniciais dos modelos é disponibilizada pelo método que se segue. Para garantir uma melhor adaptação das inicializações dos modelos, é possível disponibilizar no codificador uma selecção de valores iniciais predefinidos dos modelos. Estes modelos podem ser agrupados em grupos de distribuições iniciais e podem ser endereçados com índices, para que, no codificador, seja efectuada a selecção adaptativa de um grupo de valores iniciais 19 e que forma inicia Lisboa sob esta informação seja transmitida ao descodificador de um índice. Este método é denominado processo de ização controlado em uma só direcção. 25 de Fevereiro de 2009. 20 [1] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Bibliografia T. Wiegand, G. Sullivan, "Draft Text of Final Draft International Standard (FDIS) of Joint Video Specification (ITU-T Rec. H. 264 / ISO/IEC 14496-10 AVC)" JVT-G050, Março 2003. D. A. Huffman, " A Method for Construction of Minimum Redundancy code", Proc. IRE, Vol. 40, pp. 1098-1101, 1952. I. H. Witten, R. M. Neal, J. G. Cleary, "Arithmetic Coding for Data Compression", Communication of the ACM, Vol. 30, No. 6, pp. 520-540, 1987. G. G. Langdon, J. Rissanen, "A Simple General Binary Source code" , IEEE Transactions on Information Theory, Vol. 28, pp. 800-803, 1982. C. E. Shannon, "A Mathematical Theory of Communication", Bell Syst. Tech. Journal, Vol. 27, pp. 379-423, 623-656, 1948. P. Elias, in "Information Theory and Coding", N. Abramson (Ed.), New York, Mc-Gra-Hill, 1963.. J. Rissanen, "Generalized Kraft Inequality and Arithmetic Coding", IBM J. Res. Develop., Vol. 20, pp. 198-203, 1976. R. C. Pasco, "Source Coding and Algorythms for Fast Data Compression", Ph. D. Dissertation, Stanford University, USA, 1976. G. G. Langdon, "An Introduction to Arithmetic Coding", IBM J. Res. Develop., Vol. 28, pp. 135-149, 1984. A. Moffat, R. M. Neal, I. H. Witten, "Arithmetic Coding Revisited", Proc. IEEE Data Compression Conference, Snowbird (USA), pp. 202-211, 1996. J. Rissanen, K. M. Mohiuddin, "A Multiplication-Free Multialphabet Arithmetic Arithmetic Code", IEEE Trans. on Communication, Vol 37, pp. 93-98, 1989. 21 [11] [12] W. B. Pennebaker, J. L. Mitchell, G.G. Langdon, R. B. Arps, "An OverView of the Basic Principies of the Q-Coder Adaptive Binary Arithmetic Coder", IBM J. Res.

Develop., Vol. 32, pp. 717-726, 1988.

[13] P. G. Howard, J. S. Vitter, "Practical Implementations of Arithmetic Coding", in "Image and Text Compression", J. Storer (Ed.), Norwell (USA), Kluwer, 1992.

[14] L. Huynh, A Moffat, "A Probability-Ratio Approach to Approximate Binary Arithmetic Coding", IEEE Trans. on Information Theory, Vol. 43, pp. 1658-1662, 1997.

[15] D. Chevron, E. D. Karnin, E. Walach, "High-Efficiency, Multiplication Free Approximation of Arithmetic Coding", Proc. IEEE Data Compression Conference, Snowbird (USA), pp. 43-52, 1991.

[16] G. Feygin, P. G. Gulak, P. Chow, "Minimizing Excess Code Length and VLSI Complexity in the Multiplication Free Approximation of Arithmetic Coding ", Inform. Proc. Manag., Vol. 30, pp. 805-816, 1994.

[17] D. L. Duttweiler , Ch. Chamzas, "Probability Estimation in Arithmetic and Adaptive-huffman Entropy Coders", IEEE Trans. of Image Processing, Vol. 4, pp. 237-246, 1995. 22

Claims

REIVINDICAÇÕES 1. Processo para a codificação aritmética de um símbolo em estado binário a ser codificado, na base de uma amplitude do intervalo actual R e de uma probabilidade que representa uma estimativa de probabilidade para o símbolo a ser codificado, sendo que a probabilidade é representada através de um índice de probabilidade para endereçar um estado de probabilidade, a partir de uma multiplicidade de estados de probabilidade representativos. 0 processo caracterizado por apresentar as seguintes etapas: codificação do símbolo a ser codificado, executando as seguintes etapas parciais: representação da amplitude do intervalo actual em um índice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e execução da divisão do intervalo por meio de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade para obter um valor de amplitude do intervalo parcial, em que a etapa parcial de representação apresenta a aplicação de uma operação de deslocamento e mascaramento de bits a uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q^index = (R » q) & Qmask, sendo que Qmask representa uma máscara de bits, seleccionada em função do número de índices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits. 1
2. Processo de acordo com a reivindicação 1, caracterizado por a codificação ser efectuada também por meio da seguinte etapa: - actualização da amplitude do intervalo actual com a ajuda do valor da amplitude do intervalo, com o intuito de obter uma amplitude do intervalo nova e actualizada.
3. Processo de acordo com a reivindicação 1 ou 2, caracterizado por o valor de amplitude do intervalo parcial indicar uma amplitude de um intervalo parcial para um símbolo a ser codificado, com um estado menos provável de um intervalo actual com a actual amplitude do intervalo.
4. Processo de acordo com uma das reivindicações 1 a 3, caracterizado por a actualização da amplitude do intervalo actual ser executada em função do estado binário do símbolo a ser codificado.
5. Processo de acordo com uma das reivindicações anteriores, caracterizado por ainda apresentar a seguinte etapa: adaptação da estimativa de probabilidade, sendo que a estimativa de probabilidade abrange a utilização, por meio do índice de probabilidade, de uma tabela de regras de transição LPS (Next_State_LPS) , para obter um novo indice de probabilidade quando o símbolo a ser codificado apresenta um estado menos provável, assim como a utilização, por meio do índice de probabilidade, de uma tabela de regras de transição MPS (Next_State_MPS), para obter um novo índice de probabilidade quando o símbolo a ser codificado apresenta um estado mais provável.
6. Processo de acordo com a reivindicação 5 que, para além do já mencionado, é caracterizado por conversão de um valor que indica o estado mais provável de um estado inicialmente indicado num estado binário do símbolo a codificar, quando o índice de 2 probabilidade se assemelha a um índice de probabilidade predefinido e quando o símbolo a ser codificado apresenta um estado binário diferente do estado inicialmente indicado.
7. Processo de acordo com uma das reivindicações 1 a 6, caracterizado por a etapa parcial de actualização da amplitude do intervalo actual apresentar as seguintes etapas: equiparar a nova amplitude do intervalo à diferença da amplitude do intervalo actual menos o valor da amplitude do intervalo parcial e, - em seguida, se o símbolo a ser codificado apresentar um estado menos provável, equiparar a nova amplitude do intervalo ao valor da amplitude do intervalo parcial.
8. Processo de acordo com uma das reivindicações anteriores, caracterizado por um intervalo actual ser representado pela amplitude do intervalo actual e um ponto inicial actual, e em que a codificação é executada por meio da seguinte etapa parcial: - adição do ponto de aplicação actual e de uma diferença entre a amplitude do intervalo actual e o valor da amplitude do intervalo parcial, para obter um ponto de aplicação novo e actualizado, quando o símbolo a ser codificado apresenta um estado menos provável.
9. Processo para a descodificação aritmética de um símbolo codificado em estado binário, na base de uma amplitude do intervalo actual R e uma probabilidade que representa uma estimativa de probabilidade para o símbolo codificado, sendo que a probabilidade é representada através de um índice de probabilidade de um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos. 0 processo caracterizado por apresentar as seguintes etapas: 3 - descodificação do simbolo codificado, executando as seguintes etapas parciais: representação da amplitude do intervalo actual em um indice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e execução da divisão do intervalo, por meio de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a etapa parcial de representação apresenta a aplicação de uma operação de deslocamento e mascaramento de bits a uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q_index = (R >> q) & Qmask, sendo que Qmask representa uma máscara de bits seleccionada em função do número de índices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits.
10. Processo de acordo com a reivindicação 9, caracterizado por a descodificação ser efectuada também por meio da seguinte etapa: - actualização da amplitude do intervalo actual com a ajuda do valor da amplitude do intervalo parcial, com o intuito de obter uma amplitude do intervalo nova e actualizada.
11. Processo de acordo com a reivindicação 9 ou 10, caracterizado por o valor de amplitude do intervalo parcial indicar uma amplitude de um intervalo parcial para um símbolo codificado, com um estado menos provável de um intervalo actual com a actual amplitude do intervalo. 4
12. Processo de acordo com uma das reivindicações 9 a 11, em que a execução da actualização da amplitude do intervalo actual também é dependente de um valor abrangido por um novo intervalo parcial, caracterizado por amplitude do intervalo parcial actual e por um valor abrangido por um novo intervalo parcial.
13. Processo de acordo com a reivindicação 12, caracterizado por a descodificação ser efectuada também por meio da seguinte etapa parcial: - equiparar o estado binário do símbolo codificado a um estado menos provável e a um estado mais provável, em função de se o valor abrangido pelo novo intervalo parcial é superior ou inferior a uma diferença entre a amplitude do intervalo actual e o valor da amplitude do intervalo parcial.
14. Processo de acordo com a reivindicação 12 ou 13, caracterizado por a codificação ser efectuada por meio da actualização do valor abrangido pelo novo intervalo parcial com um próximo bit a ser importado.
15. Processo de acordo com uma das reivindicações 12 a 14, caracterizado por ainda apresentar as seguintes etapas: actualização da estimativa de probabilidade, sendo que a actualização da estimativa de probabilidade abrange a utilização, por meio do índice de probabilidade, de uma tabela de regras de transição LPS (Next_State_LPS) , para obter um novo índice de probabilidade quando o valor abrangido pelo novo intervalo parcial for superior a uma diferença entre a amplitude do intervalo actual e o valor da amplitude do intervalo parcial, e a utilização, por meio do índice de probabilidade, de uma tabela de regras de transição MPS (Next_State_MPS) , para obter um novo índice de probabilidade quando o valor abrangido pelo novo intervalo parcial for inferior a uma diferença entre a 5 amplitude do intervalo actual e o valor da amplitude do intervalo parcial.
16. Processo de acordo com uma das reivindicações 12 a 15, caracterizado por conversão de um valor que indica o estado mais provável do simbolo codificado de um estado inicialmente indicado num estado binário diferente, quando o indice de probabilidade se assemelha a um indice de probabilidade predefinido e o valor abrangido pelo novo intervalo parcial for superior a uma diferença entre a amplitude do intervalo actual e o valor da amplitude do intervalo parcial.
17. Processo de acordo com uma das reivindicações anteriores, caracterizado por a amplitude do intervalo actual ser representada com uma precisão de b bits, e em que o valor da amplitude do intervalo parcial obtido pela tabela de divisão de intervalo é representado com uma precisão de b-2 bits.
18. Processo de acordo com uma das reivindicações anteriores, caracterizado por - a etapa parcial de representação incluir a aplicação de uma operação de deslocamento numa representação da amplitude do intervalo actual, binária/interna do computador, para obter um valor quantificado para a amplitude do intervalo actual, assim como, um acesso subsequente a uma tabela (Qtab) para obter o indice de quantificação.
19. Processo de acordo com uma das reivindicações anteriores, caracterizado por - na tabela de divisão do intervalo existem, em uma tabela Rtab, valores para a amplitude do intervalo actual como valores de produto entre os índices de quantificação, valores esses que correspondem a todos os índices de quantificação possíveis e a todos os índices de probabilidade. 6
20. Processo de acordo com uma das reivindicações anteriores, caracterizado por ainda apresentar a seguinte etapa: actualização da estimativa de probabilidade, sendo que a actualização da estimativa de probabilidade é efectuada por meio de regras de transição, sendo que as regras de transição indicam o novo estado de probabilidade, de uma multiplicidade de estados de probabilidade, com base em um simbolo a ser codificado ou já codificado, que é utilizado para o simbolo seguinte a ser codificado ou já codificado.
21. Processo de acordo com uma das reivindicações anteriores, caracterizado por ainda apresentar a seguinte etapa: actualização da estimativa de probabilidade, sendo que a actualização da estimativa de probabilidade abrange a utilização, por meio do índice de probabilidade, de uma tabela de regras de transição LPS (Next_State_LPS) , para obter um novo índice de probabilidade.
22. Processo de acordo com uma das reivindicações anteriores, caracterizado por - o número de índices possíveis de quantificação e/ou o número de estados de probabilidade serem seleccionados em função do grau de precisão da codificação predefinido e/ou em função do espaço de memória disponível.
23. Processo de acordo com uma das reivindicações anteriores, caracterizado por ainda apresentar a seguinte etapa parcial: - renormalização do ponto de aplicação novo, actualizado, e da amplitude do intervalo nova, actualizada. 7
24. Processo de acordo com uma das reivindicações anteriores, caracterizado por, perante uma distribuição de probabilidade uniforme, ser aplicada a seguinte fórmula de cálculo durante a codificação: R <- R » 1 if (bit = 1) then L <- L + R, OU ser aplicada a seguinte fórmula de cálculo: L <- L « 1 if (bit = 1) then L <- L + R, e nesta última alternativa ser efectuada uma renormalização com duplicação dos valores limiares de decisão, porém sem duplicação de L e R, ser aplicada a seguinte fórmula de cálculo, de acordo com a reivindicação 13, durante a descodificação: R «- R » 1 if (V > R) then bit <- 1 V < V - R, else bit <- 0, ou a seguinte formula de cálculo: 3. Leitura de um bit e actualização de V 4. Determinação de bit, em função do posicionamento do intervalo parcial: if (V > R) then bit <- 1 V <- V — R, else 8 bit <- Ο.
25. Processo de acordo com uma das reivindicações anteriores, caracterizado por - a inicialização dos modelos de probabilidade ser efectuada em função de um parâmetro de quantificação SliceQP e em função dos parâmetros modelo predefinidos m e n, sendo que SliceQP descreve o parâmetro de quantificação predefinido no inicio de um Seqmento e m e n descrevem os parâmetros modelo.
26. Processo de acordo com uma das reivindicações anteriores, caracterizado por a inicialização do modelo de probabilidade abranqer as seguintes etapas: 1. preState = min(max(l, ((m * SliceQP) >> 4) +n), 2*N) 2. if (preState <=N) then P_state = N - preState valMPS = 0 else p_state = preState - (N+l) valMPS = 1, sendo que valMPS descreve o bit correspondente ao MPS, SliceQP descreve o parâmetro de quantificação predefinido no inicio de um segmento (slice) e m e n descrevem os parâmetros modelo.
27. Processo de acordo com uma das reivindicações anteriores, caracterizado por - a estimativa de probabilidade dos estados é efectuada por meio de uma máquina de estados finitos (finite State machine, FSM). 9
28. Processo de acordo com uma das reivindicações anteriores, caracterizado por a geração dos estados de probabilidade ser efectuada offline.
29. Processo de acordo com uma das reivindicações anteriores, caracterizado por a selecção dos estados depender da estatística dos dados a serem codificados e/ou do número dos estados.
30. Disposição para a codificação aritmética de um sistema a ser codificado, com estado binário, com base numa amplitude do intervalo actual R e uma probabilidade que representa uma estimativa de probabilidade para o símbolo a ser codificado, sendo que a probabilidade representada por um índice de probabilidade para endereçar um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos, o dispositivo caracterizado por apresentar as seguintes características: - um dispositivo para a codificação do símbolo a ser codificado e que apresenta as seguintes dispositivo: - um dispositivo para a representação da amplitude do intervalo actual em um índice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e - uma instalação para a execução da divisão de intervalo por meio de utilização de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a instalação para a representação está concebida para aplicação de uma operação de deslocamento e mascaramento de bits em uma representação binária/interna do computador da amplitude do intervalo actual,nomeadamente de acordo com a seguinte fórmula de cálculo q__index = (R » q) & Qmask, sendo que Qmask 10 representa uma máscara de bits apropriada, seleccionada em função do número de índices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits.
31. Dispositivo para a descodificação aritmética de um sistema codificado, com estado binário, com base numa amplitude do intervalo actual R e uma probabilidade que representa uma estimativa de probabilidade para o símbolo codificado, sendo que a probabilidade é representada por um índice de probabilidade para endereçar um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos, o dispositivo caracterizado por apresentar as seguintes características: - um dispositivo para a descodificação do símbolo codificado e que apresenta os seguintes dispositivos: - uma instalação para a representação da amplitude do intervalo actual em um índice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e - uma instalação para a execução da divisão de intervalo por meio de utilização de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a instalação para a representação está concebida para aplicação de uma operação de deslocamento e mascaramento de bits a uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q_index = (R » q) & Qmask, sendo que Qmask representa uma máscara de bits apropriada, seleccionada em função do número de índices de quantificação representativos, R 11 representa a amplitude do intervalo actual e q um número de bits.
32. Programa informático que permite ao computador, depois da respectiva transferência para a memória do computador, executar um processo para a codificação aritmética de um símbolo a ser codificado, com estado binário, com base em uma amplitude do intervalo actual R e uma probabilidade que representa uma estimativa de probabilidade para o símbolo a ser codificado, sendo que a probabilidade é representada por um índice de probabilidade para endereçar um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos, o processo caracterizado por apresentar a seguinte etapa: - codificação do símbolo a ser codificado, por meio da execução das seguintes etapas parciais: representação da amplitude do intervalo actual em um índice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e execução da divisão de intervalo, por meio de utilização de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a etapa parcial de representação apresenta a aplicação de uma operação de deslocamento e mascaramento de bits em uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q_index = (R >> q) & Qmask, sendo que Qmask representa uma máscara de bits seleccionada em função do número de índices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits. 12
33. Programa informático que permite ao computador, depois da respectiva transferência para a memória do computador, executar um processo para a descodificação aritmética de um simbolo codificado, com estado binário, com base em uma amplitude do intervalo actual R e uma probabilidade que representa uma estimativa de probabilidade para o símbolo codificado, sendo que a probabilidade é representada por um índice de probabilidade para endereçar um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos, o processo caracterlzado por apresentar a seguinte etapa: - descodificação do símbolo codificado, por meio da execução das seguintes etapas parciais: representação da amplitude do intervalo actual em um índice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e execução da divisão de intervalo, por meio de utilização de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a etapa parcial de representação apresenta a aplicação de uma operação de deslocamento e mascaramento de bits em uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q_index = (R » q) & Qmask, sendo que Qmask representa uma máscara de bits seleccionada em função do número de índices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits.
34. Suporte de memória que é legível pelo computador, no qual se encontra gravado um programa que permite a um computador, após a respectiva transferência para a memória do computador, executar um processo para a codificação aritmética de um símbolo a ser 13 codificado, com estado binário, com base em uma amplitude do intervalo actual R e uma probabilidade que representa uma estimativa de probabilidade para o simbolo a ser codificado, sendo que a probabilidade é representada por um indice de probabilidade para endereçar um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos, o processo caracterizado por apresentar a seguinte etapa: - codificação do simbolo a ser codificado, por meio da execução das seguintes etapas parciais: representação da amplitude do intervalo actual em um indice de quantificação a partir de uma multiplicidade de índices de quantificação representativos, e execução da divisão de intervalo, por meio de utilização de uma tabela de divisão de intervalo, utilizando o índice de quantificação e o índice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a etapa parcial de representação apresenta a aplicação de uma operação de deslocamento e mascaramento de bits em uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q_index = (R » q) & Qmask, sendo que Qmask representa uma máscara de bits seleccionada em função do número de índices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits.
35. Suporte de memória que é legível pelo computador, no qual se encontra gravado um programa que permite a um computador, após a respectiva transferência para a memória do computador, executar um processo para a descodificação aritmética de um símbolo codificado, com estado binário, com base em uma amplitude do intervalo actual R e uma probabilidade que representa uma 14 estimativa de probabilidade para o simbolo codificado, sendo que a probabilidade é representada por um indice de probabilidade para endereçar um estado de probabilidade a partir de uma multiplicidade de estados de probabilidade representativos, o processo caracterizado por apresentar a seguinte etapa: - descodificação do simbolo codificado, por meio da execução das seguintes etapas parciais: representação da amplitude do intervalo actual em um indice de quantificação a partir de uma multiplicidade de indices de quantificação representativos, e execução da divisão de intervalo, por meio de utilização de uma tabela de divisão de intervalo, utilizando o indice de quantificação e o indice de probabilidade, para obter um valor de amplitude do intervalo parcial, em que a etapa parcial de representação apresenta a aplicação de uma operação de deslocamento e mascaramento de bits em uma representação binária/interna do computador da amplitude do intervalo actual, nomeadamente de acordo com a seguinte fórmula de cálculo q_index = (R >> q) & Qmask, sendo que Qmask representa uma máscara de bits seleccionada em função do número de indices de quantificação representativos, R representa a amplitude do intervalo actual e q um número de bits.
36. Suporte de memória que é legível pelo computador, caracterizado por se encontrar gravado um programa que permite a um computador, após a respectiva transferência para a memória do computador, executar um processo de acordo com as reivindicações 32 e 33. Lisboa, 25 de Fevereiro de 2009. 15 1. Determinação do LPS2. Cálculo dos valores Rlps e Rmps Rlps = R x Rlps Rmps = R — Rlps 3. Cálculo do novo intervalo parcial: if (bit = LPS) then L <— L + Rmps R <— Rlpselse R <— Rmps 4. Actualização da estimativa de probabilidade Plps 5. Saída de bits e renormalização de R FIG. 1 1/6 1. Determinação do LPS 2. Quantificação de R: q_index = Qtab [R»q] 3. Determinação de Rlps e Rmps Rlps = Rtab [q_index, p_state] Rmps = R — Rlps 4. Cálculo do novo intervalo parcial: if (bit = LPS) then L <— L + Rmps R <— Rlps p_state <— Next_State_LPS [p_state] else R <— Rmps p_state <— Next_State_MPS [p_state] FIG.2 2/6 1. Determinação do LPS2. Quantificação de R: q_index = Qtab [R»q]3. Determinação de Rlps e Rmps: Rlps = Rtab [q_index, p_state] Rmps = R — Rlps 4. Determinação de bit, consoante o posicionamento do intervalo parcial: if (V > LPS) then bit <- LPS V <- V - Rlps R <— Rlps p_state <— Next_State_LPS [p_state]else bit <- MPS R <—Rmps p_state <— Next_State_MPS [p_state] 5. Renormalização de R, leitura de um bit e actualização de V FIG.3 3/6 Codificador: 1. Cálculo do novo intervalo parcial: R <— R » 1 if (bit =1) then L <— L + R 2. Saída/emissão de bits e renormalização de R Descodificador: 1. Determinação de bit, consoante o posicionamento do intervalo parcial: if (V > R) then bit <— 1 V-R 2. Saída/emissão de um bit, renormalização de R e actualização de V FIG.4 4/6 Codificador: 1. Cálculo do novo intervalo parcial: L <— L « 1 if (bit =1) then L <— L + R 2. Emissão de um bit e renormalização com valores limiares de decisão duplicados (sem duplicação de R e L) Descodificador: 1. Saída/emissão de um bit e actualização de V 2. Determinação de bit, consoante o posicionamento do intervalo parcial: if (V > R) then bit <— 1 V-R else bit <— 0 FIG.5 5/6 1. preState = min (max ( 1, ((m * SliceQP ) »4) + n), 126) 2. if (preState <= 63) then p_state = 63 - preState valMPS = 0 else p_state = preState - 64 valMPS = 1 FIG. 6 6/6