Redes de Computadores I — material de estudo para a P2/Final
Prof. Luiz Carlos Pessoa Albini · baseado nos slides da disciplina e nas provas de 2010–2017 e do 1º semestre de 2026. Cada tema traz o conceito, a receita, as pegadinhas e as questões de prova ligadas ao tema. Todos os desenhos e tabelas de resolução são gerados pelas mesmas funções, então um gabarito nunca contradiz outro. Abra os “Ver resolução” só depois de tentar.
Convenção de ACK usada em todo o material (slide 14, p. 6): “ACK da mensagem k aceita k e todas as anteriores”, e qualquer resposta sobre k (inclusive NACK k) aceita as anteriores a k. Os slides de codificação (4, p. 6–29) trazem a grade de 00110101 sem a onda desenhada (o professor desenha ao vivo). Por isso o nível inicial de NRZ-I e de Manchester diferencial segue a convenção “começa no repouso (baixo)”.
0. Mapa da prova
| Tipo de questão | Provas em que caiu | Peso típico | Obrigatória? |
|---|---|---|---|
| Janela deslizante (Volta-N / Rep. Seletiva) | 2010, 13, 14, 15, 16, 16F, 17, 26 | 2,0–3,0 | quase sempre |
| “Rede completa” (montar quadro + paridade + duplex + mux + onda) | 13, 14, 15, 16, 16F, 17, 26 | 2,0–3,0 | quase sempre |
| Codificação digital | 10, 13, 14, 15, 16, 16F, 17, 26 | 0,5 por código | não |
| Modulação | 10, 13, 14, 15, 16, 16F, 17, 26 | 0,5 por modulação | não |
| Hamming | 13, 14, 15, 16F, 17, 26 (oráculo) | 1,0–2,0 | não |
| Duplexação + Multiplexação (desenhos) | 10, 13, 14, 16, 17 | 1,0–3,0 | não |
| CSMA/CD × CA, 64 bytes | 10, 15, 16F, 17, 26 | 1,0 | não |
Enquadramento (01111110) | 10, 14, 16, 17 | 1,0–1,5 | não |
| LZW | 13, 15, 16F | 1,0 | não |
| Taxa de sinalização × transmissão | 26 | 1,0 | não |
| Teoria isolada (paridades, Ethernet, ADSL, celular, canais 802.11, janela máxima) | 10, 15 | 1,0 | não |
1. Taxa de sinalização × taxa de transmissão
taxa de transmissão = taxa de sinalização ÷ transições por bit (pior caso)
| Código | Transições/bit (pior caso) | Pior caso | 10 000 transições/s → |
|---|---|---|---|
| NRZ | 1 | 1s e 0s alternados | 10 000 bps |
| NRZ-I | 1 | sequência de 1s | 10 000 bps |
| RZ | 2 | todo bit | 5 000 bps |
| Manchester | 2 | sequência de 1s ou de 0s | 5 000 bps |
| Manchester diferencial | 2 | sequência de 0s | 5 000 bps |
| AMI | 2 | sequência de 1s | 5 000 bps |
Slide 4-Codificação, p. 7–8, 13, 18, 25, 30, 34.
- Identifique quantas transições por bit o código exige no pior caso (tabela acima).
- Divida a taxa de sinalização por esse número.
- Justifique em uma frase, citando o pior caso.
Exemplo (2026 Q1): 200 000 000 bauds. NRZ = 200 Mbps (1 transição por bit no pior caso, 0101…). Manchester = 100 Mbps: sempre há uma transição no meio de cada bit e, numa sequência de bits iguais, também uma transição no início, o que dá 2 transições/bit. → ver na prova 2026
2. Codificação digital
| Código | Polaridade | Regra (texto do slide) | Uso / problema |
|---|---|---|---|
| NRZ | unipolar | 1 = pulso para cima; 0 = fica no repouso | Perde o sincronismo em sequências longas de 0s ou 1s. Uso: curta distância |
| NRZ-I | unipolar | 1 = inverte a linha; 0 = fica onde está | Perde o sincronismo em sequências longas de 0s. Solução: inserir um bit 1 a cada 4 bits (8 bits de dados → 10 na linha) |
| RZ | bipolar | 1 = pulso para cima; 0 = pulso para baixo; sempre volta ao repouso antes do fim do intervalo | 2 transições por bit |
| Manchester | unipolar | 1 = transição para cima no meio; 0 = transição para baixo no meio | Auto-sincronizável. Usado na Ethernet |
| Manchester diferencial | unipolar | Sempre há transição no meio; 1 = sem transição no início; 0 = com transição no início | A transição do meio carrega só o sincronismo; a do início carrega os dados |
| AMI | bipolar | 1 = alterna pulso para cima / para baixo; 0 = repouso | Telefone fixo |
Slide 4-Codificação, p. 3–35.
- Desenhe a grade: uma coluna por bit (linhas mais fortes a cada byte) e o bit escrito acima.
- Marque o repouso (tracejado) e defina o nível inicial: repouso/baixo antes do 1º bit (NRZ-I e Manchester diferencial).
- Aplique a regra bit a bit, da esquerda para a direita, olhando só o bit atual (NRZ, RZ, Manchester) ou também o nível anterior (NRZ-I, Manchester diferencial, AMI).
- Nos códigos com meio de intervalo (RZ, Manchester, Manchester diferencial), marque o meio de cada coluna.
- Confira o pior caso: o número de transições por bit bate com a tabela da seção 1?
- Rotule o desenho com o nome do código.
- Manchester × diferencial: no Manchester o dado está na direção da transição do meio. No diferencial o dado está na presença de transição no início (0 = tem, 1 = não tem).
- NRZ-I e Manchester diferencial dependem do nível anterior, então diga o nível inicial (aqui, repouso). Um erro no começo se propaga pelo resto do desenho.
- No AMI só os 1s alternam (o primeiro é +); os 0s ficam no repouso.
- “Usando códigos unipolares” (2026 Q2): NRZ, NRZ-I, Manchester e Manchester diferencial. RZ e AMI são bipolares e não valem.
Exemplo resolvido: 00110101 (a sequência dos slides)
3. Modulação
| Modulação | Bits por símbolo | Regra usada |
|---|---|---|
| AM (amplitude) | 1 | 1 = amplitude alta; 0 = amplitude baixa (mesma frequência) |
| FM (frequência) | 1 | 1 = frequência alta (mais ciclos no intervalo); 0 = frequência baixa |
| PM / fase | 1 | 0 = fase 0°; 1 = fase 180° (onda invertida); 1 ciclo por bit |
| QAM-4 | 2 | Amplitude constante; fase 00→45°, 01→135°, 11→225°, 10→315° |
| QAM-16 | 4 | 2 primeiros bits = amplitude (00→A1, 01→A2, 10→A3, 11→A4); 2 últimos = fase (00→0°, 01→90°, 11→180°, 10→270°) |
- Agrupe os bits pelo tamanho do símbolo (1 para AM/FM/PM, 2 para QAM-4, 4 para QAM-16).
- Desenhe uma coluna por símbolo, com o grupo de bits escrito em cima.
- Para cada símbolo, escolha amplitude/frequência/fase pela tabela e desenhe a senoide com o mesmo número de ciclos em todos os símbolos (exceto no FM).
- No QAM, escreva embaixo de cada símbolo a amplitude e a fase, e desenhe a constelação ao lado (vale ponto mostrar que você conhece o mapa).
- Rotule o desenho e diga “a cada mudança na onda são transmitidos N bits”.
- QAM-4 com 16 bits dá 8 símbolos, não 16. QAM-16 com 16 bits dá 4 símbolos.
- Na PM, deixe visível o “salto” da onda na fronteira entre símbolos de fase diferente.
- No AM, o 0 não é “amplitude zero” (não confundir com OOK). Use amplitude baixa, mas visível.
Exemplo resolvido: 11100010 01010101 (2013 Q5 / 2015 Q7)
4. Duplexação e multiplexação
Sentido da comunicação: antes de dividir o canal
Simplex: só um sentido. Half-duplex: ambos podem enviar, mas alternadamente. Full-duplex: ambos enviam simultaneamente. TDD alterna transmissão e recepção; FDD permite simultaneidade usando faixas distintas.
TDD × FDD — dividir os sentidos
TDD (Time Division Duplexing): usa toda a faixa em cada turno; a guarda dá tempo para inverter o canal. FDD (Frequency Division Duplexing): reserva uma faixa por sentido, com separação espectral e equipamento capaz de transmitir e receber simultaneamente.
“Metade do tempo” ou “metade da banda” é o caso simétrico dos slides, descontadas as guardas; a divisão não precisa ser 50/50. Os slides associam WiFi à alternância e telefonia celular ao FDD: não é uma regra universal — sistemas celulares também podem usar TDD.
TDM / TDMA — dividir o tempo entre transmissões
TDM (Time Division Multiplexing): intercala transmissões em slots; cada uma usa toda a banda durante seu slot. TDMA (Time Division Multiple Access): a mesma divisão aplicada ao acesso de máquinas diferentes, como celulares transmitindo para uma torre S. O “A” significa acesso múltiplo, não outro eixo de divisão.
No TDM fixo, a sequência de slots B | C | D forma um quadro que se repete. Slot sem dados permanece vazio. As guardas entre slots evitam sobreposição temporal; ocupam tempo sem transportar dados.
Variantes citadas nos slides: servidor e reserva
Com servidor: a máquina pede slots e informa por quanto tempo usará o canal; o servidor pode conceder um ou vários slots livres. Com reserva: também aceita pedidos para momentos futuros. Aqui a alocação é sob demanda, não a rodada fixa B | C | D.
FDM / FDMA — dividir a faixa de frequências
FDM (Frequency Division Multiplexing): transmissões simultâneas em sub-bandas diferentes, separadas por bandas de guarda. Cada transmissão recebe só parte da banda disponível. FDMA aplica essa divisão ao acesso de máquinas diferentes.
CDM / CDMA — separar por código, não por tempo ou frequência
CDM (Code Division Multiplexing): transmissões ocupam a mesma banda, ao mesmo tempo. Cada uma usa um código de Walsh diferente; o canal carrega a soma, e o receptor recupera a transmissão correlacionando a soma com o código desejado. CDMA é esse princípio no acesso de máquinas diferentes.
Chip é cada elemento do código: um bit é espalhado em vários chips. No exemplo, bit 1 envia o código e bit 0 envia seu oposto. O produto escalar entre códigos distintos é zero, por isso um não contribui para a correlação do outro no caso ideal sincronizado.
Nos slides: bits sincronizados, tempo por bit maior que no TDM/FDM e até 32 transmissões simultâneas. O 32 é a configuração apresentada, não um limite universal de CDM; com códigos Walsh de N chips há N códigos ortogonais. O exemplo acima usa dois códigos de quatro chips apenas para tornar a soma visível.
OFDM — subportadoras sobrepostas, mas ortogonais
OFDM (Orthogonal Frequency Division Multiplexing) divide os dados em fluxos paralelos enviados por subportadoras próximas. Seus espectros se sobrepõem, mas a separação correta entre frequências permite distingui-las no receptor: não basta sobrepor bandas arbitrariamente.
- Por que não se confundem? Na janela útil de símbolo Tu, subportadoras espaçadas por Δf = 1/Tu são ortogonais. No modelo ideal, ao separar uma subportadora, a contribuição das demais se anula.
- Ganho sobre FDM: aproveita melhor o espectro ao dispensar bandas de guarda largas entre cada par de subportadoras. A frase do slide “mais sub-canais e maiores” descreve esse aproveitamento, não uma garantia de velocidade para qualquer configuração.
- Condição: sincronismo de tempo e frequência; perder a ortogonalidade causa interferência entre subportadoras. Sistemas OFDM costumam usar prefixo cíclico, uma cópia do fim do símbolo colocada no início, para lidar com ecos; ele custa tempo e não é banda de guarda de FDM.
- Não confundir: QAM/PSK diz como os símbolos modulam cada subportadora; OFDM diz como elas são combinadas. OFDM não implica vários usuários: OFDMA distribui grupos de subportadoras entre usuários.
WDM — vários comprimentos de onda na mesma fibra
WDM (Wavelength Division Multiplexing) combina canais ópticos de comprimentos de onda λ diferentes em uma fibra. O MUX junta os canais; o DEMUX os separa no destino. É o equivalente óptico da divisão em frequência: f = v/λ, com v sendo a velocidade da luz no meio.
5-Duplexacao (p. 2–11); 6-Multiplexacao (p. 3–25); 7-DuplexMultiplex. Ortogonalidade, correlação, prefixo cíclico e distinção OFDM/OFDMA: complementos explicativos, além do texto dos slides.
Como combinar duplexação e multiplexação na prova
- Desenhe os eixos: tempo → na horizontal e frequência ↑ na vertical.
- Primeiro a duplexação: no TDD, alterne blocos de tempo “ida” e “volta” com guarda entre eles. No FDD, divida a altura em duas faixas (ida embaixo, volta em cima) com uma faixa de guarda no meio.
- Depois a multiplexação, dentro de cada sentido: TDM = slots de tempo por máquina; FDM = sub-bandas por máquina; CDM = um bloco único com todas as máquinas (Walsh).
- Rotule cada bloco com origem→destino. Hachure as guardas.
- Se a questão pedir as ondas, desenhe dentro de cada slot/banda a forma de onda dos bits daquele intervalo.
Os 6 combos (servidor A com máquinas B, C, D; tracejado = sentido de volta, A→máquina)
- Não confunda as guardas: TDD/TDM têm tempo de guarda; FDD/FDM têm frequência de guarda.
- No TDM fixo, slot vazio continua pertencendo à máquina; nas variantes com servidor, a alocação segue os pedidos e reservas.
- No CDM não existe divisão no desenho entre as máquinas: todos ocupam o bloco inteiro.
5. Enquadramento
| Delimitador de fim | Campo tamanho |
|---|---|
| Mensagem sem limite de tamanho. É preciso procurar o delimitador no meio dos dados e alterá-lo (bit stuffing). | Tamanho máximo = o maior número representável no campo. Os dados podem conter qualquer sequência. |
Slide 11-Enquadramento, p. 3–12.
- Escreva os dados contínuos, sem os espaços entre bytes; o delimitador pode atravessar dois bytes.
- Procure 01111110 e destaque. Explique que o receptor cortaria o quadro ali.
- Aplique a regra do slide: “se encontrar um 0 seguido por 5 1s, adiciona mais um 0” (011111 → 0111110). Continue varrendo e marque cada 0 inserido.
- Mostre o quadro final: 01111110 | dados com stuffing | 01111110.
- Mostre o receptor retirando cada 0 que vem depois de 0+11111, recuperando os dados originais.
- Cite a alternativa do campo tamanho.
Do dado ao quadro — e de volta ao dado
- Mesmo se a mensagem já tiver 0111110, insere de novo (slide 11 p. 9: 011111010 → 0111110010). O receptor sempre retira o 0, então a regra não tem exceção.
- A regra do professor exige o 0 antes dos cinco 1s. Uma sequência que começa com 11111 no início dos dados (sem 0 antes) não leva inserção.
Exemplo resolvido: 11111000 10101011 11000111 11100000 00111000 10101010 (2014 Q1 / 2016 Q1 / 2017 Q1)
6. Sequencialização
Slide 12-Sequencialização.
- seq(m) = (m − 1) mod 2bits quando a 1ª mensagem tem seq 0.
- Nas questões de rede, o seq começa em 0 para cada máquina (e para cada sentido): a 1ª mensagem de cada um é 00…0.
- Na janela: o seq é o que vai no quadro. Escreva também o nº da mensagem para não se perder depois que o contador estoura.
| Mensagem nº | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| seq (3 bits) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | … | 7 | 0 |
| seq (4 bits) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … | 15 | 0 |
7. Detecção de erros (paridades, checksum, CRC) e Hamming
- Horizontal: 1 bit de paridade por grupo/linha (ex.: a cada byte ou a cada 4 bits), colocado logo depois do grupo.
- Vertical: os grupos são empilhados e 1 bit é calculado por coluna, formando uma palavra de paridade do tamanho do grupo.
- Longitudinal: as duas juntas (bit por linha + palavra por coluna); permite localizar um bit errado.
- Checksum do slide: soma os bytes, conserva os 8 bits inferiores (módulo 256) e transmite o complemento de 2 dessa soma. O receptor soma os dados e o checksum e deve obter 0 módulo 256.
- CRC: divide a mensagem (com zeros acrescentados) por um polinômio gerador (ex.: 1001 = x³+1) em aritmética mod 2 e envia o resto. A Ethernet usa CRC-32 no FCS.
Slide 13-Detecção de Erros, p. 3–7.
7.1. Detectar não é necessariamente corrigir
Durante a transmissão, um bit pode inverter: 0 → 1 ou 1 → 0. O emissor calcula uma informação redundante, chamada verificador, e a envia junto dos dados. O receptor verifica se os dados recebidos continuam compatíveis com ela.
- Verificação falhou: houve erro no conjunto protegido, que inclui dados e verificador.
- Verificação passou: nenhum erro foi detectado; isso não garante que os dados estejam corretos.
- Detectar: perceber uma inconsistência. Corrigir: descobrir quais bits precisam ser invertidos para recuperar os dados.
7.2. Paridade par e ímpar — a regra básica
O bit de paridade faz a quantidade de 1s, incluindo ele mesmo, ficar par ou ímpar. Os dados 1011 têm três 1s:
| Convenção | Bit acrescentado | Resultado | Total de 1s |
|---|---|---|---|
| Paridade par | 1 | 1011 1 | 4 — par |
| Paridade ímpar | 0 | 1011 0 | 3 — ímpar |
Por que detecta erros? Uma inversão muda a quantidade de 1s em uma unidade: par vira ímpar e vice-versa. Duas inversões preservam a paridade. Logo, uma verificação de paridade simples detecta uma quantidade ímpar de inversões no conjunto protegido, mas não detecta uma quantidade par.
7.3. Paridade horizontal — um bit por linha
Na convenção deste material, cada grupo de dados é escrito em uma linha e recebe um bit à direita. O receptor verifica cada linha separadamente. Com paridade par:
| Dados | Quantidade de 1s | Paridade H | Linha transmitida |
|---|---|---|---|
| 1011 | 3 | 1 | 1011 1 |
| 0110 | 2 | 0 | 0110 0 |
| 0000 | 0 | 0 | 0000 0 |
| 1111 | 4 | 0 | 1111 0 |
Erro detectado: a primeira linha era 1011 1, mas chegou 1001 1. Agora há três 1s: a paridade par falhou. Sabemos a linha afetada, mas não qual bit está errado.
Erro não detectado: se chegar 1000 1, dois bits dos dados inverteram. O total continua par e a verificação passa.
7.4. Paridade vertical — um bit por coluna
Empilhe os mesmos grupos e conte os 1s em cada coluna. Os bits calculados formam uma palavra adicional, do mesmo tamanho de um grupo. Com paridade par:
| Linha | C1 | C2 | C3 | C4 |
|---|---|---|---|---|
| Dados 1 | 1 | 0 | 1 | 1 |
| Dados 2 | 0 | 1 | 1 | 0 |
| Dados 3 | 0 | 0 | 0 | 0 |
| Dados 4 | 1 | 1 | 1 | 1 |
| Quantidade de 1s | 2 | 2 | 3 | 2 |
| Paridade vertical par | 0 | 0 | 1 | 0 |
A palavra de paridade é 0010. Ela é enviada além dos dados, na posição definida pelo formato do quadro. O receptor confere se cada coluna, incluindo a palavra de paridade, tem quantidade par de 1s.
Diferença prática: horizontal resume cada grupo em um bit; vertical resume o bloco de grupos em uma palavra. Limitação da vertical: duas inversões na mesma coluna preservam a paridade daquela coluna.
7.5. Paridade longitudinal — as duas juntas neste material
Aqui, longitudinal combina a horizontal com a vertical, formando uma paridade bidimensional. A tabela abaixo usa paridade par em todas as linhas e colunas:
Atenção à nomenclatura: em outros materiais, “longitudinal/LRC” também pode designar apenas a verificação por colunas. Para resolver as questões deste resumo, mantenha a convenção aqui adotada e observe como o enunciado organiza os grupos.
| Linha | C1 | C2 | C3 | C4 | H |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 |
| 4 | 1 | 1 | 1 | 1 | 0 |
| V | 0 | 0 | 1 | 0 | 1 |
O canto inferior direito completa as verificações: tanto a última linha quanto a última coluna ficam com paridade par.
- Suponha que o bit da linha 2, coluna 3 inverta de 1 para 0.
- A verificação da linha 2 falha.
- A verificação da coluna 3 também falha.
- A interseção aponta o bit errado. Assumindo exatamente uma inversão, basta inverter esse bit para corrigir.
Exemplo — paridade ímpar sobre 1011 0110 0000 1111 (grupos de 4)
| Grupo | nº de 1s | Horizontal ímpar |
|---|---|---|
| 1011 | 3 | 10110 |
| 0110 | 2 | 01101 |
| 0000 | 0 | 00001 |
| 1111 | 4 | 11111 |
| Vertical ímpar (por coluna) | colunas: 2,2,3,2 | 1101 |
| Longitudinal | Linhas com H: 10110 01101 00001 11111; palavra vertical com canto: 11010. O canto é 0: a coluna H tem 3 uns e a palavra vertical tem 3 uns; ambos permanecem ímpares. O exemplo usa matriz 4×4 para satisfazer as duas verificações do canto. | |
Paridade bidimensional — achar a linha e a coluna
CRC — divisão módulo 2, passo a passo
7.6. Checksum — somar os valores dos grupos
Em vez de contar 1s, o checksum faz uma operação aritmética sobre os dados. Na variante usada neste material, somam-se os bytes e transmite-se um valor que faz a soma total dar zero módulo 256. “Módulo 256” significa conservar o resto da divisão por 256, isto é, os oito bits inferiores.
- Some os valores dos bytes.
- Conserve somente os oito bits inferiores: S = soma mod 256.
- Calcule checksum = (−S) mod 256. Em oito bits, isso corresponde ao complemento de 2: inverter os bits e somar 1, descartando eventual carry.
- Envie os dados e o checksum.
- O receptor soma tudo, incluindo o checksum: o resultado deve ser 0 módulo 256.
Exemplo pequeno — dois bytes com valores 200 e 100
| Etapa | Cálculo | Resultado |
|---|---|---|
| Somar os dados | 200 + 100 | 300 |
| Conservar oito bits | 300 mod 256 | 44 |
| Calcular o checksum | −44 mod 256 | 212 |
| Conferir no receptor | (200 + 100 + 212) mod 256 | 0 |
São enviados os bytes de dados 200 e 100, mais o checksum 212. Se o primeiro byte chegar como 201, o receptor obtém (201 + 100 + 212) mod 256 = 1: erro detectado.
Exemplo numérico já usado no material — slide 13, p. 6
Bytes: 10110001 + 10000110 + 01001100 + 11111111 + 10100000 = 177+134+76+255+160 = 802 = 0011 0010 0010. Conservando 8 bits: 00100010 = 34. Checksum = −34 mod 256 = 222 = 11011110 (inverte os 8 bits e soma 1). Receptor: (802+222) mod 256 = 0. Isso é complemento de 2; não misture com o checksum Internet em complemento de 1.
7.7. CRC — divisão binária com XOR
CRC normalmente significa Cyclic Redundancy Check, ou verificação de redundância cíclica. O slide usa o título “Ciclic Redundant Code”. A ideia é tratar os bits como coeficientes de um polinômio e calcular o resto da divisão por um gerador combinado entre emissor e receptor.
Exemplo: o gerador 1011 representa x³ + x + 1: o primeiro bit é o coeficiente de x³, o segundo de x², o terceiro de x e o último do termo constante. Seu grau é 3, então o resto ocupa três bits.
Para fazer a conta binária não é necessário desenvolver os polinômios. Na aritmética módulo 2, a subtração é XOR (⊕), sem empréstimo e sem “vai um”:
| Operação | Resultado |
|---|---|
| 0 ⊕ 0 | 0 |
| 0 ⊕ 1 | 1 |
| 1 ⊕ 0 | 1 |
| 1 ⊕ 1 | 0 |
Exemplo completo — dados 1101, gerador 1011
- Reserve espaço: como o gerador tem grau 3, acrescente três zeros: 1101 → 1101000.
- Divida por XOR: alinhe o primeiro 1 do gerador com o primeiro 1 do restante atual e aplique XOR. Repita enquanto o restante tiver grau pelo menos 3.
- Escreva o resto com três bits, inclusive zeros à esquerda.
- Envie os dados originais seguidos do resto, substituindo os zeros reservados.
| Passo | Restante atual | Gerador alinhado | Resultado do XOR |
|---|---|---|---|
| 1 | 1101000 | 1011000 | 0110000 |
| 2 | 0110000 | 0101100 | 0011100 |
| 3 | 0011100 | 0010110 | 0001010 |
| 4 | 0001010 | 0001011 | 0000001 |
O resto é 001. Portanto, transmite-se 1101 001: quatro bits de dados e três de CRC. Os zeros extras serviram apenas para reservar espaço no cálculo; não se envia 1101000 seguido de mais três bits.
Como o receptor verifica?
Neste modelo didático, divide-se o conjunto recebido 1101001 pelo mesmo gerador 1011, sem acrescentar novos zeros. O resto é zero: 1101001 ⊕ 1011000 = 0110001; depois ⊕ 0101100 = 0011101; depois ⊕ 0010110 = 0001011; finalmente ⊕ 0001011 = 0000000.
- Resto diferente de zero: erro detectado.
- Resto zero: nenhum erro detectado, não uma garantia absoluta de correção.
Exemplo de erro detectado: se apenas o último bit inverter, chega 1101000. A primeira divisão da tabela já mostra que seu resto é 001, diferente de zero.
Capacidade e limites do CRC
Uma rajada de erro vai do primeiro ao último bit invertido; os bits entre eles não precisam estar todos errados. Um CRC de grau r, com gerador de termo constante 1, detecta todas as rajadas de comprimento até r bits. Assim, o gerador deste exemplo detecta todas as rajadas de até três bits.
Há padrões não detectáveis: se o polinômio das inversões for múltiplo do gerador, a divisão continuará com resto zero. Outras garantias dependem do gerador e do comprimento da mensagem.
- Grau não é quantidade de bits do gerador: 1011 tem quatro bits, grau 3 e produz três bits de CRC.
- XOR não é soma binária comum: 1 ⊕ 1 = 0, sem carry.
- CRC não corrige automaticamente os dados e não protege contra adulteração intencional.
- A Ethernet usa CRC-32 no FCS, com parâmetros adicionais, como inicialização, reflexão e XOR final. A regra de resto zero acima descreve a divisão didática, não todos os parâmetros do CRC Ethernet.
Tópicos da aula 13, p. 2–7; explicações passo a passo, exemplos adicionais e limites de detecção: complementos didáticos. Nomenclatura das paridades mantida conforme este resumo.
Hamming [7,4]
- Separe a mensagem em nibbles (8 bits → 2 blocos: o alto e depois o baixo).
- p1 = d1⊕d2⊕d4 · p2 = d1⊕d3⊕d4 · p3 = d2⊕d3⊕d4.
- Monte p1 p2 d1 p3 d2 d3 d4.
- Numere os bits recebidos de 1 a 7.
- s1 = b1⊕b3⊕b5⊕b7 · s2 = b2⊕b3⊕b6⊕b7 · s3 = b4⊕b5⊕b6⊕b7.
- Síndrome s3s2s1 em binário = posição do erro (000 = sem erro).
- Inverta o bit dessa posição.
- Extraia os dados das posições 3, 5, 6 e 7.
- Mostre cada XOR: só a palavra final não explica o procedimento.
- Posições 1, 2 e 4 são paridades: se o erro é nelas, os dados já estavam certos.
- Hamming [7,4] corrige até um erro por palavra. Com dois erros, a síndrome pode levar a uma correção errada; 000 significa palavra válida, não prova absoluta de ausência de erros. As resoluções adotam o limite de um erro.
Hamming — quais posições cada paridade verifica?
Exemplo: codificar e decodificar 0101 1100 (2015 Q5)
8. Controle de fluxo — janelas deslizantes
| Volta-N (Go-Back-N) | Repetição Seletiva | |
|---|---|---|
| Erro na mensagem k | Retransmite k e todas depois de k dentro da janela | Retransmite somente k |
| Resposta | Um NACK obriga a repetir tudo depois do 1º erro | Um NACK para cada mensagem com erro |
| Ideal para | Redes com poucos erros | Redes com muitos erros |
| Janela máxima (n bits de seq) | 2n − 1 | 2n−1 |
Slide 14-Controle de Fluxo, p. 3–10. Janela máxima: convenção padrão ⚠ (não está nos slides).
Por que a janela máxima? (2015 Q1) Com 4 bits e W=16, o emissor envia seqs 0…15. Se todos chegam mas as confirmações se perdem, o receptor já espera 0; retransmitir o quadro antigo 0 é indistinguível de um novo 0. Se nada chegou, o emissor também observa ausência de confirmação. Com W=15 no Volta-N, o receptor que aceitou 0…14 espera 15 e pode reconhecer o 0 repetido como antigo: sobra um valor para separar os estados. Na Repetição Seletiva, janelas de quadros antigos e novos não podem se sobrepor: limite 8.
Mesmo erro, retransmissões diferentes
Quando o número de sequência dá a volta
- Liste as mensagens 1..N com o seq de cada uma: seq = (m − 1) mod 2bits.
- Marque com ✗ quais erram e em qual tentativa (regra geral + regra especial).
- Anote quando a janela muda: “após a aceitação da k-ésima” → vale na rodada seguinte.
- Rodada: envie a janela inteira (Volta-N) ou só as ainda não aceitas (Rep. Seletiva).
- Receptor: Volta-N aceita até o 1º erro e descarta o resto; Rep. Seletiva aceita/bufferiza as corretas.
- Resposta: Volta-N → NACK do seq com erro (ou ACK do último). Rep. Seletiva → ACK da última aceita em ordem + NACK de cada erro.
- Deslize a base para a 1ª mensagem ainda não aceita.
- Repita e, no fim, confira que todas foram aceitas em ordem.
- Nº da mensagem ≠ nº de sequência. Escreva os dois (“seq 5 (msg 14)”).
- A mudança de janela vale “após a aceitação”, não “após o envio”.
- “Retransmitida 4 vezes até chegar” = 4 tentativas com erro e a 5ª correta. A regra especial vence a regra geral.
- “Par começando pela mensagem de sequência 2” vale da 1ª mensagem com esse seq em diante, inclusive o seq 0 quando o contador estoura.
- O erro “na primeira transmissão” vale mesmo se o quadro seria descartado: no Volta-N, a 1ª transmissão pode ser um quadro que o receptor joga fora, e mesmo assim ele conta como a tentativa com erro.
- Se o desenho ficar enorme, use a tabela de rodadas como apoio para conferir cada seta e não se perder.
Exemplo resolvido: prova 2026 Q5 (Volta-N, 20 msgs, 4 bits, W 3 → 6 → 4)
9. Questão “rede completa” — receita mestre
- Montar as mensagens em uma tabela, campo a campo, na ordem do enunciado. Tamanho = nº de bytes de dados, em binário com o nº de bits do campo. Sequência = 0 para a 1ª mensagem de cada máquina. Endereços pela tabela do enunciado.
- Código verificador: horizontal = 1 bit logo após cada grupo; vertical = empilhe os grupos e calcule 1 bit por coluna (a palavra vai no campo indicado). Paridade par ou ímpar conforme o enunciado. Diga sobre quais campos calculou.
- Duplexação: quem fala em que tempo (TDD, ida/volta alternadas com guarda) ou em que faixa (FDD, faixa de ida e faixa de volta).
- Multiplexação: dentro de cada sentido, dê um slot (TDM) ou uma banda (FDM) a cada máquina, na ordem do enunciado. Slot vazio continua da máquina e é desenhado vazio.
- Codificação/modulação: corte cada mensagem em pedaços de N bits (o “bits por intervalo” do enunciado) e desenhe a onda daquele pedaço dentro do slot/banda correspondente.
- O tamanho é em bytes (16 bits de dados = 2 = 00010 em 5 bits), não em bits.
- Sequência começa em 0 por máquina: A e B mandam seq 0 na primeira mensagem.
- A paridade horizontal entra depois de cada grupo, então ela também vai para a linha e muda o nº de slots.
- Último slot incompleto: desenhe só os bits que existem (ou complete com repouso) e diga isso.
- Em códigos que dependem do nível anterior (NRZ-I, AMI, Manchester diferencial), a onda continua de um slot para o outro da mesma mensagem.
Exemplo completo — prova 2026 Q6 (3,0, obrigatória)
1. Montagem: o campo Destino/Origem identifica a máquina (A=0, B=1) nos dois sentidos, porque do outro lado só existe o servidor. 2. Verificador: paridade ímpar inserida após cada grupo de 4 bits.
3. Duplexação TDD: os intervalos alternam ida (A e B → S) e volta (S → A, S → B), com guarda entre eles. Começamos pela ida. 4. Multiplexação FDM: A usa a banda f1 e B a banda f2, nos dois sentidos. A volta de A (S→A) fica vazia porque S não responde a A, mas a banda continua sendo de A. 5. Modulação AM: 4 bits por intervalo (1 = amplitude alta, 0 = baixa). A ocupa 5 intervalos de ida (20 bits). B ocupa 8: são 30 bits, ou seja, 7 intervalos completos e o último com só 2 bits. S→B ocupa 5 intervalos de volta.
10. Controle de acesso ao meio (MAC)
- Aloha: a primeira rede sem fio do mundo, criada na Universidade do Havaí para interligar os campi. Transmite quando quer; se houver colisão, tenta de novo. Aloha discreto: as transmissões só começam no início de intervalos de tempo, o que reduz as colisões.
- CSMA (Carrier Sense Multiple Access): adaptação do Aloha discreto para o fio (barramento). A máquina ouve antes de transmitir: se o canal está ocupado, espera; se está livre, transmite.
- CSMA não persistente: com o canal ocupado, espera um tempo aleatório inteiro em (0, 2N − 1], onde N é a tentativa. Da 11ª à 15ª tentativa o intervalo fica limitado a (0, 1024]. Na 16ª, “pânico” (desiste).
| Tentativa N | 1 | 2 | 3 | 4 | … | 10 | 11–15 | 16 |
|---|---|---|---|---|---|---|---|---|
| Espera | (0,1] | (0,3] | (0,7] | (0,15] | … | (0,1023] | (0,1024] | PÂNICO |
- CSMA/CD (Collision Detection) — Ethernet compartilhada, half-duplex. Escuta enquanto transmite; se detectar colisão, interrompe e tenta novamente após espera aleatória. O quadro deve durar pelo menos a propagação de ida e volta na rede. Na Ethernet clássica, a janela de colisão é de 512 tempos de bit (64 bytes); uma rede dentro das especificações permite detectar a colisão nesse intervalo. Ethernet comutada full-duplex não usa CSMA/CD.
- CSMA/CA (Collision Avoidance) — WiFi. Escuta o canal e disputa o acesso com espera aleatória. No terminal oculto, A e C alcançam B, mas não se ouvem. A troca opcional RTS → CTS reserva o meio antes de dados → ACK; estações que ouvem a reserva adiam o envio. Reduz a chance e o custo de colisões, mas não garante que elas ocorram apenas em RTS/CTS.
- Passagem de bastão: como uma corrida de revezamento. Só quem está com o bastão transmite; se tudo funciona, não há colisão.
| CSMA/CD | CSMA/CA | |
|---|---|---|
| Onde | Ethernet (fio) | WiFi (802.11) |
| Ideia | Detecta a colisão enquanto transmite e para | Evita a colisão de dados reservando o canal (RTS/CTS) |
| Requisito | Transmitir e ouvir ao mesmo tempo | Não precisa ouvir enquanto transmite |
| Colisões | Detectáveis dentro da janela de colisão numa rede conforme as especificações | Ainda possíveis; RTS/CTS reduz a exposição dos dados |
| Custo | Quadro mínimo de 64 B; limite de propagação da rede | Espera aleatória, ACK e RTS/CTS quando habilitados |
| Problema resolvido | Não gasta o canal com quadros já colididos | Terminal oculto |
CSMA/CD — por que o quadro não pode acabar cedo?
CSMA/CA — terminal oculto e reserva do canal
Aloha puro × discreto — quando pode começar?
Passagem de bastão — acesso por vez
Slide 10-MAC, p. 3–43; slide 16-Ethernet (CSMA/CD em 4 etapas, quadro).
11. Ethernet, WiFi, Bluetooth e camadas
Modelo em camadas
| OSI | TCP/IP | Função (slide 1) |
|---|---|---|
| Aplicação | Aplicação | Os aplicativos do usuário |
| Apresentação | Interpreta as requisições das aplicações para as camadas inferiores | |
| Sessão | Separa os aplicativos dentro de uma máquina (ex.: portas do TCP) | |
| Transporte | Transporte | Origem-destino (TCP) |
| Rede | Rede | Endereçamento e roteamento (IP) |
| Enlace | Enlace | Comunicação entre duas máquinas conectadas. MAC (acesso ao meio) + LLC (enquadramento, sequencialização, detecção de erros, controle de fluxo) |
| Física | Física | Especificações físicas, ondas e sinais elétricos |
Ethernet (IEEE 802.3)
| Preâmbulo | SFD | DA | SA | Tamanho | Dados LLC | Preenchimento | FCS |
|---|---|---|---|---|---|---|---|
| 7 B (0s e 1s, sincronismo) | 1 B (início real) | 6 B destino | 6 B origem | 2 B (tamanho dos dados em octetos) | 0–1500 B | completa até o mínimo | 4 B (CRC-32 sobre tudo menos preâmbulo/SFD/FCS) |
- Menor quadro: 64 B (CSMA/CD). Maior: 1518 B = DA + SA + Tamanho + 1500 de dados + FCS (6 + 6 + 2 + 1500 + 4).
- Notação 10Base5 = 10 Mbps, banda base, segmentos de até 500 m; T = par trançado, F = fibra. Padrões: 802.2 LLC, 802.3 Ethernet, 802.11 WiFi, 802.15 WPAN.
- Hub: estrela física e barramento lógico; repete o sinal nas demais portas. Switch (camada 2): encaminha unicast conhecido à porta do destino; destino desconhecido e broadcast são difundidos. Store-and-forward recebe tudo e verifica o FCS antes de enviar. Cut-through começa após ler o destino: reduz a latência, mas pode propagar um quadro com erro. Ponte: interliga segmentos LAN na camada 2. Full-duplex: os dois sentidos operam simultaneamente em enlace ponto a ponto, sem CSMA/CD; não dobra a taxa de um único sentido.
- Endereço MAC de 48 bits: 24 bits do fabricante (OUI) + 24 bits da placa.
Quadro Ethernet — o que entra na contagem e no CRC?
Hub × switch — por onde vai o quadro?
Store-and-forward × cut-through — quando começa a saída?
WiFi (802.11)
- Com infraestrutura: as estações se associam ao ponto de acesso (AP), e a comunicação entre elas passa por ele; o SSID identifica a rede. Ad hoc: estações comunicam-se diretamente, sem AP. Encaminhar mensagens por vários nós exige roteamento; não é automático por ser ad hoc.
- A faixa de 2,4 GHz vai de 2,4 a 2,485 GHz, dividida em 11 (14) canais com sobreposição parcial. Os canais servem para separar redes/APs vizinhos e reduzir a interferência.
- MAC: CSMA/CA (DCF), com troca de 2 ou 4 quadros (dados + ACK, e RTS/CTS opcionais). Segurança: WEP, WPA, WPA2.
Infraestrutura × ad hoc
WiFi — sobreposição entre canais
Bluetooth (802.15)
- Curto alcance (10 m; novas versões até 100 m), em 2,4 GHz com salto de frequência contra interferência. Baixa complexidade, baixo consumo e baixo custo.
- Bluetooth clássico dos slides: piconet com 1 mestre + até 7 escravos ativos; o mestre coordena clock, saltos e turnos de acesso (TDMA). Scatternet: piconets interligadas por dispositivos que participam de mais de uma delas. Os slides citam 10 piconets/80 dispositivos e 79 frequências; os dois primeiros números não são limites universais de Bluetooth.
- Estados Standby e Connection. Modos de conexão: Active (transmite/recebe), Sniff (monitora), Hold (sem comunicação, economiza bateria) e Park (está na rede, mas não participa do tráfego).
Bluetooth clássico — piconet, scatternet e saltos
Slides 1-Modelo Camadas, 9-Enlace, 16-Ethernet, 17-WiFi, 18-Bluetooth.
12. Compressão LZW
- Escreva o dicionário inicial numerado.
- w = vazio. Para cada caractere c: se w+c está no dicionário, faça w = w+c.
- Se não está: emita o código de w, adicione w+c como nova entrada e faça w = c.
- No fim, emita o código de w.
- Leia o 1º código e escreva a sua string (ela vira “anterior”).
- Para cada código seguinte: se existe, a saída é a sua string. Se ainda não existe (caso especial), saída = anterior + 1º caractere do anterior.
- Nova entrada = anterior + 1º caractere da saída atual; anterior = saída.
- Na decodificação, a nova entrada é criada um passo atrasada em relação à codificação. Mostre a tabela com as duas colunas.
- Use ␣ para o espaço, senão o professor não sabe se você esqueceu dele.
Exemplo: “a arara arava” (2015 Q4)
13. “Consulta ao oráculo” / “cola” (bônus)
- Endereço de origem = o que o enunciado define (fileira/posição, por exemplo).
- Tamanho = quantidade de caracteres da mensagem (2017, regra 7), em binário se o campo pedir bits.
- Dados = a pergunta, com as 4 opções numeradas de 1 a 4.
- Formato Ethernet (2017): Preâmbulo / SFD / Destino / Origem / Tamanho / Dados (sem FCS: “não precisa usar detecção de erros”). Uma mensagem fora do formato é descartada pelo switch.
- Resposta: decodifique a palavra de 7 bits com a receita de Hamming da seção 7 e leia d1d2d3d4 em binário (1–4).
Palavras válidas para as respostas 1–4:
Exemplo de correção: recebido 1001011 (palavra 1000011 da resposta 3 com o bit 4 trocado):
14. Banco de provas — enunciados e resoluções
Os enunciados foram transcritos dos originais digitalizados. Quando o OCR estava corrompido, o valor foi lido na imagem. Cada resolução indica a receita usada e, nos pontos em que o enunciado é ambíguo, a interpretação adotada, que vale a pena escrever também na prova.
Prova 2010 — 2º semestre
Prova 2013 — 2º semestre (obrigatórias: 3 e 7)
Prova 2014 — 2º semestre, Prova B (obrigatórias: 3 e 7)
Prova 2015 — 2º semestre (obrigatórias: 3 e 8)
Prova 2016 — 2º semestre (obrigatórias: 2 e 5)
Prova Final 2016 — 2º semestre
Prova 2017 — 2º semestre (obrigatórias: 2 e 5)
Prova 2026 — 1º semestre (obrigatórias: 5 e 6; escolher itens até 10)
15. Checklist da véspera
Taxa
bps = bauds ÷ transições/bit (pior caso). NRZ, NRZ-I = 1. RZ, Manchester, Manchester diferencial, AMI = 2.Códigos (1 linha cada)
NRZ: 1 alto, 0 repouso.NRZ-I: 1 inverte, 0 mantém (começa no repouso).
RZ (bip.): 1 ↑, 0 ↓, volta ao 0 no meio.
Manchester: 1 ↑ no meio, 0 ↓ no meio.
Manchester dif.: sempre transição no meio; 0 = transição no início, 1 = sem.
AMI (bip.): 1 alterna +/− (1º +), 0 repouso.
Unipolares: NRZ, NRZ-I, MAN, MAND.
Modulação ⚠
AM: 1 alta/0 baixa. FM: 1 mais ciclos. PM: 1 = 180°. QAM-4: 00 45°, 01 135°, 11 225°, 10 315°. QAM-16: 2 bits de amplitude + 2 de fase (00 0°, 01 90°, 11 180°, 10 270°).Hamming [7,4] ⚠
p1 p2 d1 p3 d2 d3 d4, par.p1=d1⊕d2⊕d4 · p2=d1⊕d3⊕d4 · p3=d2⊕d3⊕d4.
s1=b1⊕b3⊕b5⊕b7 · s2=b2⊕b3⊕b6⊕b7 · s3=b4⊕b5⊕b6⊕b7 → s3s2s1 = posição.