Fano의 인코딩 상태가 고르지 않습니다. 우리는 컴퓨터 과학 통합 국가 시험을 준비하고 있습니다. 파노 상태. 이 작업을 수행하려면 Fano 조건, Huffman 코드를 알아야 합니다.
이 작업을 수행할 때 Fano 조건을 알아야 하며,허프만 코드
파노의 직접적 조건은 무엇을 의미하는가?
파노 조건 창시자인 이탈리아계 미국인 과학자 로버트 파노(Robert Fano)의 이름을 따서 명명되었습니다. 자기 종료 코드를 구성할 때 코딩 이론에서 조건이 필요합니다. 다른 용어가 주어지면 이러한 코드를 접두사 코드라고 합니다.
공식화하다 이 조건다음과 같이 할 수 있습니다: "어떤 코드워드도 다른 코드워드의 시작 역할을 할 수 없습니다. 코드워드 ».
수학적 관점에서 조건은 다음과 같이 공식화될 수 있습니다.코드에 B라는 단어가 포함되어 있으면 비어 있지 않은 C 줄에 대해 BC라는 단어가 코드에 존재하지 않습니다. ».
역 Fano 조건의 의미는 무엇입니까?
역 Fano 규칙도 있으며 그 공식은 다음과 같습니다.어떤 코드워드도 다른 코드워드의 끝 역할을 할 수 없습니다. ».
수학적 관점에서 역조건은 다음과 같이 공식화될 수 있습니다.코드에 B라는 단어가 포함되어 있으면 비어 있지 않은 문자열 C에 대해 CB라는 단어가 코드에 존재하지 않습니다. ».
작업: "A", "B", "C", "D", "E"라는 문자로 구성된 시퀀스가 제공됩니다. 주어진 시퀀스를 인코딩하려면 고르지 않은 바이너리 코드, 이를 통해 명확한 디코딩을 수행할 수 있습니다.
편지
이진 동등물
010
011
101
111
질문 : 기호 중 하나가 가능성을 보존하는 방식으로 코드워드의 길이를 줄이는 것이 가능합니까? 명확한 디코딩? 이 경우 나머지 기호의 코드는 변경되지 않고 그대로 유지되어야 합니다.
옵션 번호
답변
B–01
불가능해 보인다
C–01
D–01
해결책 : 디코딩 가능성을 보존하려면 직접 또는 역방향을 준수하는 것으로 충분합니다.파노 조건 . 옵션 1, 3, 4를 순차적으로 검사해 보겠습니다. 옵션 중 어느 것도 적합하지 않으면 정답은 옵션 2(불가능)가 됩니다.
옵션 1. 코드: A - 00, B - 01, C - 011, D - 101, E - 111. 직접파노 조건 실행되지 않음: 문자 "B"의 코드가 문자 "C"의 코드 시작 부분과 일치합니다. 역방향 Fano 규칙은 적용되지 않습니다. 문자 "B"의 코드는 문자 "D"의 코드 끝과 일치합니다. 옵션이 적합하지 않습니다.
옵션 3. 코드: A - 00, B - 010, C - 01, D - 101, E - 111. 직접파노 조건 실행되지 않음: 문자 "C"의 코드가 문자 "B"의 코드 시작 부분과 일치합니다. 반대의 조건도 만족되지 않습니다. 문자 "C"의 코드는 문자 "D"의 코드 끝과 일치합니다. 옵션이 적합하지 않습니다.
옵션 4. 코드: A - 00, B - 010, C - 011, D - 01, E - 111. 직접파노 조건 실행되지 않음: 문자 "D"의 코드가 문자 "B" 및 "C"의 코드 시작 부분과 일치합니다. 그러나 역방향 Fano 규칙이 준수됩니다. 문자 "D"의 코드는 다른 모든 문자의 코드 끝과 일치하지 않습니다. 이러한 이유로 옵션이 적합합니다.
직접 및 역순 준수 문제 해결 옵션을 확인한 후파노 조건 , 옵션 4가 올바른 것으로 확인되었습니다.
답변 : 4
허프만 코드
허프만 코딩의 기본 아이디어는 시퀀스에서 문자의 발생 빈도를 기반으로 합니다. 시퀀스에서 가장 자주 발생하는 기호는 매우 작은 새로운 코드를 수신하고, 가장 적게 발생하는 기호는 반대로 매우 작은 코드를 수신합니다. 긴 코드. 이는 우리가 모든 입력을 처리했을 때 가장 일반적인 문자가 가장 적은 공간을 차지하고(원래보다 적은) 가장 희귀한 문자가 가장 많은 공간을 차지하도록 하기 때문입니다. (그러나 드물기 때문에 중요하지 않습니다).
№ 1. 문자 O, B, D, P, A를 인코딩하기 위해 우리는 각각 숫자 0, 1, 2, 3, 4의 이진 표현을 사용하기로 결정했습니다(단일 문자의 경우 하나의 중요하지 않은 0을 보존함). 숫자 표현). 이런 식으로 일련의 문자 WATERFALL을 인코딩하고 그 결과를 적어보면 8진수 코드, 그러면 잘 될 거예요
1) 22162
2) 1020342
3) 2131453
4) 34017
설명.
먼저 숫자 조건의 데이터를 이진 코드로 표현해야 합니다.
100
그런 다음 일련의 문자 WATERFALL - 010010001110010을 인코딩합니다. 이제 이 표현을 오른쪽에서 왼쪽으로 세 쌍으로 나누고 결과 숫자 집합을 다음으로 변환해 보겠습니다. 십진수 코드, 그런 다음 8진수로 변환(8진수 표현은 삼중으로 나눌 때 10진수와 동일함)
010 010 001 110 010 - 22162.
№ 2. 문자 A, B, C 및 D로만 구성된 통신 채널을 통해 메시지를 전송하려면 A-00, B-11, B-010, D-011과 같은 문자별 코딩이 사용됩니다. 메시지는 통신 채널인 VBGAGV를 통해 전송됩니다. 이 코드로 메시지를 인코딩하세요. 받았다 이진수 16진수로 변환합니다.
1) CBDADC
2) 511110
3) 5B1A
4) A1B5
설명.
문자 시퀀스를 인코딩해 보겠습니다: VBGAGV - 0101101100011010. 이제 이 표현을 오른쪽에서 왼쪽으로 4개로 나누고 결과 숫자 집합을 먼저 10진수 코드로 변환한 다음 16진수로 변환해 보겠습니다.
0101 1011 0001 1010 - 5 11 1 10 - 5В1А.
정답은 3번에 표시되어 있어요
№ 3. 문자 A, B, C 및 D로만 구성된 메시지를 인코딩하려면 길이가 다른 이진 코드가 사용됩니다.
010
011
이러한 방식으로 VGAGBV 문자 시퀀스를 인코딩하고 결과를 기록하면 다음과 같은 결과를 얻을 수 있습니다.
1) CDADBC
2) A7C4
3) 412710
4) 4S7A
설명.
문자 시퀀스를 인코딩해 보겠습니다: VGAGBV - 0100110001111010. 이제 이 표현을 오른쪽에서 왼쪽으로 4개로 나누고 결과 숫자 집합을 먼저 10진수 코드로 변환한 다음 16진수로 변환해 보겠습니다.
0100 1100 0111 1010 - 4 12 7 10 - 4С7А.
정답은 4번에 기재되어 있습니다.
№ 4. 검정색과 흰색 래스터 이미지왼쪽부터 한 줄씩 인코딩됨 상단 모서리그리고 오른쪽 하단에서 끝납니다. 인코딩할 때 1은 검정색을 나타내고 0은 흰색을 나타냅니다.
간결성을 위해 결과는 다음과 같이 작성되었습니다. 8진법계산 선택하다 올바른 입력암호.
1) 57414
2) 53414
3) 53412
4) 53012
설명.
첫 번째 줄 코드: 10101.
두 번째 줄 코드: 11000.
세 번째 줄 코드: 01010.
한 줄에 순서대로 코드를 작성해 봅시다: 101011100001010. 이제 이 표현을 오른쪽에서 왼쪽으로 세 쌍으로 나누고 결과 숫자 세트를 10진수 코드( 8진수 표현세 쌍으로 나눌 때 십진수와 일치합니다).
101 011 100 001 010 - 53412.
№ 5. 5글자용 라틴 알파벳해당 이진 코드가 지정됩니다(일부 문자의 경우 - 2비트, 일부 - 3비트). 이 코드는 표에 나와 있습니다.
000
110
001
이진 문자열 1100000100110으로 인코딩된 문자 집합을 확인합니다.
1)바데
2) 바데
3)백데
4) BDB
설명.
Fano 조건이 충족된다는 것을 알 수 있습니다. 어떤 코드 단어도 다른 코드 단어의 시작이 아니므로 처음부터 메시지를 확실히 해독할 수 있습니다.
테이블 데이터에 따라 코드를 왼쪽에서 오른쪽으로 분할하고 문자로 변환해 보겠습니다.
110 000 01 001 10 - b a c d e.
정답은 3번에 기재되어 있습니다.
№ 6. 잡음이 많은 채널을 통해 숫자를 전송하려면 패리티 코드가 사용됩니다. 각 숫자는 다음과 같이 기록됩니다. 이진 표현, 길이 4에 선행 0이 추가되고 모듈로 2의 요소 합계가 결과 시퀀스에 추가됩니다(예를 들어 23을 전송하면 시퀀스 0010100110을 얻습니다). 01100010100100100110 형식으로 채널을 통해 전송된 번호를 확인하세요.
1) 6543
2) 62926
3) 62612
4) 3456
설명.
예제에서는 2개의 문자가 10개의 이진수(비트)로 인코딩되고 각 숫자에 5비트가 할당되는 것을 보여줍니다. 조건에 따르면 각 숫자는 4자 길이의 코드로 작성되므로 다섯 번째 숫자는 생략할 수 있습니다.
그것을 분해하자 이진 표기법 5개 문자 그룹으로 분류: 01100 01010 01001 00110. 각 5개 문자의 마지막 숫자를 버리고 이를 10진수 표기법으로 변환합니다.
0110 0101 0100 0011 - 6 5 4 3.
정답은 1번 아래에 나열되어 있습니다.
№ 7. 4개의 문자만 포함하는 메시지는 통신 채널(P, O, R, T)을 통해 전송됩니다. 문자를 인코딩하려면 5비트 코드 단어가 사용됩니다.
P-11111, O-11000, P-00100, T-00011.
이 코드워드 세트에는 다음과 같은 속성이 있습니다.세트에 있는 두 단어는 적어도 세 위치에서 다릅니다.
이 속성은 간섭이 있을 때 메시지를 해독하는 데 중요합니다(다음과 같다고 가정). 전송된 비트왜곡될 수 있지만 사라지지는 않습니다.) 인코딩된 메시지의 길이가 5의 배수이고 각 5분할이 일부 코드 단어와 한 위치 이상 다를 경우 올바르게 수신된 것으로 간주됩니다. 이 경우 5개는 해당 문자를 인코딩하는 것으로 믿어집니다. 예를 들어 5개의 00000이 수신되면 문자 P가 전송된 것으로 간주됩니다.
아래 메시지 중에서 올바르게 수신된 메시지를 찾아 디코딩을 표시하십시오(공백은 중요하지 않음).
11011 11100 00011 11000 01110
00111 11100 11110 11000 00000
1) 홍수
2) 로터
3) 도끼
4) 어떤 메시지도 제대로 수신되지 않았습니다
설명.
두 메시지의 길이는 5의 배수입니다.
첫 번째 메시지 “11011 11100 00011 11000 01110”을 분석해 보면, 한 위치에서만 “01110”이라는 단어와 다른 단어가 없기 때문에 잘못 수신되었다는 결론에 도달합니다.
두 번째 메시지를 살펴보겠습니다. 각각의 5개가 특정 코드워드와 한 위치만 다르다는 점을 고려하면 "AX"로만 해독될 수 있습니다.
№ 8. 5비트 코드는 통신 채널을 통해 데이터를 전송하는 데 사용됩니다. 메시지에는 다음 코드 단어로 인코딩된 문자 A, B 및 C만 포함되어 있습니다.
A - 10010, B - 11111, C - 00101.
전송 중에 간섭이 발생할 수 있습니다. 그러나 일부 오류를 수정해 볼 수는 있습니다. 이거 둘 중 아무거나 세 가지 코드단어는 적어도 세 가지 위치에서 서로 다릅니다. 따라서 단어를 전송할 때 최대 한 위치에서 오류가 발생하면 어떤 문자가 전송되었는지에 대해 교육적인 추측을 할 수 있습니다. (“코드가 하나의 오류를 정정한다”고 합니다.) 예를 들어 코드워드 00100이 수신되면 문자 B가 전송된 것으로 간주됩니다. (B에 대한 코드워드와의 차이점은 한 위치에만 있습니다. 다른 코드워드는 더 많은 차이가 있습니다.) 수신된 코드워드가 문자 A, B, C에 대한 코드워드와 두 위치 이상 다를 경우 오류가 발생한 것으로 간주됩니다. "엑스").
수신된 메시지 10000 10101 11001 10111. 이 메시지를 해독하세요 - 선택 올바른 옵션.
1) AVBB
2) XXXXXX
3) ABxB
4) 아흐B
설명.
우리는 메시지의 모든 단어를 해독합니다. 첫 번째 단어: 10000은 문자 A와 한 위치에서만 다릅니다. 두 번째 단어: 10101은 문자 B와 한 위치에서만 다릅니다. 세 번째 단어: 11001은 두 위치 이상의 문자와 다릅니다. 네 번째 단어: 10111은 문자 B와 한 위치에서만 다릅니다.
답: ABxB.
№ 9. 문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인코딩하기 위해 우리는 비균일 이진 코드를 사용하기로 결정했습니다. 이를 통해 통신 채널의 수신 측에 나타나는 이진 시퀀스를 명확하게 디코딩할 수 있습니다. 문자 A, B, C 및 D의 경우 A - 111, B - 110, C - 101, D - 100과 같은 코드 단어가 사용되었습니다.
아래 나열된 코드 단어 중 문자 D를 인코딩하는 데 사용할 수 있는 코드 단어를 표시하십시오. 코드는 명확한 디코딩 특성을 충족해야 합니다. 두 개 이상의 코드워드를 사용할 수 있는 경우 가장 짧은 코드워드를 입력하십시오.
1) 1
2) 0
3) 01
4) 10
설명.
길이가 일정하지 않은 코드를 사용하여 작성된 메시지를 명확하게 디코딩하려면 코드가 다른(더 긴) 코드의 시작이 되어서는 안 됩니다. 가장 짧은 것부터 시작하여 문자 D에 대한 옵션을 살펴보겠습니다.
1) D=1: 문자 코드 D는 표시되는 모든 문자 코드의 시작이므로 이 옵션은 적합하지 않습니다.
2) D=0: 문자 D에 대한 코드는 다른 코드의 시작이 아니므로 이 옵션이 적합합니다.
3) D=01: 문자 D에 대한 코드는 다른 코드의 시작이 아니므로 이 옵션이 적합합니다.
4) D=10: 문자 D에 대한 코드는 문자 B 및 G에 대한 코드의 시작이므로 이 옵션은 적합하지 않습니다.
따라서 0과 01의 두 가지 옵션이 적합합니다. 0은 01보다 짧습니다.
№ 10. 4개의 문자만 포함된 메시지는 통신 채널을 통해 전송됩니다.
E, N, O, T.
모든 메시지에서 가장 많은 문자는 O이고, 다음으로 가장 흔한 문자는 E, N입니다. 문자 T는 다른 문자보다 덜 일반적입니다.
메시지를 전송하려면 명확한 디코딩을 허용하는 균일하지 않은 이진 코드를 사용해야 합니다. 메시지는 가능한 한 짧아야 합니다. 암호 작성자는 아래 나열된 코드 중 하나를 사용할 수 있습니다. 그는 어떤 코드를 선택해야 할까요?
1) E−0, N−1, O−00, T−11
2) O−1, N−0, E−01, T−10
3) E−1, N−01, O−001, T−000
4) O−0, N−11, E−101, T−100
설명.
Fano 조건을 만족하는 코드를 선택해 보겠습니다. 코드 3과 4입니다.
메시지를 최대한 짧게 유지하려면 문자가 자주 나타날수록 코드도 짧아야 합니다.
따라서 대답은 4입니다. 문자 O가 가장 일반적인 문자이고 옵션 4는 이를 인코딩하는 데 하나의 문자를 사용하기 때문입니다.
№ 11. 문자 K, L, M, N으로 구성된 특정 시퀀스를 인코딩하기 위해 Fano 조건을 만족하는 비균일 이진 코드를 사용하기로 결정했습니다. 문자 H에는 코드 워드 0을 사용하고 문자 K에는 코드 워드 110을 사용했습니다. 4개 코드 워드의 가능한 가장 짧은 총 길이는 얼마입니까?
1) 7
2) 8
3) 9
4) 10
메모. Fano 조건은 코드워드가 다른 코드워드의 시작이 아님을 의미합니다. 이를 통해 암호화된 메시지를 명확하게 해독할 수 있습니다.
설명.
나머지 두 기호에 대해 Fano 조건을 만족하는 가장 짧은 표현을 찾아보겠습니다. 코드워드 1은 Fano 조건을 위반하므로 사용할 수 없습니다. 두 자리 코드워드 중 워드 10은 사용할 수 있지만, 워드 11과 01은 사용할 수 없습니다. 이러한 코드 구성으로는 네 번째 기호에 대한 두 자리 코드 워드를 선택하는 것이 불가능합니다. 따라서 우리는 111이라는 세 자리 단어를 사용합니다.
따라서 4개의 코드워드 모두의 가능한 가장 짧은 총 길이는 1 + 3 + 2 + 3 = 9가 됩니다.
정답은 3번에 기재되어 있습니다.
№12. 메시지는 통신 채널을 통해 전송되며 각 메시지에는 A 16개, B 8개, C 4개, G 4개가 포함되어 있습니다(메시지에 다른 문자는 없습니다). 각 문자는 이진 시퀀스로 인코딩됩니다. 코드를 선택할 때 두 가지 요구 사항이 고려되었습니다.
a) 하나의 코드 단어가 다른 코드 단어의 시작이 아닙니다(이는 코드가 명확한 디코딩을 허용하는 데 필요합니다).
b) 인코딩된 메시지의 전체 길이는 가능한 짧아야 합니다.
문자 A, B, C, D를 인코딩하려면 다음 중 어떤 코드를 선택해야 합니까?
1) A:0, B:10, C:110, D:111
2) A:0, B:10, C:01, D:11
3) A:1, B:01, C:011, D:001
4) A:00, B:01, C:10, D:11
설명.
2와 3은 코드 쌍을 포함하고 있기 때문에 적합하지 않습니다. 그 중 하나는 다른 것의 시작입니다.
첫 번째 코드를 사용할 때의 메시지 길이는 다음과 같습니다. .
네 번째 코드를 사용할 때의 메시지 길이는 다음과 같습니다. .
첫 번째 코드를 사용하면 메시지가 더 짧아지므로 이 코드를 사용해야 합니다.
자연스럽게 질문이 생깁니다. 디코딩이 항상 고유한 비균일 코드가 있습니까? 예, 존재합니다.
로버트 파노다음을 공식화했습니다. 충분조건코드에 명확한 디코딩이 있는지 확인합니다. 어떤 코드워드도 다른 코드워드의 시작이 아닙니다.이 조건이 충족되면 디코딩에 문제가 없습니다.
허락하다 A 1, A 2그리고 A 3- 일부 알파벳 위의 단어는 다음과 같습니다. A 1=2 3, 그건 A 1에서 얻은 A 2간단히 단어만 추가하면 A 3(단어 A 2또는 A 3단일 문자일 수 있음). 단어의 이름을 지정하자 A 2, 이는 단어의 첫 부분입니다. A 1, 접두사단어 A 1. 예를 들어, 단어의 경우 11101101 접두사는 단어가 될 것입니다 1110110 , 111011 , 11101 , 1110 , 111 , 11 , 1 .
그러면 코드에 대한 Fano 조건은 다음과 같이 공식화될 수 있습니다.
어떤 코드워드도 다른 코드워드의 접두어가 아닙니다..
Fano 조건을 만족하는 코드를 호출합니다. 접두사. 따라서 코드 앞에 접두사가 있으면 명확한 디코딩이 가능합니다.
예를 들어, 코드워드로 구성된 코드 {0, 10, 11} 는 접두사이며 다음 코드 시퀀스입니다. 01001101110 유일한 방법으로 코드 단어로 나눌 수 있습니다. 0 10 0 11 0 11 10 .
코드워드로 구성된 코드 {0, 10, 11, 100} 는 접두사가 아니며 명확한 디코딩을 허용하지 않습니다. 실제로 동일한 시퀀스를 코드 단어로 나눌 수 있습니다. 다른 방법들: 0 10 0 11 0 11 10 또는 0 100 11 0 11 10 .
Fano 조건은 코드에 대한 명확한 디코딩을 위한 충분조건일 뿐 필수조건은 아니라는 점에 유의하는 것이 중요합니다.
예를 들어, 두 개의 코드워드만으로 구성된 간단한 코드 {1, 10} 는 분명히 접두사는 아니지만 이 코드로 인코딩하여 얻은 모든 코드 시퀀스를 명확하게 디코딩합니다. 실제로 이러한 순서에서는 두 개의 0이 나란히 나타날 수 없습니다. 그런 다음 각 0을 두 번째 코드 단어의 역 이미지로 앞의 단위로 바꾸고 나머지 모든 것을 첫 번째 단어의 역 이미지로 대체하면 이는 명확한 디코딩이 됩니다.
다른 것들도 있고 그 이하도 있어요 간단한 코드, 동일한 속성을 가지고 있습니다. 예를 들어, 코드 {01,10,011} 또한 접두사가 붙지 않지만 명확한 디코딩이 있습니다(직접 증명해 보세요).
Fano 조건이 만족되지 않으면 코드가 고유하게 디코딩 가능한지 어떻게 확인할 수 있습니까? 다음 방법을 사용할 수 있습니다.
말을 하자 A 2~이다 접두사단어 A 1. 그 다음에 A 1=2 3, 어디 A 3어떤 단어, 단어의 마지막 부분 A 1. 전화하자 3 접미사몇 마디 A 1그리고 A 2, 그 중 하나는 다른 하나의 접두사이고 쌍 자체는 A 1그리고 A 2전화하자 접두사.
주어진 코드에서 코드워드의 모든 접두어 쌍을 고려하고 이들로부터 모든 접미어 세트를 구성해 보겠습니다. 다음으로 우리는 모든 접두사 쌍을 고려합니다. 그 중 하나는 코드 단어이고 다른 하나는 접미사이며, 접미사 세트를 확장하여 접미사를 구성합니다. 새로운 접미사가 더 이상 나타나지 않을 때까지 이 과정을 계속하겠습니다. 코드워드와 일치하는 접미사가 없는 경우에만 코드를 고유하게 디코딩할 수 있습니다.
예를 들어, 코드의 경우 {01,10,011} 많은 접미사가있을 것입니다 {1,0,11} . 여기에 있는 단일 접미사는 코드 단어와 일치하지 않으므로 이 코드는 고유하게 디코딩 가능하다고 주장할 수 있습니다.
작업 1.다음 코드가 고유한 디코딩 속성을 가지고 있는지 확인합니다. a) {110, 11, 100, 00, 10} 비) {100, 001, 101, 1101, 11011} .
접두사가 아닌 코드로 얻은 디코딩 시퀀스는 접두사 코드보다 더 복잡한 분석이 필요합니다. 접두사 코드가끔 불린다 즉각적인(즉시 디코딩 가능) 왜냐하면 코드 시퀀스를 읽을 때 단어의 마지막 기호에 도달하면 코드 단어의 끝이 즉시 인식되기 때문입니다. 이것이 접두사 코드의 장점입니다.
다른 코드 테이블을 고려해 보겠습니다. A B C D D 000 01 10 011 100 여기서 Fano 조건은 만족되지 않습니다. 왜냐하면 문자 B(01)의 코드는 문자 G(011) 코드의 시작이고 문자 코드는 D(100)는 문자 B(10)의 코드로 시작됩니다. 그러나 "역" Fano 조건이 충족된다는 점을 알 수 있습니다. 즉, 어떤 코드도 다른 코드의 끝이 아닙니다(이러한 코드를 postfix라고 함). 따라서 인코딩된 메시지는 끝에서부터 명확하게 디코딩될 수 있습니다. 예를 들어 체인 011000110110을 생각해 보세요. 마지막 편지이 메시지에는 B(코드 10)만 있을 수 있습니다: B 0110001101 10 끝에서 두 번째 문자는 B(코드 01): B B 01100011 01 10 등입니다: B D G B B 01 100 011 01 10.
슬라이드 26프레젠테이션에서 "정보 인코딩 방법". 프레젠테이션이 포함된 아카이브의 크기는 734KB입니다.코딩 방법
다른 프레젠테이션 요약"이진 코딩" - 숫자. 바이너리 코딩 텍스트 정보. 인코딩 테이블. 텍스트의 정보량. 컴퓨터의 이진 코딩. 텍스트 정보의 코딩. 확장된 코드 테이블. 상징. 고유한 바이너리 코드입니다. 라틴 알파벳의 편지. 바이너리 시스템을 사용합니다. 컴퓨터.
"이진 코드로 정보 인코딩" - 정의. 숫자 체계. 바이너리 시스템계산 코딩. 정보의 인코딩. 코딩 예시를 들어보세요. 십진법계산 숫자의 의미. 숫자의 의미는 위치에 따라 다릅니다. 알파벳. 언어. 로마 인 비 위치 시스템. 바이너리 코딩. 여기서 암호화된 내용은 무엇입니까?
"코딩 방법" - 열 번호입니다. 편지 소스 텍스트. 정보의 인코딩. 정보 인코딩 방법. 정보를 디코딩합니다. 전송된 정보. 코드의 세계에서. 자동 코딩. 좌표 방법. 장점과 단점. 다양한 코드. 소년. 무엇을 부를 수 있나요? 공책정보 저장 측면에서. 인코딩된 텍스트. 정보매체. 키워드. 퍼즐을 풀어보세요.
"정보 인코딩 방법" - 컴퓨터 메모리에서 정보는 이진 코드로 표시됩니다. 인코딩 및 디코딩. 정보를 인코딩할 수 있습니다. 정보 인코딩 방법. 간단한 코드 테이블을 만들어 보겠습니다. 암호화된 단어를 찾으려면 첫 음절만 취하세요. 다가오는 스쿠너의 깃발에서 Lom이 읽은 것. 생각해 내다 나만의 방식러시아 알파벳의 문자 코딩. 작업. 암호화된 정보. 루이 점자 발명 특별한 방법정보 제시.
"정보 인코딩 방법" - 컴퓨터의 이진 코딩. 정보의 양. Shapp 광학 전신. 파노 상태. 사용할 코드. 메시지 받음. "예 혹은 아니오". 최초의 전신. 정보 인코딩 방법. 녹음 정보. 왜 바이너리 코딩. 신호 플래그. 코딩. 인코딩 및 디코딩. 정보의 인코딩. 인코딩 방법을 선택합니다. 정보 유형. 옵션은 몇 개인가요?
안녕하세요! 제 이름은 Alexander Georgievich이고 컴퓨터 과학 및 프로그래밍 분야의 모스크바 전문 교사입니다. 코딩과 관련된 문제를 접하셨는데, 이를 해결하기 위한 알고리즘이 혼란스러우신가요? 급하게 만나야 하는 사람파노 조건, 그리고 저와 함께 개인 레슨도 신청하세요. 수업에서는 간단하고 복잡한 주제별 연습 문제를 해결하는 데 중점을 둡니다.
파노의 직접적 조건은 무엇을 의미하는가?
파노 조건창시자인 이탈리아계 미국인 과학자 로버트 파노(Robert Fano)의 이름을 따서 명명되었습니다. 자기 종료 코드를 구성할 때 코딩 이론에서 조건이 필요합니다. 다른 용어가 주어지면 이러한 코드를 접두사 코드라고 합니다.
이 조건은 다음과 같이 공식화될 수 있습니다. 어떤 코드워드도 다른 코드워드의 시작 역할을 할 수 없습니다.».
수학적 관점에서 조건은 다음과 같이 공식화될 수 있습니다. 코드에 다음 단어가 포함된 경우B, 비어 있지 않은 문자열의 경우C 단어 BC가 코드에 존재하지 않습니다.».
역 Fano 조건의 의미는 무엇입니까?
역 Fano 규칙도 있으며 그 공식은 다음과 같습니다. 어떤 코드워드도 다른 코드워드의 끝 역할을 할 수 없습니다.».
수학적 관점에서 역조건은 다음과 같이 공식화될 수 있습니다. 코드에 B라는 단어가 포함되어 있으면 비어 있지 않은 문자열 C에 대해 CB라는 단어가 코드에 존재하지 않습니다.».
Fano 조건의 실제 적용
고려해 봅시다 전화 번호 V 기존 전화 통신. 번호 "102"가 이미 존재하는 경우 "1029876" 번호는 발급되지 않습니다. 처음 세 자리 숫자로 전화를 걸면 PBX는 다른 모든 숫자 인식 및 수신을 중지하고 번호 102로 가입자에게 연결됩니다. 그러나 이 규칙은 운영자에게 유효하지 않습니다. 이동통신. 이는 번호를 누르려면 해당 키(주로 녹색 이미지가 있는 키)를 눌러야 하기 때문입니다. 휴대폰. 이러한 이유로 "102", "1020" 및 "1029876"이라는 숫자가 존재하고 다른 수신자에게 할당될 수 있습니다.
작업:문자 "A", "B", "C", "D" 및 "E"로 구성된 시퀀스가 제공됩니다. 주어진 시퀀스를 인코딩하기 위해 균일하지 않은 이진 코드가 사용되며 이를 통해 명확한 디코딩을 수행할 수 있습니다.
질문: 명확한 디코딩 가능성을 보존하는 방식으로 심볼 중 하나가 코드워드의 길이를 줄이는 것이 가능합니까? 이 경우 나머지 기호의 코드는 변경되지 않고 그대로 유지되어야 합니다.
해결책: 디코딩 가능성을 보존하려면 직접 또는 역방향을 준수하는 것으로 충분합니다.파노 조건. 옵션 1, 3, 4를 순차적으로 검사해 보겠습니다. 옵션 중 어느 것도 적합하지 않으면 정답은 옵션 2(불가능)가 됩니다.
옵션 1. 코드: A - 00, B - 01, C - 011, D - 101, E - 111. 직접 파노 조건실행되지 않음: 문자 "B"의 코드가 문자 "C"의 코드 시작 부분과 일치합니다. 역방향 Fano 규칙은 적용되지 않습니다. 문자 "B"의 코드는 문자 "D"의 코드 끝과 일치합니다. 옵션이 적합하지 않습니다.
옵션 3. 코드: A - 00, B - 010, C - 01, D - 101, E - 111. 직접 파노 조건실행되지 않음: 문자 "C"의 코드가 문자 "B"의 코드 시작 부분과 일치합니다. 반대의 조건도 만족되지 않습니다. 문자 "C"의 코드는 문자 "D"의 코드 끝과 일치합니다. 옵션이 적합하지 않습니다.
옵션 4. 코드: A - 00, B - 010, C - 011, D - 01, E - 111. 직접 파노 조건실행되지 않음: 문자 "D"의 코드가 문자 "B" 및 "C"의 코드 시작 부분과 일치합니다. 그러나 역방향 Fano 규칙이 준수됩니다. 문자 "D"의 코드는 다른 모든 문자의 코드 끝과 일치하지 않습니다. 이러한 이유로 옵션이 적합합니다.
직접 및 역순 준수 문제 해결 옵션을 확인한 후 파노 조건, 옵션 4가 올바른 것으로 확인되었습니다.
답변: 4
이제 컴퓨터 과학 및 ICT 통합 상태 시험 데모 버전에서 제안된 문제에 대한 멀티미디어 솔루션을 숙지하시기 바랍니다. 그런데, 이 작업사용하여 해결되는 문제 유형을 나타냅니다. 파노 조건.
아직도 질문이 있으신가요?
이 간행물을 읽은 후에도 여전히 몇 가지 질문이나 오해가 있거나, 다룬 내용을 통합하고 싶다면 실용적인 솔루션, 그런 다음 저에게 전화하여 컴퓨터 과학 및 ICT 개인 수업에 등록하세요.
사용 시사프리젠테이션을 통해 계정을 직접 만드세요( 계정) Google을 검색하고 로그인하세요: https://accounts.google.com
슬라이드 캡션:
명확한 디코딩 직접 및 역 조건 Fano 컴퓨터 과학 및 ICT 교사 MBOU 중등 학교 No. 7 Okha, Sakhalin 지역 Sergienko Tatyana Gennadievna
작업 1 "Good morning"이라는 문구를 인코딩하기 위해 다음 코드를 선택하겠습니다. GOODBREUT Space 111 000 00 1 01 0 10 11
문자 코드는 단일 비트 문자열로 "연결"되어 네트워크를 통해 전송됩니다. 예를 들어 좋은 아침 → 11100000100001110101000 대상에서 원본 메시지를 복원하는 방법과 이것이 가능한지 여부에 대한 문제가 발생합니다.
11100000100001110101000 디코드 이 메시지다양한 방법으로 가능합니다. 또한 문자 P – 1과 U – 0으로만 구성되어 있다고 가정합니다. 그런 다음 RRRUUUUURUUURRRURRUUU를 얻습니다. 즉, 의미 없는 글자 모음.
코드 메시지를 해독할 수 있는 경우 해당 코드를 고유하게 디코딩 가능하다고 합니다. 유일한 방법(분명히).
이는 코드가 고유하게 디코딩될 수 없음을 의미합니다.
작업 2 통일 코드. 동일한 문구에 대해 통일 코드를 사용합니다: D O R E U T Space 111 000 001 101 011 010 100 110
균일한 코드는 비균일한 코드보다 훨씬 길기 때문에 비경제적입니다. 이로 인해 코딩이 더 복잡해지지만 동시에 명확하게 디코딩되므로 작업이 자연스럽게 쉬워집니다.
작업 3 메시지 길이를 줄이려면 비균일 코드를 사용해 보세요. 코드 단어가 해당하는 코드 다른 문자소스 알파벳은 한 문자에서 여러 문자까지 길이가 다를 수 있습니다.
우리는 사용 다음 코드: 01이 비트열은 고유하게 디코딩됩니다. D O R E U T 스페이스 01 00 1011 100 1010 1101 1110 1111
첫 번째 문자는 D(코드 01)입니다. 01로 시작하는 다른 코드 단어는 없습니다. 두 번째 문자는 O(코드 00)입니다. 00으로 시작하는 다른 단어는 없습니다. Fano 조건이라고 하는 이 동일한 속성은 다른 문자의 코드워드에도 적용됩니다.
FANO 조건 다른 코드워드의 시작과 일치하는 코드워드가 없습니다. 이러한 코드를 접두사(메시지 시작 부분부터 디코딩됨)라고 하며 고유하게 디코딩됩니다.
작업 4 코드를 하나 더 생각해 보겠습니다. 접두사가 아닙니다. 문자 D(10)의 코드는 문자 B(1011), U(1000)의 코드 시작 부분과 일치하고 문자 O(00)의 코드는 문자 P( 001). D O R E U T 스페이스 10 00 1011 001 0101 1000 0111 1111
메시지를 인코딩해 보겠습니다. GOOD MORNING → 10 00 1011 001 00 0101 1111 1000 0111 001 00 처음부터 디코딩을 시작하겠습니다. 첫 번째는 D 또는 U이고 그 다음은 일반적으로 진행됩니다. 다양한 변형: P 또는 B... 즉 앞을 “보아야” 하는데, 이는 매우 불편합니다.
마지막부터 메시지를 해독해 봅시다. 확실히 해독되었습니다! 역 Fano 조건이 충족됩니다. 즉, 다른 코드워드의 끝과 일치하는 코드워드가 없습니다.
역 Fano 조건을 만족하는 코드를 postfix라고 합니다.
결론을 내리자면: 사용된 코드에 대해 직접 또는 역 Fano 조건이 만족되면 메시지가 고유하게 디코딩됩니다.
Fano 조건은 충분하지만 충분하지 않습니다. 필요한 조건명확한 디코딩 가능성 이는 다음을 의미합니다. - 명확한 디코딩 가능성의 경우 직접 또는 역의 두 가지 조건 중 적어도 하나를 충족하는 것으로 충분합니다. - 직접 또는 역 Fano 조건이 모두 충족되지 않지만 그럼에도 불구하고 명확한 디코딩을 제공하는 코드가 있을 수 있습니다. 그렇지 않으면 표현의 의미가 상실됩니다.
작업 5 문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인코딩하려면 균일하지 않은 이진 코드가 사용되므로 결과 이진 시퀀스를 명확하게 디코딩할 수 있습니다. 코드는 다음과 같습니다: A – 00, B – 01, C – 100, D – 101, D – 110.
코드를 여전히 명확하게 해독할 수 있도록 문자 중 하나에 대한 코드 단어의 길이를 줄이는 것이 가능합니까? 나머지 문자의 코드는 변경되어서는 안됩니다. 정답을 선택하세요: 1) 문자 D -11의 경우 2) 불가능합니다 3) 문자 G - 10의 경우 4) 문자 D -10의 경우
해결책: 원천– 접두사. 이를 위해 Fano 조건이 충족됩니다. 즉, 3비트 코드 중 어느 것도 00(A) 또는 01(B)로 시작하지 않습니다. (이 경우 역파노 조건이 만족되지 않습니다. 코드 A(00)는 엔딩 B(100)와 일치하고, 코드 B(01)는 엔딩 D(101)와 일치합니다.)
이제 답변을 확인해 보겠습니다. D를 11로 줄여보겠습니다. 결과 코드가 위반하는 경우 직접적인 상태 Fano, 그러면 명확한 디코딩 속성이 위반됩니다. 하지만 이런 일은 일어나지 않았습니다. 11로 시작하는 다른 코드는 없습니다. 올바른 결정. 다른 옵션을 확인해 보겠습니다.
우리는 옵션 2를 즉시 고려하지 않습니다. 답을 찾았습니다. 옵션 3은 Fano의 직접 조건을 위반합니다. 문자 B(101)의 코드는 10으로 시작합니다. 옵션 4도 Fano의 직접적인 조건을 위반합니다. 저것들. 대답은 분명합니다. 다른 옵션은 없습니다.
관심을 가져주셔서 감사합니다!