Кодирование информации
Разработка предназначена учителю информатики при прохождении темы "Кодирование информации". В ней рассматриваются примеры кодирования текстовой информации с использованием равномерных и неравномерных кодов. Кодирование используется в различных сферах деятельности человека, и если человек знаком с основными положениями даже школьной теории кодирования, то он сможет применить эти знания на практике, а ученик сможет решать задачи, связанные с кодированием текстовой информации.
Человек способен не только воспринимать, но и видоизменять информацию, если ему это необходимо для каких-то целей. Поэтому существует текстовая, числовая, графическая и звуковая информация. Для представления текстовой и числовой информации обычно используются алфавиты, то есть наборы символов, с помощью которых составляются тексты. Текст – это некоторая последовательность, составленная из символов алфавита. Для общения между людьми тексты должны осмысленными, они должны что-то сообщать, то есть люди должны понимать тексты. Однако бывают ситуации, когда осмысленные тексты должны быть преобразованы в неосмысленные. Например, когда требуется передать конфиденциальную информацию, ее преобразуют, используя так называемые шифры, то есть правила преобразования текста. Самый простой шифр может быть получен обычной заменой символов сообщения, полученного с помощью алфавита А, на символы алфавита В. Например, возьмем слово «танк». Это слово из русского алфавита. Заменим четыре русские буквы четырьмя символами алфавита В={&*+/} следующим образом: «т» - на «+», «а» - на «/», «н» - на «*», «к» - на «&». Новое зашифрованное слово будет выглядеть как «+/*&». Это слово для русского языка не имеет смысла. Однако это слово может быть легко преобразовано в слово «танк», если будет известно правило обратного преобразования, то есть, «+» - на «т», «/» - на «а», «*» - на «н», «*» - на «к». Не всегда из правила прямого преобразования текста можно получить правило для обратного преобразования текста. Например, если бы правило прямого преобразования осуществляло замену двух различных символов русского языка одним символом нового алфавита, например, «т» и «к» на «+», то мы столкнулись бы с трудностью для правила обратного преобразования, а именно на какую букву заменять символ «+». Это происходит потому, что в первом случае правило прямого преобразования текста осуществляет взаимно однозначное соответствие между четырьмя символами первого и четырьмя символами другого алфавита, а во втором случае – нет.
Правило взаимно однозначного соответствия (замены) символов одного алфавита символам другого алфавита называют кодом (замена «+» - на «т», «/» - на «а», «*» - на «н», «*» - на «к» - это код), а процесс замены символов исходного текста на новые символы – кодированием. Процесс, обратный кодированию называют декодированием. Кодирование является одним их простейших способов шифрования текста.
Рассмотрим возможные способы кодирования.
1. В качестве алфавита А возьмем четыре символа , например, «а», «б», «р», «г», в качестве алфавита В - один символ. Пусть это «1». В качестве кода можно выбрать следующее соответствие - а – 1, б – 11, р – 111, г – 1111 и ему подобные, при этом в качестве кода какого-либо символа может любое конечное число единиц. Количество единиц, соответствующее тому или иному символу алфавита А назовем длиной кода этого символа. Если закодировать выбранным кодом слово «багр», то получим 1111111111. Декодировать такой текст не представляется возможным в силу того, что неясно, какая единица является концом того или иного кода. То же самое произойдет, если вместо единицы выбрать любой другой символ. Следовательно, алфавит, состоящий из одного символа, не может быть выбран в качестве алфавита В для формирования кода.
2. В качестве алфавита А возьмем те же четыре символа «а», «б», «р», «г», в качестве алфавита В - два символа, например, «0» и «1». В качестве кода можно выбрать следующее соответствие - а – 10, б – 110, р – 1110, г – 11110. Если закодировать подобным кодом слово «багр», то получим 11010111101110. Данное слово уже можно декодировать. Здесь в качестве кодов символов алфавита А выбраны коды, имеющие разную длину, поэтому выбранный код называют неравномерным.
3. В качестве алфавита А возьмем символы «а», «б», «р», «г», в качестве алфавита В - символы «0» и «1». В качестве кода можно выберем следующее соответствие - а – 00, б – 01, р – 10, г – 11. Если закодировать этим кодом слово «багр», то получим 01001110. Это слово также можно декодировать. Здесь в качестве кодов символов алфавита А выбраны последовательности символов из алфавита В, имеющие одинаковую длину, поэтому выбранный код называют равномерным.
Равномерные коды можно легко декодировать, разделяя текст на группы символов и заменяя группу символов на один символ исходного алфавита. В данном примере – по два символа в группе. Всего различных вариантов кода длины 2 будет 4! = 1*2*3*4 = 24.
Несомненно, что можно было выбрать коды и любой большей длины, например, а – 000, б – 101, р – 100, г – 111. Однако при этом закодированный текст имел бы большую длину. Чем длиннее текст, тем больше времени будет необходимо для его декодирования.
4. В качестве алфавита А возьмем символы «а», «б», «р», «г», в качестве алфавита В - три символа, например, «0», «1» и «2». В качестве кода можно выбрать одно из следующих соответствий
41. а – 00, б – 01, р – 02, г – 10
42. а – 00, б – 01, р – 02, г – 11
43.а – 00, б – 01, р – 02, г – 20
44.а – 00, б – 01, р – 02, г – 21
45.а – 00, б – 01, р – 02, г – 22
46.а – 01, б – 02, р – 12, г – 22
Можно продолжать и далее, так как это не все соответствия. Поскольку всего пар, которые можно составить из 3 символов – 9: (00), (01), (02), (10), (11), (12), (20), (21), (22), то всего вариантов выбора четырех пар из 9 будет число сочетаний из 9 по 4 и равно = 9!/(4!*5!)=126. Каждую из четырех выбранных из пар можно расставить 4!=24 способами для символов или «а», или «б», или «р», или «г». Например. Рассмотрим код 41. Из него можно получить код 410. а – 00, б – 01, р – 10, г – 02, 411. а – 00, б – 10, р – 01, г – 02 и т. д. Всего, таким образом, вариантов выбора всевозможных соответствий будет равно 126*24 = 3024. Если закодировать кодом 41 слово «багр», то получим 01001002. Это слово также можно декодировать.
5. В качестве алфавита А возьмем символы «а», «б», «в», «г», «д», «р», в качестве алфавита В - два символа, например, «0», «1». Если начать выбор кода таким же способом, как и для третьего способа, то есть а – 00, б – 01, в – 10, г – 11, д - , р – , то необходимо увеличить длину последовательности на 1 и тогда получим один из вариантов кода а – 000, б – 001, в – 010, г – 011, д - 100, р – 101. При этом останутся две невостребованные последовательности 110 и 111. Если бы в алфавите А было восемь символов, то все возможные последовательности из двух символов длины три были бы использованы. Таким образом, при использовании равномерных кодов между мощностью N алфавита А и мощностью М алфавита В существует связь N <= M^L, где L – длина последовательности, при этом L, M, N – натуральные числа (выражение M^L следует читать как M в степени L).
В третьем примере N = 4, M = 2 минимальная величина L = 2 и тогда 4 = 2 и тогда 4 = 2^2, в четвертом примере N = 4, M = 3, минимальная величина L = 2, 4 < 3^2. Если взять N = 4, M = 4, минимальная величина L = 1. Действительно, L = 1, так как этот случай рассмотрен в примере шифрования. Если взять значение N < M, то он сведется к случаю N = 4, M = 4. Какой-то один символ в алфавите В не придется использовать. Следовательно, должно выполняться условие N > = M. Чтобы подсчитать длину D закодированного текста (в символах алфавита В), необходимо знать величины N и M, длину исходного текста К (в символах алфавита А), затем из неравенства N <= M^L установить (можно подбором) минимальное значение L и произвести вычисления по формуле D = L*K.
Рассмотрим текст Хлеб – всему голова. В нем K = 20 символов. Алфавит A = {а б в г е л м о у Х - .} содержит 12 символов, то есть N = 12. Пусть В ={0 1} содержит два символа, то есть M = 2. Такой алфавит называют двоичным, а символы алфавита – двоичными. Рассмотрим неравенство 12 <= 2^L. Минимальное значение L = 4. D = 20*4 = 80 двоичных цифр (символов из алфавита В).
Таким образом, при кодировании текста используются равномерные или неравномерные коды. Равномерные коды необходимы для представления текстовой информации в двоичном виде в компьютере и сохранения ее в таком виде в памяти компьютера. Вполне естественно, что при этом значение величины L существенно влияет на объем сохраняемого текста. Неравномерные коды используются при передаче сообщений в сети, причем используются такие, которые позволяют обнаруживать и исправлять ошибки.
Что такое технология потоковых данных
Использование облачного хранилища данных в образовательном пространстве
Восьмеричный переход
Конспект урока информатики по теме «Разветвляющие алгоритмы», 10 класс
Человек способен не только воспринимать, но и видоизменять информацию, если ему это необходимо для каких-то целей. Поэтому существует текстовая, числовая, графическая и звуковая информация. Для представления текстовой и числовой информации обычно используются алфавиты, то есть наборы символов, с помощью которых составляются тексты. Текст – это некоторая последовательность, составленная из символов алфавита. Для общения между людьми тексты должны осмысленными, они должны что-то сообщать, то есть люди должны понимать тексты. Однако бывают ситуации, когда осмысленные тексты должны быть преобразованы в неосмысленные. Например, когда требуется передать конфиденциальную информацию, ее преобразуют, используя так называемые шифры, то есть правила преобразования текста. Самый простой шифр может быть получен обычной заменой символов сообщения, полученного с помощью алфавита А, на символы алфавита В. Например, возьмем слово «танк». Это слово из русского алфавита. Заменим четыре русские буквы четырьмя символами алфавита В={&*+/} следующим образом: «т» - на «+», «а» - на «/», «н» - на «*», «к» - на «&». Новое зашифрованное слово будет выглядеть как «+/*&». Это слово для русского языка не имеет смысла. Однако это слово может быть легко преобразовано в слово «танк», если будет известно правило обратного преобразования, то есть, «+» - на «т», «/» - на «а», «*» - на «н», «*» - на «к». Не всегда из правила прямого преобразования текста можно получить правило для обратного преобразования текста. Например, если бы правило прямого преобразования осуществляло замену двух различных символов русского языка одним символом нового алфавита, например, «т» и «к» на «+», то мы столкнулись бы с трудностью для правила обратного преобразования, а именно на какую букву заменять символ «+». Это происходит потому, что в первом случае правило прямого преобразования текста осуществляет взаимно однозначное соответствие между четырьмя символами первого и четырьмя символами другого алфавита, а во втором случае – нет.
Правило взаимно однозначного соответствия (замены) символов одного алфавита символам другого алфавита называют кодом (замена «+» - на «т», «/» - на «а», «*» - на «н», «*» - на «к» - это код), а процесс замены символов исходного текста на новые символы – кодированием. Процесс, обратный кодированию называют декодированием. Кодирование является одним их простейших способов шифрования текста.
Рассмотрим возможные способы кодирования.
1. В качестве алфавита А возьмем четыре символа , например, «а», «б», «р», «г», в качестве алфавита В - один символ. Пусть это «1». В качестве кода можно выбрать следующее соответствие - а – 1, б – 11, р – 111, г – 1111 и ему подобные, при этом в качестве кода какого-либо символа может любое конечное число единиц. Количество единиц, соответствующее тому или иному символу алфавита А назовем длиной кода этого символа. Если закодировать выбранным кодом слово «багр», то получим 1111111111. Декодировать такой текст не представляется возможным в силу того, что неясно, какая единица является концом того или иного кода. То же самое произойдет, если вместо единицы выбрать любой другой символ. Следовательно, алфавит, состоящий из одного символа, не может быть выбран в качестве алфавита В для формирования кода.
2. В качестве алфавита А возьмем те же четыре символа «а», «б», «р», «г», в качестве алфавита В - два символа, например, «0» и «1». В качестве кода можно выбрать следующее соответствие - а – 10, б – 110, р – 1110, г – 11110. Если закодировать подобным кодом слово «багр», то получим 11010111101110. Данное слово уже можно декодировать. Здесь в качестве кодов символов алфавита А выбраны коды, имеющие разную длину, поэтому выбранный код называют неравномерным.
3. В качестве алфавита А возьмем символы «а», «б», «р», «г», в качестве алфавита В - символы «0» и «1». В качестве кода можно выберем следующее соответствие - а – 00, б – 01, р – 10, г – 11. Если закодировать этим кодом слово «багр», то получим 01001110. Это слово также можно декодировать. Здесь в качестве кодов символов алфавита А выбраны последовательности символов из алфавита В, имеющие одинаковую длину, поэтому выбранный код называют равномерным.
Равномерные коды можно легко декодировать, разделяя текст на группы символов и заменяя группу символов на один символ исходного алфавита. В данном примере – по два символа в группе. Всего различных вариантов кода длины 2 будет 4! = 1*2*3*4 = 24.
Несомненно, что можно было выбрать коды и любой большей длины, например, а – 000, б – 101, р – 100, г – 111. Однако при этом закодированный текст имел бы большую длину. Чем длиннее текст, тем больше времени будет необходимо для его декодирования.
4. В качестве алфавита А возьмем символы «а», «б», «р», «г», в качестве алфавита В - три символа, например, «0», «1» и «2». В качестве кода можно выбрать одно из следующих соответствий
41. а – 00, б – 01, р – 02, г – 10
42. а – 00, б – 01, р – 02, г – 11
43.а – 00, б – 01, р – 02, г – 20
44.а – 00, б – 01, р – 02, г – 21
45.а – 00, б – 01, р – 02, г – 22
46.а – 01, б – 02, р – 12, г – 22
Можно продолжать и далее, так как это не все соответствия. Поскольку всего пар, которые можно составить из 3 символов – 9: (00), (01), (02), (10), (11), (12), (20), (21), (22), то всего вариантов выбора четырех пар из 9 будет число сочетаний из 9 по 4 и равно = 9!/(4!*5!)=126. Каждую из четырех выбранных из пар можно расставить 4!=24 способами для символов или «а», или «б», или «р», или «г». Например. Рассмотрим код 41. Из него можно получить код 410. а – 00, б – 01, р – 10, г – 02, 411. а – 00, б – 10, р – 01, г – 02 и т. д. Всего, таким образом, вариантов выбора всевозможных соответствий будет равно 126*24 = 3024. Если закодировать кодом 41 слово «багр», то получим 01001002. Это слово также можно декодировать.
5. В качестве алфавита А возьмем символы «а», «б», «в», «г», «д», «р», в качестве алфавита В - два символа, например, «0», «1». Если начать выбор кода таким же способом, как и для третьего способа, то есть а – 00, б – 01, в – 10, г – 11, д - , р – , то необходимо увеличить длину последовательности на 1 и тогда получим один из вариантов кода а – 000, б – 001, в – 010, г – 011, д - 100, р – 101. При этом останутся две невостребованные последовательности 110 и 111. Если бы в алфавите А было восемь символов, то все возможные последовательности из двух символов длины три были бы использованы. Таким образом, при использовании равномерных кодов между мощностью N алфавита А и мощностью М алфавита В существует связь N <= M^L, где L – длина последовательности, при этом L, M, N – натуральные числа (выражение M^L следует читать как M в степени L).
В третьем примере N = 4, M = 2 минимальная величина L = 2 и тогда 4 = 2 и тогда 4 = 2^2, в четвертом примере N = 4, M = 3, минимальная величина L = 2, 4 < 3^2. Если взять N = 4, M = 4, минимальная величина L = 1. Действительно, L = 1, так как этот случай рассмотрен в примере шифрования. Если взять значение N < M, то он сведется к случаю N = 4, M = 4. Какой-то один символ в алфавите В не придется использовать. Следовательно, должно выполняться условие N > = M. Чтобы подсчитать длину D закодированного текста (в символах алфавита В), необходимо знать величины N и M, длину исходного текста К (в символах алфавита А), затем из неравенства N <= M^L установить (можно подбором) минимальное значение L и произвести вычисления по формуле D = L*K.
Рассмотрим текст Хлеб – всему голова. В нем K = 20 символов. Алфавит A = {а б в г е л м о у Х - .} содержит 12 символов, то есть N = 12. Пусть В ={0 1} содержит два символа, то есть M = 2. Такой алфавит называют двоичным, а символы алфавита – двоичными. Рассмотрим неравенство 12 <= 2^L. Минимальное значение L = 4. D = 20*4 = 80 двоичных цифр (символов из алфавита В).
Таким образом, при кодировании текста используются равномерные или неравномерные коды. Равномерные коды необходимы для представления текстовой информации в двоичном виде в компьютере и сохранения ее в таком виде в памяти компьютера. Вполне естественно, что при этом значение величины L существенно влияет на объем сохраняемого текста. Неравномерные коды используются при передаче сообщений в сети, причем используются такие, которые позволяют обнаруживать и исправлять ошибки.
Рекомендуем посмотреть:
Что такое технология потоковых данных
Использование облачного хранилища данных в образовательном пространстве
Восьмеричный переход
Конспект урока информатики по теме «Разветвляющие алгоритмы», 10 класс
Похожие статьи:
Оценка достижений учащихся на уроках информатики
Конспект открытого урока по информатике в 9 классе
Конспект урока информатики в 8 классе
 |
Автор: Ирина Ивановна Биглова
Опубликовано: 3607 дней назад (8 января 2015)
Просмотров: 2275
Блог: Блог Бигловой Ирины
Рубрика: Методические разработки
|
0 Голосов: 0 |
| # 9 января 2015 в 09:34 +1 | ||
|
| # 8 апреля 2015 в 12:15 0 | ||
|
| # 19 апреля 2015 в 09:56 0 | ||
|