terça-feira, 19 de janeiro de 2016

Métodos de ordenação

Hoje iremos falar sobre métodos de ordenação.

Ordenação é o ato de classificar uma sequência de elementos em uma ordem predefinida, geralmente em ordem crescente ou decrescente.

Dado uma sequência de n elementos:
<a1, a2, a3, ..., an>

A saída será uma permutação (reordenada):
<a'1, a'2, a'3, ..., a'n>

tal que:
a'1 ≤ a'2 ≤ a'3 ≤ ... ≤ a'n
Os algoritmos que ordenam um conjunto de elementos são os algoritmos de ordenação, são exemplos de algoritmos de ordenação BubbleSort, InsertionSort, SelectionSort, MergeSort e QuickSort.

A princípio introduziremos com os métodos de ordenação mais simples, BubbleSort, InsertionSort e SelectionSort.

Para os psuedo-códigos adotaremos A sendo o vetor de elementos, p a posição de início do vetor e r a posição final do vetor.


  • BubbleSort

A ordenação por flutuação. A ideia é percorrer o vetor e a cada passagem flutuando para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

Pseudo-código
Algoritmo BubbleSort (A, p, r)
    para ls ← n até 2 faça
        para i ← 1 até ls - 1 faça
            se A[i] > A[i+1] então
                troca (A[i], A[i+1])

Complexidade:
Melhor caso: Θ(n2)
Pior caso: Θ(n2)

  • InsertionSort

A ordenação por inserção. O funcionamento do algoritmo é percorrer um vetor da esquerda para a direita de forma que os elementos mais à esquerda fiquem ordenados. O algoritmo de inserção é similar a organização das cartas em um jogo de baralho.

Foto: Wikipédia

Pseudo-código
Algoritmo InsertionSort (A, p, r)
    para i ← p + 1 até r faça
        k ← A[i]
            j ← i - 1
        enquanto j ≥ p e A[j] > k
            A[j+1] ← A[j]
            j ← j + 1
    A[j+1] ← k

Complexidade:
Melhor caso: Θ(n)
Pior caso: Θ(n2)

  • SelectionSort

A ordenação por seleção tem o objetivo colocar o menor valor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim sucessivamente.

Foto: Wikipédia

Pseudo-código
Algoritmo SelectionSort (A, p, r)
    para i ← p até r - 1 faça
        j ← i + 1
        para k ← j + 1 até r faça
            se A[k] < A[j] então
                j ← k
        se A[j] < A[i] então
            troca(A[i], A[j])

Complexidade:
Melhor caso: Θ(n2)
Pior caso: Θ(n2)

segunda-feira, 7 de dezembro de 2015

Telecomunicações - Transmissor

O transmissor pode possuir três subsistemas: conversor A/D, modulador e codificador.


Conversor A/D
Mesmo que o sinal não seja originalmente digital, ele pode ser convertido. O processo de conversão é divido em três partes: amostragem, quantização e codificação.

Teorema da amostragem (Nyquist)
Um sinal pode ser reconstruído exatamente (sem qualquer erro) a partir de suas amostras em um tempo discreto tomadas uniformemente a uma taxa de R amostras por segundo. R deve ser igual ou maior que duas vezes a largura de banda (R >= 2B).

Quantização
Ao completar a conversão A/D, a mensagem original é representada por uma sequência de amostras, cada amostra assume um dos L níveis de quantização. No processo de quantização é gerada uma aproximação do sinal analógico em digital. A diferença entre o sinal analógico e o sinal digital gerado é chamado de ruído de quantização. Quanto maior a quantidade de níveis, menor vai ser o ruído de quantização, mas mais susceptível a perca de dados o sinal fica, devido a proximidade do níveis e a interferência causa pelo ruído do canal. E quanto menor a quantidade de níveis, menos susceptível ao ruído do meio e maior o ruído de quantização.

Codificação
É designação de cada nível quantizado por um dado código.

Modulação por codificação de pulso (PCM – Pulse-coded modulation)
Na PCM cada amostra quantizada é representada por uma combinação ordenada de dois pulsos básicos p1(t) para representa 1 e p0(t) para representar 0. Onde 0 e 1 são digitos binários referente a um bit de informação. Dessa forma, cada amostra pode ser mapeada como uma sequência de pulsos.

Observação: A sequência de pulsos é feita no domínio do tempo, para trabalhar sob o domínio do tempo é difícil, para isso existe a Transformada de Fourier, algoritmo que transforma o sinal do domínio do tempo para o domínio da frequência e vice-versa.

Formula
log b L = N
Onde N é o número de bits do sinal quantizado, sendo L a quantidade de níveis e b é a quantidade de símbolos (por exemplo, utilizando o código binário, b seria 2).


Em projeto de sistemas de comunicação consideramos algumas coisas, como as características do sinal e do canal.

Em um sistema de comunicação, os parâmetros e as limitações físicas fundamentais que controlam a taxa de transmissão e qualidade do canal são: largura de banda (B) e a potência do sinal (Ps).

Largura de Banda
A largura de banda de um canal, é o intervalo de frequências que ele é capaz de transmitir com razoável fidelidade, em outras palavras, é a medida da capacidade de transmissão de um determinado meio.

Potência do Sinal
Podemos entender essa potência como a força do sinal, que tem grande papel na transmissão, já que ela está relacionada a qualidade de transmissão. O aumento de Ps reforça o pulso do sinal.

SNR
O SNR é a relação Ps pela Pr (Potência do ruído), é ele que determina a qualidade de recuperação do sinal transmitido. Em toda transmissão é exigido uma SNR mínima.
Uma maior SNR significa que o pulso de sinais transmitido pode usar mais níveis de sinais, permitindo um maior número de bits em cada transmissão de pulso.

Capacidade do Canal
A capacidade do canal é a capacidade de transmissão de dados de forma confiável no canal, ela está diretamente relacionada a SNR e a largura de banda.
Um dos tipos de canais mais comuns é conhecido como canal com ruído gaussiano branco aditivo (AWGN – Addtive White Gaussian Noise), esse canal tem ruído conhecido e constante, sendo possível calcular a capacidade do canal, através da seguinte formula:
C = B log2 (1 + SNR) bit/s
Os dB tem uma relação com o sinal ruído, portanto a partir dos dB você pode encontrar a SNR do canal.
Q(dB) = 10 log10 (Ps/Pr)
Lembrando que:
Ps / Pr = SNR

Modulador
Os sinais banda base podem ser transmitidos diretamente por meio de um canal apropriado, mas dependendo das características do canal e do sinal (no domínio da frequência), sinais banda base não são adequados para serem transmitidos.
Quando as bandas de frequência do sinal e do canal não coincidem exatamente, os canais podem ser deslocados (em frequência). Os sinais podem ser modificados para que a transmissão se torne possível. Essa modificação é chamada de modulação, processo de variação de amplitude, frequência e/ou fase de uma portadora senoidal.

Portadora é uma senoide de alta frequência.

Os sinais de rádio por exemplo, são sinais modulados. Sinal AM (Amplitude Modulation) onde é feito uma variação da amplitude de um sinal senoidal (portadora), já o sinal FM (Frequence Modulation) a variação é feita na frequência de um sina senoidal. Ao aumentar a amplitude, estamos aumentando a potência do sinal fazendo com que tenha um alcance maior, mas com o aumento da potência do sinal também é aumentado a potência do ruído fazendo com que haja mais perca de dados, ou seja, uma menor qualidade da transmissão.


Codificador
A função básica do codificador de sinais fonte é reduzir a taxa de bits necessária para a transmissão da mensagem de acordo com a capacidade do canal de transmissão.


O que é Banda base?
Banda base ou baixa base, é faixa de frequência que é gerada pela fonte, por exemplo a voz humana, está na baixa base, onde sua frequência varia de de 0 podendo atingir até 4000 Hz. Também existe a banda passa (também chamada de banda passante) é um conjunto contínuo de valores de frequência e a banda alta que é um frequência que tende ao infinito no domínio da frequência.


Multiplexação
É essa técnica que permite mais de um canal de informação em um mesmo meio. Essa combinação pode ser feita por uma divisão da frequência, onde cada faixa de frequência determinada serve para transmitir um canal. Um exemplo é um cabo usado pela rede telefônica, onde o mesmo cabo serve tanto para o telefone quanto para a internet.
A multiplexação pode ser:
FDMA – Multiplexação por divisão de frequência.
TDMA – Multiplexação por divisão do tempo.

E como é feito para selecionar essas faixas?
Utilizando filtros, que são um tipo de circuito que seleciona uma determinada faixa de frequência. Existem quatro tipos de filtros: filtro passa baixa, passa faixa, passa alta e passa tudo.

Filtro passa baixa: aceita frequências chamadas de banda baixa.
Filtro passa faixa: aceita frequências chamadas de banda passa.
Filtro passa alta: aceita frequências chamadas de banda alta.
Filtro passa tudo: aceita todos os tipos de frequência.


Filtros Ideais vs Filtros Práticos
Não vou falar sobre os filtros, apenas deixarei uma imagem para que você tire suas próprias conclusões. Ah, só uma coisinha, filtros ideais não existe na prática, existem apenas em teoria.





Observação: Os receptores fazem o processo inverso dos transmissores, para no final a mensagem possa ser mostrada da forma que foi gerada.

sábado, 5 de dezembro de 2015

Telecomunicações - Sinais e Sistemas

Antigamente as mensagens eram transportadas por pombos-correio, luzes, fogo, corredores, sinais de fumaça, entre outros. Essas formas era adequadas para a época, mas conforme o mundo evoluiu os dados precisavam viajar mais rápidos, surgindo tecnologias que permitissem sistemas elétricos de comunicação.


Mas, o que é telecomunicações?
De forma simples, é o ramo da engenharia elétrica que abrange a projeção, implantação e manutenção dos sistemas de comunicação.


Analógica? Digital?
As mensagens podem ser digitais ou analógicas. Mensagens digitais possuem uma combinação ordenada de uma quantidade finita de símbolos ou palavras código, por exemplo, o alfabeto, código morse (sim, o código morse), fala humana. Já as mensagens analógicas possuem dados que variam de forma contínua, por exemplo, pressão, temperaturas, ondas de som.


Sinais

Não só as mensagens podem ser digitais ou analógicas, mas também os sinais. Na imagem você pode ver um conjunto de blocos, cada bloco ou um conjunto de blocos (no domínio do tempo) representa uma informação, enquanto no sinal analógica um bloco possui um conjunto de informações.

 
Os sinais também podem ser contínuos e discretos. Os discretos são formados por uma sequência de quantidades de inteiros discretos, onde cada sequência é uma amostra. Já os contínuos podem ser representando por uma função continua.


Hmm. E como é feito a transmissão das mensagens?
Veja a imagem a baixo:



Esse é um modelo simples do sistema de comunicação. Imagine uma transmissão de radio. Quando o apresentador fala no microfone, o som emitido é convertido por um transdutor de entrada em forma de ondas elétricas, referida como sinal banda base. O transmissor modifica o sinal em banda base para transmissão mais eficiente e logo após é transmitido por um canal, esse canal é o meio escolhido para fazer o transporte do sinal como um cabo coaxial ou uma fibra óptica, por exemplo.
O receptor processa o sinal recebido pelo canal, desfazendo as modificações feitas pelo transmissor, vale salientar que o sinal não chega ao receptor como foi transmitido por causa das distorções que são causadas pelo ruido durante a transmissão pelo canal. Depois de passar pelo receptor o sinal vai para o transdutor de saída que converte o sinal elétrico à sua forma original, que é a fala do apresentador.


Por que os sinais digitais são melhores que o analógico?
Simplesmente porque os sinais digitais são “imunes” ao ruído. Sempre que um sinal é transmitido pelo canal ele sofre interferência do ruído, essa interferência gera modificações no sinal transmitido fazendo com que haja perca de dados. Já o sinal digital, mesmo que haja interferência, o sinal pode ser regenerado.


Repetidores ajudam ainda mais…
Ao longo da transmissão o sinal vai perdendo qualidade, mesmo o sinal digital. Os repetidores são aparelhos que ao receber o sinal fazem a regeneração, possibilitando a retransmissão do sinal com qualidade e sem percas. Você pode está se perguntando se não pode ser feito com o sinal analógico… Poder pode. Mas, é viável? O sinal analógico não pode ser regenerado, a “solução” seria ampliar a potência do sinal, mas isso também iria aumentar o ruído… Resumindo, é inviável fazer isso com o sinal analógico.