Prazo de entrega recomendado: 23/05/2021

Nesta tarefa, vamos exercitar o projeto de algoritmos iterativos em Python para implementar algoritmos um pouco mais elaborados.

Adoramos conversar com nossos amigos pelo telefone e ouvir as nossas músicas preferidas tocarem na rádio. Não faz muito tempo, a qualidade da chamada dos telefone era tão ruim que não sabíamos com quem estávamos falando e ainda escutamos um bocado de ruído no rádio, dependendo de onde estivermos. Hoje os computadores e celulares prometem resolver esses problemas com o som digital.

Mas você já se perguntou como um áudio pode ser representado e armazenado na forma digital? Isso é, como transformamos uma onda sonora em uma sequência de bits? Essa transformação é feita por uma técnica de amostragem (sampling), que recebe um sinal analógico contínuo e devolve uma cadeia de números que representam as variações de amplitude do sinal no tempo. Quanto mais amostras em uma unidade de tempo, mais fiel será o áudio digital obtido.

Desta vez sua tarefa será processar sinais de áudio digitalizados. Um áudio digital será lido como uma lista de números reais que podem assumir valores positivos e negativos. Uma ilustração de um sinal exemplo é mostrada a seguir.

Mixando áudio

Um problema comum ao processar sinais digitais é a mixagem, isso é, a combinação de vários signais digitais distintos de entrada, formando um único sinal resultado. Pense, por exemplo, no sonoplasta que precisa combinar a voz e os vários instrumentos que foram gravados separadamente no estúdio.

Nesta tarefa, seu objetivo é criar um programa reamostrar.py que recebe vários sinais digitais e produz um sinal digital resultante.

Adicionando sinais

Para combinar dois ou mais sinais, precisamos entender um pouco do princípio de superposição de ondas. Simplificadamente, ele diz que a onda resultante é a soma das ondas parciais. Por exemplo, se duas pessoas falam ao mesmo tempo, então a voz de cada pessoa corresponde a uma onda sonora distinta, mas o que escutamos de fato é a soma dos dois sinais.

Se um mesmo sinal for tocado por duas caixas de som ao mesmo tempo, então iremos escutar o mesmo sinal original, mas com um volume bem mais alto (veja o exemplo acima à esquerda). Quando as amplitudes do sinal são negadas, podemos ter um efeito de cancelamento (veja o exemplo da direita). É esse fenômeno que é utilizado por alguns aparelhos para cancelamento de ruído. Para evitar que o volume resultante aumente, ao invés da soma, normalmente consideramos a média das amplitudes.

Reamostragem

Quando os sinais têm a mesma frequência de amostragem, combiná-los é fácil: basta calcular a média de cada amostra. Mas pode ser que os sinais de entrada não tenham a mesma frequência de amostragem. Por esse motivo, você deverá comprimir todos os sinais para que eles tenham a frequência do sinal com menor frequência.

Existem diversas técnicas para realizar reamostragem, mas nesta tarefa não estamos interessados nos algoritmos mais complexos. Iremos utilizar uma estratégia de interpolação descrita a seguir. Seja $s_i$ o $i$-ésimo sinal da entrada. Iremos denotar o número de amostras de $s_i$ por $n_i$ e o mínimo entre todos os números de amostras $n_{min}$. Um sinal $s_i$ pode ser entendido como um vetor, em que $s_{ij} \in \mathbb{R}$ é a $j$-ésima amostra do sinal $i$ com $j$ começando em $0$ e terminando em $n_i - 1$. Nosso objetivo é, para cada sinal $s_i$, criar um novo sinal comprimido $\bar{s}_i$ com apenas $n_{min}$ amostras.

Primeiro definimos uma função de interpolação $f_i(l, r)$ que corresponde à média aritmética das amostras de $s_i$ cujos índices estão em um intervalo semiaberto $[l, r)$. Observe que pode ser que os índices $l$ e $r$ não sejam inteiros, mas para calcular a média, iremos considerar todos os índices inteiros nesse intervalo. O comprimento de um intervalo será $d = \frac{n_i}{n_{min}}$. Com isso, podemos criar a $j$-ésima amostra no sinal comprimido $\bar{s}_{i}$ definindo $$\bar{s}_{ij} = f_i(d \cdot j, \quad d \cdot j + d).$$

Vejamos um exemplo. Suponha $s_i = (1, 2, 3, 4, 5, 6)$ e suponha $n_{min} = 4$, assim, $d = \frac{6}{4} = 1.5$. A amostra $\bar{s}_{i0}$ corresponde a $f_i(0, 1.5) = \frac{1 + 2}{2} = 1.5$. A amostra $\bar{s}_{i1}$ corresponde a $f_i(1.5, 3) = 3$. A amostra $\bar{s}_{i2}$ corresponde a $f_i(3, 4.5) = \frac{4+5}{2} = 4.5$. Por fim, a amostra $\bar{s}_{ic}$ corresponde a $f_i(4.5, 6) = 6$. Com isso, $\bar{s}_{i} = (1.5, 3, 4.5, 6)$.

Podemos ilustrar esse procedimento com a figura abaixo. Cada amostra $s_{ij}$ corresponde a um retângulo cinza de largura unitária e comprimento $s_{ij}$ (observe que o comprimento pode ser negativo). As coordenadas desse retângulo vão de de $j$ a $j+1$ no eixo horizontal. Cada amostra $\bar{s}_{ij}$ corresponde a um retângulo vermelho de largura $d$ com coordenadas $dj$ e $dj + d$ no eixo horizontal. O comprimento do retângulo vermelho é $f_i(d j, d j + d)$ e corresponde à media aritmética das alturas dos retângulos cinza cujas coordenadas $j$ intersectam o intervalo $[dj, dj+d)$ do eixo horizontal.

Entrada

A primeira linha da entrada contém um inteiro $m \ge 1$ que corresponde ao número de sinais digitais. Cada uma das próximas $m$ linhas contém uma sequência de números reais representando um diferente sinal digital. Vejamos exemplos a seguir.

Sinais de mesma frequência:

3
1.00 -2.00 3.00 0.00 
0.00 1.50 -1.20 -1.00
3.00 -1.50 1.50 1.00

Sinais de frequências múltiplas da menor:

4
1.00 1.00 -3.75 0.00 -2.45 1.00
1.00 -1.35 1.25
1.00 1.00 1.00 3.20 -1.50 2.25 0.50 -0.50 -1.75
1.00 -3.50 -2.25

Sinais de frequências arbitrarias:

3
1.00 2.00 3.00 4.00 5.00 6.00
4.50 -3.05 1.50 2.25
1.40 -3.50 1.25 -2.55 3.15

Saída

A saída deve ser uma única linha representando o sinal resultante recombinado após a reamostragem de cada sinal de entrada. Cada número é representado com duas casas decimais. Vejamos as saídas dos exemplos anteriores.

Sinais de mesma frequência:
```
1.33 -0.67 1.10 0.00
```
Sinais de frequências múltiplas da menor:
```
1.00 -1.35 -0.58
```
Sinais de frequências arbitrarias:
```
1.65 0.40 1.15 3.80
```

Dicas

Há várias formas de verificar se um número inteiro está em determinado intervalo real $[l, r)$, mas é preciso tomar cuidado com erros de aproximação nos números de ponto flutuante que representam os limites $l$ e $r$. Evite algoritmos que executam operações sobre pontos flutuantes sucessivamente.
Pode ser útil arredondar um número não inteiro. A biblioteca math já fornece algumas funções auxiliares para calcular o piso (math.floor(x)) e o teto (math.ceil(x)) de um certo número.
```
>>> import math
>>> x = math.pi
>>> x
3.141592653589793
>>> math.floor(x)
3
>>> math.ceil(x)
4
>>> math.floor(3)
3
>>> math.ceil(3)
3
```

Correção

Esta tarefa será avaliada pelo corretor automático e por um monitor, mas sem apresentação do aluno. Para obter o conceito C, você precisa resolver corretamente as unidades de testes com sinais de mesma frequência e com sinais de frequências múltiplas da menor frequência. Lembre-se de que seu programa deverá estar organizado em funções adequadamente, cada uma com uma responsabilidade bem definida. Crie uma função principal e não execute instruções no nível global. Não serão aceitos programas desorganizados ou ilegíveis.

Lembre-se de que o monitor poderá confirmar ou revisar a nota atribuída automaticamente. Atente-se para o relatório de correção da sua tarefa! Procure ler e entender o feedback dado pelo monitor e procure corrigir os problemas identificados nesta e em tarefas futuras. Se tiver dúvidas, não deixe de procurar atendimento.

A pasta da tarefa no seu repositório vem inicialmente com um arquivo nao_corrigir.txt que serve para indicar que você ainda está trabalhando nesta tarefa. Você pode realizar quantos pushes quanto forem necessários. O monitor só irá corrigir sua tarefa quando esse arquivo for removido do repositório.