Richard Hamming: ບົດທີ 13. ທິດສະດີຂໍ້ມູນຂ່າວສານ

ພວກເຮົາໄດ້ເຮັດມັນ!

"ຈຸດປະສົງຂອງຫຼັກສູດນີ້ແມ່ນເພື່ອກະກຽມເຈົ້າສໍາລັບອະນາຄົດດ້ານວິຊາການຂອງເຈົ້າ."

ສະບາຍດີ, Habr. ຈືຂໍ້ມູນການບົດຄວາມທີ່ຫນ້າຫວາດສຽວ "ເຈົ້າແລະວຽກຂອງເຈົ້າ" (+219, 2588 bookmarks, 429k ອ່ານ)?

ດັ່ງນັ້ນ Hamming (ແມ່ນແລ້ວ, ແມ່ນແລ້ວ, ການກວດສອບຕົນເອງແລະການແກ້ໄຂຕົນເອງ ລະຫັດ Hamming) ມີ​ທັງ​ຫມົດ​ ປື້ມບັນ, ຂຽນໂດຍອີງໃສ່ການບັນຍາຍຂອງລາວ. ພວກເຮົາແປມັນ, ເພາະວ່າຜູ້ຊາຍເວົ້າຈິດໃຈຂອງລາວ.

ນີ້​ແມ່ນ​ປຶ້ມ​ທີ່​ບໍ່​ພຽງ​ແຕ່​ກ່ຽວ​ກັບ IT​, ມັນ​ເປັນ​ຫນັງ​ສື​ກ່ຽວ​ກັບ​ແນວ​ຄິດ​ຂອງ​ຄົນ​ທີ່​ເຢັນ​ຢ່າງ​ບໍ່​ຫນ້າ​ເຊື່ອ​. “ມັນ​ບໍ່​ພຽງ​ແຕ່​ເປັນ​ການ​ເພີ່ມ​ຄວາມ​ຄິດ​ໃນ​ທາງ​ບວກ​; ມັນອະທິບາຍເງື່ອນໄຂທີ່ເພີ່ມໂອກາດໃນການເຮັດວຽກທີ່ຍິ່ງໃຫຍ່."

ຂອບໃຈ Andrey Pakhomov ສໍາລັບການແປ.

ທິດສະດີຂໍ້ມູນຂ່າວສານໄດ້ຖືກພັດທະນາໂດຍ C. E. Shannon ໃນທ້າຍຊຸມປີ 1940. ຜູ້ຈັດການ Bell Labs ຢືນຢັນວ່າລາວເອີ້ນວ່າ "ທິດສະດີການສື່ສານ" ເພາະວ່າ ... ນີ້ແມ່ນຊື່ທີ່ຖືກຕ້ອງກວ່າ. ສໍາລັບເຫດຜົນທີ່ຊັດເຈນ, ຊື່ "ທິດສະດີຂໍ້ມູນຂ່າວສານ" ມີຜົນກະທົບຫຼາຍຕໍ່ສາທາລະນະ, ນັ້ນແມ່ນເຫດຜົນທີ່ Shannon ເລືອກມັນ, ແລະມັນເປັນຊື່ທີ່ພວກເຮົາຮູ້ຈັກຈົນເຖິງທຸກມື້ນີ້. ຊື່ຕົວມັນເອງຊີ້ໃຫ້ເຫັນວ່າທິດສະດີກ່ຽວຂ້ອງກັບຂໍ້ມູນ, ເຊິ່ງເຮັດໃຫ້ມັນສໍາຄັນຍ້ອນວ່າພວກເຮົາກ້າວໄປສູ່ຍຸກຂອງຂໍ້ມູນ. ໃນບົດນີ້, ຂ້າພະເຈົ້າຈະສໍາຜັດກັບບົດສະຫຼຸບຕົ້ນຕໍຈໍານວນຫນຶ່ງຈາກທິດສະດີນີ້, ຂ້າພະເຈົ້າຈະສະຫນອງບໍ່ເຄັ່ງຄັດ, ແຕ່ເປັນຫຼັກຖານ intuitive ຂອງບາງບົດບັນຍັດສ່ວນບຸກຄົນຂອງທິດສະດີນີ້, ດັ່ງນັ້ນທ່ານເຂົ້າໃຈວ່າ "ທິດສະດີຂໍ້ມູນຂ່າວສານ" ຕົວຈິງແລ້ວແມ່ນ, ບ່ອນທີ່ທ່ານສາມາດນໍາໃຊ້ມັນ. ແລະບ່ອນທີ່ບໍ່.

ກ່ອນອື່ນ ໝົດ, "ຂໍ້ມູນ" ແມ່ນຫຍັງ? Shannon ເທົ່າກັບຂໍ້ມູນທີ່ມີຄວາມບໍ່ແນ່ນອນ. ລາວເລືອກ logarithm ລົບຂອງຄວາມເປັນໄປໄດ້ຂອງເຫດການໃດຫນຶ່ງເປັນການວັດແທກປະລິມານຂອງຂໍ້ມູນທີ່ທ່ານໄດ້ຮັບເມື່ອເຫດການທີ່ມີ probability p ເກີດຂຶ້ນ. ຕົວຢ່າງ, ຖ້າຂ້ອຍບອກເຈົ້າວ່າສະພາບອາກາດໃນ Los Angeles ມີໝອກ, ຫຼັງຈາກນັ້ນ p ຢູ່ໃກ້ກັບ 1, ເຊິ່ງກໍ່ບໍ່ໄດ້ໃຫ້ຂໍ້ມູນຫຼາຍ. ແຕ່ຖ້າຂ້ອຍເວົ້າວ່າຝົນຕົກໃນ Monterey ໃນເດືອນມິຖຸນາ, ມັນຈະມີຄວາມບໍ່ແນ່ນອນໃນຂໍ້ຄວາມແລະມັນຈະມີຂໍ້ມູນເພີ່ມເຕີມ. ເຫດການທີ່ເຊື່ອຖືໄດ້ບໍ່ມີຂໍ້ມູນໃດໆ, ນັບຕັ້ງແຕ່ບັນທຶກ 1 = 0.

ໃຫ້ເບິ່ງນີ້ໃນລາຍລະອຽດເພີ່ມເຕີມ. Shannon ເຊື່ອວ່າການວັດແທກປະລິມານຂອງຂໍ້ມູນຄວນຈະເປັນຫນ້າທີ່ຢ່າງຕໍ່ເນື່ອງຂອງຄວາມເປັນໄປໄດ້ຂອງເຫດການ p, ແລະສໍາລັບເຫດການເອກະລາດມັນຄວນຈະເປັນສິ່ງເພີ່ມເຕີມ - ຈໍານວນຂໍ້ມູນທີ່ໄດ້ຮັບຜົນມາຈາກການປະກົດຕົວຂອງສອງເຫດການເອກະລາດຄວນຈະເທົ່າກັບ. ຈໍານວນຂໍ້ມູນທີ່ໄດ້ຮັບເປັນຜົນມາຈາກການປະກົດຕົວຂອງເຫດການຮ່ວມກັນ. ສໍາລັບຕົວຢ່າງ, ຜົນໄດ້ຮັບຂອງມ້ວນ dice ແລະມ້ວນຫຼຽນແມ່ນປົກກະຕິແລ້ວເປັນເຫດການເອກະລາດ. ໃຫ້ພວກເຮົາແປຂ້າງເທິງນີ້ເຂົ້າໄປໃນພາສາຂອງຄະນິດສາດ. ຖ້າ I (p) ແມ່ນຈໍານວນຂໍ້ມູນທີ່ບັນຈຸຢູ່ໃນເຫດການທີ່ມີຄວາມເປັນໄປໄດ້ p, ຫຼັງຈາກນັ້ນສໍາລັບເຫດການຮ່ວມກັນປະກອບດ້ວຍສອງເຫດການເອກະລາດ x ກັບຄວາມເປັນໄປໄດ້ p1 ແລະ y ກັບຄວາມເປັນໄປໄດ້ p2 ພວກເຮົາໄດ້ຮັບ.

(x ແລະ y ແມ່ນເຫດການເອກະລາດ)

ນີ້ແມ່ນສົມຜົນ Cauchy ທີ່ເປັນປະໂຫຍດ, ເປັນຄວາມຈິງສໍາລັບ p1 ແລະ p2 ທັງຫມົດ. ເພື່ອແກ້ໄຂສົມຜົນທີ່ເປັນປະໂຫຍດນີ້, ໃຫ້ສົມມຸດວ່າ

p1 = p2 = p,

ນີ້ເຮັດໃຫ້

ຖ້າ p1 = p2 ແລະ p2 = p ແລ້ວ

ແລະອື່ນໆ ການຂະຫຍາຍຂະບວນການນີ້ໂດຍໃຊ້ວິທີມາດຕະຖານສຳລັບເລກກຳລັງ, ສຳລັບຕົວເລກສົມເຫດສົມຜົນທັງໝົດ m/n ຕໍ່ໄປນີ້ແມ່ນຄວາມຈິງ.

ຈາກການສືບຕໍ່ສົມມຸດຕິຖານຂອງການວັດແທກຂໍ້ມູນ, ມັນປະຕິບັດຕາມວ່າຟັງຊັນ logarithmic ແມ່ນການແກ້ໄຂຢ່າງຕໍ່ເນື່ອງພຽງແຕ່ກັບສົມຜົນທີ່ເປັນປະໂຫຍດ Cauchy.

ໃນທິດສະດີຂໍ້ມູນຂ່າວສານ, ມັນເປັນເລື່ອງທໍາມະດາທີ່ຈະເອົາຖານ logarithm ເປັນ 2, ດັ່ງນັ້ນທາງເລືອກຄູ່ມີຂໍ້ມູນ 1 bit ຢ່າງແທ້ຈິງ. ດັ່ງນັ້ນ, ຂໍ້ມູນແມ່ນວັດແທກໂດຍສູດ

ໃຫ້ຢຸດຊົ່ວຄາວ ແລະເຂົ້າໃຈສິ່ງທີ່ເກີດຂຶ້ນຂ້າງເທິງ. ກ່ອນອື່ນ ໝົດ, ພວກເຮົາບໍ່ໄດ້ ກຳ ນົດແນວຄວາມຄິດຂອງ "ຂໍ້ມູນ"; ພວກເຮົາພຽງແຕ່ ກຳ ນົດສູດ ສຳ ລັບການວັດແທກປະລິມານຂອງມັນ.

ອັນທີສອງ, ມາດຕະການນີ້ແມ່ນຂຶ້ນກັບຄວາມບໍ່ແນ່ນອນ, ແລະເຖິງແມ່ນວ່າມັນເຫມາະສົມສໍາລັບເຄື່ອງຈັກ - ຕົວຢ່າງ, ລະບົບໂທລະສັບ, ວິທະຍຸ, ໂທລະພາບ, ຄອມພິວເຕີ, ແລະອື່ນໆ - ມັນບໍ່ໄດ້ສະທ້ອນເຖິງທັດສະນະຄະຕິຂອງມະນຸດຕໍ່ຂໍ້ມູນຂ່າວສານ.

ອັນທີສາມ, ນີ້ແມ່ນມາດຕະການທີ່ກ່ຽວຂ້ອງ, ມັນຂຶ້ນກັບສະຖານະປັດຈຸບັນຂອງຄວາມຮູ້ຂອງທ່ານ. ຖ້າທ່ານເບິ່ງກະແສຂອງ "ຕົວເລກແບບສຸ່ມ" ຈາກເຄື່ອງສ້າງຕົວເລກແບບສຸ່ມ, ທ່ານສົມມຸດວ່າແຕ່ລະຕົວເລກຕໍ່ໄປແມ່ນບໍ່ແນ່ນອນ, ແຕ່ຖ້າທ່ານຮູ້ສູດການຄິດໄລ່ "ຕົວເລກແບບສຸ່ມ", ຕົວເລກຕໍ່ໄປຈະຮູ້ຈັກ, ແລະດັ່ງນັ້ນຈິ່ງຈະບໍ່ຮູ້ຈັກ. ບັນຈຸຂໍ້ມູນ.

ດັ່ງນັ້ນຄໍານິຍາມຂອງຂໍ້ມູນຂອງ Shannon ແມ່ນເຫມາະສົມສໍາລັບເຄື່ອງຈັກໃນຫຼາຍໆກໍລະນີ, ແຕ່ເບິ່ງຄືວ່າບໍ່ເຫມາະສົມກັບຄວາມເຂົ້າໃຈຂອງມະນຸດກ່ຽວກັບຄໍາສັບ. ມັນແມ່ນຍ້ອນເຫດຜົນນີ້, "ທິດສະດີຂໍ້ມູນຂ່າວສານ" ຄວນຖືກເອີ້ນວ່າ "ທິດສະດີການສື່ສານ." ຢ່າງໃດກໍ່ຕາມ, ມັນຊ້າເກີນໄປທີ່ຈະປ່ຽນຄໍານິຍາມ (ເຊິ່ງໃຫ້ທິດສະດີຄວາມນິຍົມໃນເບື້ອງຕົ້ນ, ແລະຍັງເຮັດໃຫ້ຄົນຄິດວ່າທິດສະດີນີ້ກ່ຽວຂ້ອງກັບ "ຂໍ້ມູນ"), ດັ່ງນັ້ນພວກເຮົາຕ້ອງຢູ່ກັບພວກເຂົາ, ແຕ່ໃນເວລາດຽວກັນເຈົ້າຕ້ອງ. ເຂົ້າໃຈຢ່າງຊັດເຈນວ່າຄໍານິຍາມຂອງຂໍ້ມູນຂອງ Shannon ແມ່ນມາຈາກຄວາມຫມາຍທີ່ຖືກນໍາໃຊ້ທົ່ວໄປແນວໃດ. ຂໍ້ມູນຂອງ Shannon ກ່ຽວຂ້ອງກັບບາງສິ່ງບາງຢ່າງທີ່ແຕກຕ່າງກັນຫມົດ, ຄືຄວາມບໍ່ແນ່ນອນ.

ນີ້ແມ່ນບາງສິ່ງບາງຢ່າງທີ່ຈະຄິດກ່ຽວກັບເວລາທີ່ທ່ານສະເຫນີຄໍາສັບຕ່າງໆ. ຄໍານິຍາມທີ່ສະເຫນີ, ເຊັ່ນຄໍານິຍາມຂອງຂໍ້ມູນຂອງ Shannon, ເຫັນດີກັບຄວາມຄິດຕົ້ນສະບັບຂອງທ່ານແລະມັນແຕກຕ່າງກັນແນວໃດ? ເກືອບບໍ່ມີຄໍາສັບໃດທີ່ສະທ້ອນເຖິງວິໄສທັດທີ່ຜ່ານມາຂອງທ່ານກ່ຽວກັບແນວຄວາມຄິດ, ແຕ່ໃນທີ່ສຸດ, ມັນແມ່ນຄໍາສັບທີ່ໃຊ້ທີ່ສະທ້ອນໃຫ້ເຫັນເຖິງຄວາມຫມາຍຂອງແນວຄວາມຄິດ, ດັ່ງນັ້ນການວາງບາງສິ່ງບາງຢ່າງຢ່າງເປັນທາງການໂດຍຜ່ານຄໍານິຍາມທີ່ຊັດເຈນສະເຫມີແນະນໍາບາງສິ່ງລົບກວນ.

ພິຈາລະນາລະບົບທີ່ມີຕົວອັກສອນປະກອບດ້ວຍສັນຍາລັກ q ທີ່ມີຄວາມເປັນໄປໄດ້ pi. ໃນ​ກໍ​ລະ​ນີ​ນີ້ ຈໍານວນຂໍ້ມູນສະເລ່ຍ ໃນລະບົບ (ມູນຄ່າທີ່ຄາດໄວ້ຂອງມັນ) ເທົ່າກັບ:

ອັນນີ້ເອີ້ນວ່າ entropy ຂອງລະບົບທີ່ມີການແຈກຢາຍຄວາມເປັນໄປໄດ້ {pi}. ພວກເຮົາໃຊ້ຄໍາວ່າ "entropy" ເນື່ອງຈາກວ່າຮູບແບບຄະນິດສາດດຽວກັນປະກົດຢູ່ໃນ thermodynamics ແລະກົນໄກສະຖິຕິ. ນີ້ແມ່ນເຫດຜົນທີ່ວ່າຄໍາວ່າ "entropy" ເຮັດໃຫ້ເກີດຄວາມສໍາຄັນຂອງຄວາມສໍາຄັນອ້ອມຂ້າງຕົວມັນເອງ, ເຊິ່ງໃນທີ່ສຸດກໍ່ບໍ່ສົມເຫດສົມຜົນ. ຮູບແບບຄະນິດສາດດຽວກັນຂອງ notation ບໍ່ໄດ້ຫມາຍເຖິງການຕີຄວາມຫມາຍດຽວກັນຂອງສັນຍາລັກ!

entropy ຂອງການແຈກຢາຍຄວາມເປັນໄປໄດ້ມີບົດບາດສໍາຄັນໃນທິດສະດີການເຂົ້າລະຫັດ. ຄວາມບໍ່ສະເຫມີພາບຂອງ Gibbs ສໍາລັບສອງການແຈກຢາຍຄວາມເປັນໄປໄດ້ທີ່ແຕກຕ່າງກັນ pi ແລະ qi ແມ່ນຫນຶ່ງໃນຜົນສະທ້ອນທີ່ສໍາຄັນຂອງທິດສະດີນີ້. ດັ່ງນັ້ນພວກເຮົາຕ້ອງພິສູດວ່າ

ຫຼັກຖານສະແດງແມ່ນອີງໃສ່ເສັ້ນສະແດງທີ່ຊັດເຈນ, ຮູບ. 13.I, ເຊິ່ງສະແດງໃຫ້ເຫັນວ່າ

ແລະຄວາມສະເຫມີພາບຈະບັນລຸໄດ້ພຽງແຕ່ເມື່ອ x = 1. ໃຫ້ພວກເຮົານໍາໃຊ້ຄວາມບໍ່ສະເຫມີພາບກັບແຕ່ລະໄລຍະຂອງຜົນລວມຈາກເບື້ອງຊ້າຍ:

ຖ້າຕົວຫນັງສືຂອງລະບົບການສື່ສານປະກອບດ້ວຍສັນຍາລັກ q, ຫຼັງຈາກນັ້ນ, ຄວາມເປັນໄປໄດ້ຂອງການສົ່ງສັນຍານຂອງແຕ່ລະສັນຍາລັກ qi = 1/q ແລະການທົດແທນ q, ພວກເຮົາໄດ້ຮັບຈາກຄວາມບໍ່ສະເຫມີພາບຂອງ Gibbs.

ຮູບ 13.I

ນີ້ຫມາຍຄວາມວ່າຖ້າຄວາມເປັນໄປໄດ້ຂອງການສົ່ງສັນຍານ q ທັງຫມົດແມ່ນຄືກັນແລະເທົ່າກັບ - 1 / q, ຫຼັງຈາກນັ້ນ entropy ສູງສຸດແມ່ນເທົ່າກັບ ln q, ຖ້າບໍ່ດັ່ງນັ້ນຄວາມບໍ່ສະເຫມີພາບຖື.

ໃນກໍລະນີຂອງລະຫັດທີ່ສາມາດຖອດລະຫັດໄດ້ເປັນເອກະລັກ, ພວກເຮົາມີຄວາມບໍ່ສະເຫມີພາບຂອງ Kraft

ໃນປັດຈຸບັນຖ້າຫາກວ່າພວກເຮົາກໍານົດ pseudo-probabilities

ບ່ອນທີ່ແນ່ນອນ = 1, ເຊິ່ງຕາມມາຈາກຄວາມບໍ່ສະເໝີພາບຂອງ Gibbs,

ແລະນໍາໃຊ້ algebra ເລັກນ້ອຍ (ຈື່ວ່າ K ≤ 1, ດັ່ງນັ້ນພວກເຮົາສາມາດລຸດໄລຍະ logarithmic, ແລະບາງທີອາດມີຄວາມເຂັ້ມແຂງຄວາມບໍ່ສະເຫມີພາບຕໍ່ມາ), ພວກເຮົາໄດ້ຮັບ.

ບ່ອນທີ່ L ແມ່ນຄວາມຍາວລະຫັດສະເລ່ຍ.

ດັ່ງນັ້ນ, entropy ແມ່ນຕໍາ່ສຸດທີ່ຜູກມັດສໍາລັບລະຫັດຕົວອັກສອນໂດຍສັນຍາລັກໃດໆທີ່ມີຄວາມຍາວຂອງລະຫັດສະເລ່ຍ L. ນີ້ແມ່ນທິດສະດີຂອງ Shannon ສໍາລັບຊ່ອງທາງທີ່ບໍ່ມີການແຊກແຊງ.

ໃນປັດຈຸບັນພິຈາລະນາທິດສະດີຕົ້ນຕໍກ່ຽວກັບຂໍ້ຈໍາກັດຂອງລະບົບການສື່ສານທີ່ຂໍ້ມູນຖືກຖ່າຍທອດເປັນກະແສຂອງບິດເອກະລາດແລະສິ່ງລົບກວນ. ມັນເຂົ້າໃຈວ່າຄວາມເປັນໄປໄດ້ຂອງການສົ່ງຕໍ່ທີ່ຖືກຕ້ອງຂອງຫນຶ່ງບິດແມ່ນ P> 1/2, ແລະຄວາມເປັນໄປໄດ້ທີ່ຄ່າບິດຈະຖືກ inverted ໃນລະຫວ່າງການສົ່ງ (ຄວາມຜິດພາດຈະເກີດຂຶ້ນ) ເທົ່າກັບ Q = 1 - P. ເພື່ອຄວາມສະດວກ, ພວກເຮົາ. ສົມມຸດວ່າຄວາມຜິດພາດແມ່ນເປັນເອກະລາດແລະຄວາມເປັນໄປໄດ້ຂອງຄວາມຜິດພາດແມ່ນຄືກັນສໍາລັບແຕ່ລະບິດທີ່ສົ່ງ - ນັ້ນແມ່ນ, ມີ "ສຽງສີຂາວ" ໃນຊ່ອງທາງການສື່ສານ.

ວິທີທີ່ພວກເຮົາມີສາຍນ້ໍາຍາວຂອງ n bits ເຂົ້າໄປໃນຂໍ້ຄວາມຫນຶ່ງແມ່ນການຂະຫຍາຍ n - dimensional ຂອງລະຫັດຫນຶ່ງບິດ. ພວກເຮົາຈະກໍານົດມູນຄ່າຂອງ n ຕໍ່ມາ. ພິຈາລະນາຂໍ້ຄວາມທີ່ປະກອບດ້ວຍ n-ບິດເປັນຈຸດໃນຊ່ອງ n-ມິຕິ. ເນື່ອງຈາກພວກເຮົາມີພື້ນທີ່ n-dimensional - ແລະສໍາລັບຄວາມງ່າຍດາຍທີ່ພວກເຮົາຈະສົມມຸດວ່າແຕ່ລະຂໍ້ຄວາມມີຄວາມເປັນໄປໄດ້ດຽວກັນທີ່ຈະເກີດຂຶ້ນ - ມີຂໍ້ຄວາມ M (M ຍັງຈະຖືກກໍານົດໃນພາຍຫລັງ), ດັ່ງນັ້ນຄວາມເປັນໄປໄດ້ຂອງຂໍ້ຄວາມທີ່ສົ່ງແມ່ນ.

(ຜູ້ສົ່ງ)
ຕາຕະລາງ 13.II

ຕໍ່ໄປ, ພິຈາລະນາແນວຄວາມຄິດຂອງຄວາມສາມາດຂອງຊ່ອງທາງ. ໂດຍບໍ່ມີການເຂົ້າໄປໃນລາຍລະອຽດ, ຄວາມອາດສາມາດຂອງຊ່ອງທາງແມ່ນກໍານົດເປັນຈໍານວນສູງສຸດຂອງຂໍ້ມູນທີ່ສາມາດສົ່ງຜ່ານຊ່ອງທາງການສື່ສານ, ໂດຍຄໍານຶງເຖິງການນໍາໃຊ້ລະຫັດທີ່ມີປະສິດທິພາບທີ່ສຸດ. ບໍ່ມີການໂຕ້ຖຽງວ່າຂໍ້ມູນເພີ່ມເຕີມສາມາດຖືກສົ່ງຜ່ານຊ່ອງທາງການສື່ສານຫຼາຍກວ່າຄວາມສາມາດຂອງມັນ. ນີ້ສາມາດພິສູດໄດ້ສໍາລັບຊ່ອງທາງ symmetric binary (ທີ່ພວກເຮົາໃຊ້ໃນກໍລະນີຂອງພວກເຮົາ). ຄວາມ​ອາດ​ສາ​ມາດ​ຂອງ​ຊ່ອງ​ທາງ​, ໃນ​ເວ​ລາ​ທີ່​ການ​ສົ່ງ bits​, ແມ່ນ​ລະ​ບຸ​ໄວ້​ເປັນ​

ບ່ອນທີ່, ເຊັ່ນດຽວກັບກ່ອນ, P ແມ່ນຄວາມເປັນໄປໄດ້ຂອງບໍ່ມີຂໍ້ຜິດພາດໃນບາງບິດທີ່ຖືກສົ່ງ. ເມື່ອສົ່ງ n ບິດເອກະລາດ, ຄວາມອາດສາມາດຂອງຊ່ອງທາງແມ່ນໃຫ້ໂດຍ

ຖ້າພວກເຮົາຢູ່ໃກ້ກັບຄວາມອາດສາມາດຂອງຊ່ອງທາງ, ຫຼັງຈາກນັ້ນພວກເຮົາຕ້ອງສົ່ງຂໍ້ມູນເກືອບນີ້ສໍາລັບແຕ່ລະສັນຍາລັກ ai, i = 1, ..., M. ພິຈາລະນາວ່າຄວາມເປັນໄປໄດ້ຂອງການປະກົດຕົວຂອງແຕ່ລະສັນຍາລັກ ai ແມ່ນ 1 / M, ພວກເຮົາໄດ້ຮັບ

ໃນເວລາທີ່ພວກເຮົາສົ່ງຂໍ້ຄວາມ M ທີ່ເປັນໄປໄດ້ເທົ່າທຽມກັນ, ພວກເຮົາມີ

ເມື່ອ n ບິດຖືກສົ່ງ, ພວກເຮົາຄາດຫວັງວ່າຄວາມຜິດພາດ nQ ຈະເກີດຂື້ນ. ໃນທາງປະຕິບັດ, ສໍາລັບຂໍ້ຄວາມທີ່ປະກອບດ້ວຍ n-bits, ພວກເຮົາຈະມີຂໍ້ຜິດພາດປະມານ nQ ໃນຂໍ້ຄວາມທີ່ໄດ້ຮັບ. ສໍາລັບ n ໃຫຍ່, ການປ່ຽນແປງທີ່ກ່ຽວຂ້ອງ (variation = width distribution, )
ການແຜ່ກະຈາຍຂອງຈໍານວນຂອງຄວາມຜິດພາດຈະກາຍເປັນແຄບເພີ່ມຂຶ້ນເປັນ n ເພີ່ມຂຶ້ນ.

ດັ່ງນັ້ນ, ຈາກດ້ານເຄື່ອງສົ່ງ, ຂ້ອຍເອົາຂໍ້ຄວາມ ai ເພື່ອສົ່ງແລະແຕ້ມຮູບກົມອ້ອມຮອບມັນດ້ວຍລັດສະໝີ.

ເຊິ່ງມີຂະຫນາດໃຫຍ່ເລັກນ້ອຍໂດຍຈໍານວນທີ່ເທົ່າກັບ e2 ກ່ວາຈໍານວນຄວາມຜິດພາດທີ່ຄາດໄວ້ Q, (ຮູບ 13.II). ຖ້າ n ແມ່ນໃຫຍ່ພຽງພໍ, ຄວາມເປັນໄປໄດ້ຂອງຈຸດຂໍ້ຄວາມ bj ທີ່ປາກົດຢູ່ດ້ານຜູ້ຮັບຈະຂະຫຍາຍອອກໄປນອກຂອບເຂດນີ້. ໃຫ້ sketch ສະຖານະການດັ່ງທີ່ຂ້າພະເຈົ້າເຫັນມັນຈາກທັດສະນະຂອງ transmitter: ພວກເຮົາມີ radii ໃດຈາກຂໍ້ຄວາມທີ່ສົ່ງ ai ໄປຫາຂໍ້ຄວາມທີ່ໄດ້ຮັບ bj ທີ່ມີຄວາມເປັນໄປໄດ້ຂອງຄວາມຜິດພາດເທົ່າກັບ (ຫຼືເກືອບເທົ່າກັນ) ກັບການແຜ່ກະຈາຍປົກກະຕິ, ເຖິງສູງສຸດ. ໃນ nQ. ສໍາລັບ e2 ໃດກໍ່ຕາມ, ມີ n ຂະຫນາດໃຫຍ່ດັ່ງນັ້ນຄວາມເປັນໄປໄດ້ຂອງຈຸດຜົນໄດ້ຮັບ bj ຢູ່ນອກຂອບເຂດຂອງຂ້ອຍແມ່ນນ້ອຍເທົ່າທີ່ທ່ານຕ້ອງການ.

ຕອນນີ້ໃຫ້ເບິ່ງສະຖານະການດຽວກັນຈາກຂ້າງຂອງເຈົ້າ (ຮູບ 13.III). ຢູ່ດ້ານຜູ້ຮັບມີຮູບຊົງ S(r) ຂອງລັດສະໝີດຽວກັນ r ອ້ອມຮອບຈຸດທີ່ໄດ້ຮັບ bj ໃນຊ່ອງ n-dimensional, ເຊັ່ນວ່າຖ້າຂໍ້ຄວາມທີ່ໄດ້ຮັບ bj ຢູ່ໃນຂອບເຂດຂອງຂ້ອຍ, ຫຼັງຈາກນັ້ນຂໍ້ຄວາມ ai ທີ່ສົ່ງໂດຍຂ້ອຍແມ່ນຢູ່ໃນຂອງເຈົ້າ. ວົງ.

ຄວາມຜິດພາດສາມາດເກີດຂຶ້ນໄດ້ແນວໃດ? ຂໍ້ຜິດພາດອາດຈະເກີດຂື້ນໃນກໍລະນີທີ່ໄດ້ອະທິບາຍໄວ້ໃນຕາຕະລາງຂ້າງລຸ່ມນີ້:

ຮູບທີ 13.III

ໃນທີ່ນີ້ພວກເຮົາເຫັນວ່າຖ້າຢູ່ໃນຂອບເຂດທີ່ສ້າງຂຶ້ນປະມານຈຸດທີ່ໄດ້ຮັບ, ມີຢ່າງຫນ້ອຍຫນຶ່ງຈຸດທີ່ສອດຄ່ອງກັບຂໍ້ຄວາມທີ່ບໍ່ໄດ້ເຂົ້າລະຫັດທີ່ເປັນໄປໄດ້, ຫຼັງຈາກນັ້ນມີຂໍ້ຜິດພາດເກີດຂື້ນໃນລະຫວ່າງການສົ່ງ, ເພາະວ່າທ່ານບໍ່ສາມາດກໍານົດວ່າຂໍ້ຄວາມໃດຖືກສົ່ງ. ຂໍ້ຄວາມທີ່ສົ່ງແມ່ນບໍ່ມີຂໍ້ຜິດພາດພຽງແຕ່ຖ້າຈຸດທີ່ກົງກັນກັບມັນຢູ່ໃນຂອບເຂດ, ແລະບໍ່ມີຈຸດອື່ນທີ່ເປັນໄປໄດ້ໃນລະຫັດທີ່ໃຫ້ຢູ່ໃນຂອບເຂດດຽວກັນ.

ພວກເຮົາມີສົມຜົນທາງຄະນິດສາດສໍາລັບຄວາມເປັນໄປໄດ້ຂອງຄວາມຜິດພາດ Pe ຖ້າຂໍ້ຄວາມ ai ຖືກສົ່ງໄປ.

ພວກເຮົາສາມາດຖິ້ມປັດໄຈທໍາອິດໃນເງື່ອນໄຂທີສອງ, ຖືວ່າເປັນ 1. ດັ່ງນັ້ນພວກເຮົາຈຶ່ງໄດ້ຮັບຄວາມບໍ່ສະເຫມີພາບ

ເຫັນໄດ້ແຈ້ງວ່າ

ເພາະສະນັ້ນ

ນຳໃຊ້ຄືນໃໝ່ກັບໄລຍະສຸດທ້າຍຢູ່ເບື້ອງຂວາ

ເອົາ n ຂະຫນາດໃຫຍ່ພຽງພໍ, ໄລຍະທໍາອິດສາມາດເອົາເປັນຂະຫນາດນ້ອຍຕາມທີ່ຕ້ອງການ, ເວົ້າຫນ້ອຍກ່ວາຈໍານວນບາງ d. ເພາະສະນັ້ນພວກເຮົາມີ

ຕອນນີ້ໃຫ້ເບິ່ງວິທີທີ່ພວກເຮົາສາມາດສ້າງລະຫັດແທນທີ່ງ່າຍດາຍເພື່ອເຂົ້າລະຫັດຂໍ້ຄວາມ M ທີ່ປະກອບດ້ວຍ n bits. ໂດຍບໍ່ຮູ້ວ່າຈະສ້າງລະຫັດແນວໃດ (ລະຫັດແກ້ໄຂຂໍ້ຜິດພາດຍັງບໍ່ທັນຖືກປະດິດ), Shannon ເລືອກລະຫັດແບບສຸ່ມ. Flip ຫຼຽນສໍາລັບແຕ່ລະ n bits ໃນຂໍ້ຄວາມແລະເຮັດຊ້ໍາຂະບວນການສໍາລັບຂໍ້ຄວາມ M. ໃນຈໍານວນທັງຫມົດ, nM coin flips ຈໍາເປັນຕ້ອງໄດ້ເຮັດ, ສະນັ້ນມັນເປັນໄປໄດ້

ວັດຈະນານຸກົມລະຫັດມີຄວາມເປັນໄປໄດ້ດຽວກັນ ½nM. ແນ່ນອນ, ຂະບວນການ Random ຂອງການສ້າງ codebook ຫມາຍຄວາມວ່າມີຄວາມເປັນໄປໄດ້ຂອງການຊ້ໍາກັນ, ເຊັ່ນດຽວກັນກັບຈຸດລະຫັດທີ່ຈະຢູ່ໃກ້ກັນແລະດັ່ງນັ້ນຈຶ່ງເປັນແຫຼ່ງຂອງຄວາມຜິດພາດທີ່ເປັນໄປໄດ້. ຫນຶ່ງຕ້ອງພິສູດວ່າຖ້າສິ່ງນີ້ບໍ່ເກີດຂຶ້ນກັບຄວາມເປັນໄປໄດ້ທີ່ສູງກວ່າລະດັບຄວາມຜິດພາດທີ່ເລືອກຂະຫນາດນ້ອຍ, ຫຼັງຈາກນັ້ນ n ທີ່ໄດ້ຮັບແມ່ນໃຫຍ່ພຽງພໍ.
ຈຸດສໍາຄັນແມ່ນວ່າ Shannon ສະເລ່ຍທຸກ codebooks ທີ່ເປັນໄປໄດ້ເພື່ອຊອກຫາຄວາມຜິດພາດໂດຍສະເລ່ຍ! ພວກເຮົາຈະໃຊ້ສັນຍາລັກ Av[.] ເພື່ອສະແດງຄ່າສະເລ່ຍໃນໄລຍະຊຸດຂອງປື້ມລະຫັດສຸ່ມທີ່ເປັນໄປໄດ້ທັງໝົດ. ໂດຍສະເລ່ຍໃນໄລຍະ d ຄົງທີ່, ແນ່ນອນ, ໃຫ້ຄ່າຄົງທີ່, ເພາະວ່າການສະເລ່ຍແຕ່ລະໄລຍະແມ່ນຄືກັນກັບທຸກໆໄລຍະອື່ນໆໃນຜົນລວມ,

ເຊິ່ງສາມາດເພີ່ມຂຶ້ນ (M–1 ໄປຫາ M)

ສໍາລັບຂໍ້ຄວາມໃດນຶ່ງ, ເມື່ອສະເລ່ຍໃນທົ່ວທຸກ codebooks, ການເຂົ້າລະຫັດຈະແລ່ນຜ່ານຄ່າທີ່ເປັນໄປໄດ້ທັງຫມົດ, ດັ່ງນັ້ນຄວາມເປັນໄປໄດ້ສະເລ່ຍທີ່ຈຸດໃດຫນຶ່ງຢູ່ໃນ sphere ແມ່ນອັດຕາສ່ວນຂອງປະລິມານຂອງ sphere ກັບປະລິມານພື້ນທີ່ທັງຫມົດ. ປະລິມານຂອງຜ່ານແມ່ນ

ບ່ອນທີ່ s=Q+e2 <1/2 ແລະ ns ຕ້ອງເປັນຈຳນວນເຕັມ.

ໄລຍະສຸດທ້າຍຢູ່ເບື້ອງຂວາແມ່ນໃຫຍ່ທີ່ສຸດໃນລວມນີ້. ທໍາອິດ, ໃຫ້ປະເມີນມູນຄ່າຂອງມັນໂດຍໃຊ້ສູດ Stirling ສໍາລັບ factorials. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຈະເບິ່ງຄ່າສໍາປະສິດທີ່ຫຼຸດລົງຂອງຄໍາທີ່ຢູ່ທາງຫນ້າຂອງມັນ, ສັງເກດວ່າຄ່າສໍາປະສິດນີ້ເພີ່ມຂຶ້ນເມື່ອພວກເຮົາຍ້າຍໄປທາງຊ້າຍ, ແລະດັ່ງນັ້ນພວກເຮົາສາມາດ: (1) ຈໍາກັດມູນຄ່າຂອງຜົນບວກກັບຜົນລວມຂອງຄວາມຄືບຫນ້າທາງເລຂາຄະນິດກັບ. ຄ່າສໍາປະສິດເບື້ອງຕົ້ນນີ້, (2) ຂະຫຍາຍຄວາມຄືບຫນ້າທາງເລຂາຄະນິດຈາກ ns ຂໍ້ກໍານົດເປັນຈໍານວນ infinite ຂອງຂໍ້ກໍານົດ, (3) ຄິດໄລ່ຜົນລວມຂອງຄວາມຄືບຫນ້າທາງເລຂາຄະນິດ infinite (ພຶດຊະຄະນິດມາດຕະຖານ, ບໍ່ມີຫຍັງສໍາຄັນ) ແລະສຸດທ້າຍໄດ້ຮັບຄ່າຈໍາກັດ (ສໍາລັບຂະຫນາດໃຫຍ່ພຽງພໍ. n):

ສັງເກດເຫັນວ່າ entropy H (s) ປາກົດຢູ່ໃນຕົວຕົນ binomial ແນວໃດ. ໃຫ້ສັງເກດວ່າການຂະຫຍາຍຊຸດ Taylor H(s)=H(Q+e2) ໃຫ້ການຄາດຄະເນທີ່ໄດ້ຮັບໂດຍຄໍານຶງເຖິງພຽງແຕ່ອະນຸພັນທໍາອິດແລະບໍ່ສົນໃຈອື່ນໆທັງຫມົດ. ບັດ​ນີ້​ໃຫ້​ເຮົາ​ມາ​ລວມ​ເອົາ​ຄຳ​ເວົ້າ​ສຸດ​ທ້າຍ:

ບ່ອນທີ່

ທັງໝົດທີ່ພວກເຮົາຕ້ອງເຮັດແມ່ນເລືອກ e2 ເຊັ່ນວ່າ e3 < e1, ແລະຫຼັງຈາກນັ້ນໄລຍະສຸດທ້າຍຈະນ້ອຍລົງ, ຕາບໃດທີ່ n ແມ່ນໃຫຍ່ພໍ. ດັ່ງນັ້ນ, ຄວາມຜິດພາດ PE ໂດຍສະເລ່ຍສາມາດໄດ້ຮັບຂະຫນາດນ້ອຍຕາມຄວາມຕ້ອງການກັບຄວາມອາດສາມາດຊ່ອງໄດ້ arbitrarily ໃກ້ກັບ C.
ຖ້າຄ່າສະເລ່ຍຂອງລະຫັດທັງຫມົດມີຂໍ້ຜິດພາດເລັກນ້ອຍ, ຢ່າງຫນ້ອຍຫນຶ່ງລະຫັດຕ້ອງເຫມາະສົມ, ດັ່ງນັ້ນຈຶ່ງມີລະບົບລະຫັດທີ່ເຫມາະສົມຢ່າງຫນ້ອຍຫນຶ່ງ. ນີ້ແມ່ນຜົນໄດ້ຮັບທີ່ສໍາຄັນທີ່ໄດ້ຮັບໂດຍ Shannon - "ທິດສະດີຂອງ Shannon ສໍາລັບຊ່ອງທາງທີ່ບໍ່ມີສຽງ", ເຖິງແມ່ນວ່າມັນຄວນຈະສັງເກດວ່າລາວໄດ້ພິສູດນີ້ສໍາລັບກໍລະນີທົ່ວໄປຫຼາຍກ່ວາສໍາລັບຊ່ອງທາງ symmetric binary ງ່າຍດາຍທີ່ຂ້ອຍໃຊ້. ສໍາ​ລັບ​ກໍ​ລະ​ນີ​ທົ່ວ​ໄປ​, ການ​ຄິດ​ໄລ່​ທາງ​ຄະ​ນິດ​ສາດ​ແມ່ນ​ມີ​ຄວາມ​ສັບ​ສົນ​ຫຼາຍ​, ແຕ່​ແນວ​ຄວາມ​ຄິດ​ບໍ່​ໄດ້​ແຕກ​ຕ່າງ​ກັນ​, ສະ​ນັ້ນ​ເລື້ອຍໆ​, ການ​ນໍາ​ໃຊ້​ຕົວ​ຢ່າງ​ຂອງ​ກໍ​ລະ​ນີ​ໃດ​ຫນຶ່ງ​, ທ່ານ​ສາ​ມາດ​ເປີດ​ເຜີຍ​ໃຫ້​ເຫັນ​ຄວາມ​ຫມາຍ​ທີ່​ແທ້​ຈິງ​ຂອງ​ທິດ​ສະ​ດີ​ໄດ້​.

ຂໍໃຫ້ວິພາກວິຈານຜົນໄດ້ຮັບ. ພວກເຮົາໄດ້ເວົ້າຊ້ໍາເລື້ອຍໆ: "ສໍາລັບຂະຫນາດໃຫຍ່ພຽງພໍ n." ແຕ່ n ແມ່ນໃຫຍ່ເທົ່າໃດ? ຫຼາຍ, ຂະຫນາດໃຫຍ່ຫຼາຍຖ້າຫາກວ່າທ່ານກໍ່ຕ້ອງການທີ່ຈະທັງສອງໃກ້ຊິດກັບຄວາມອາດສາມາດຊ່ອງແລະໃຫ້ແນ່ໃຈວ່າການໂອນຂໍ້ມູນທີ່ຖືກຕ້ອງ! ຂະຫນາດໃຫຍ່ດັ່ງນັ້ນ, ໃນຄວາມເປັນຈິງ, ທີ່ທ່ານຈະຕ້ອງໄດ້ລໍຖ້າເປັນເວລາດົນນານເພື່ອສະສົມຂໍ້ຄວາມຂອງ bits ພຽງພໍທີ່ຈະເຂົ້າລະຫັດມັນຕໍ່ມາ. ໃນກໍລະນີນີ້, ຂະຫນາດຂອງວັດຈະນານຸກົມລະຫັດສຸ່ມຈະເປັນຂະຫນາດໃຫຍ່ພຽງແຕ່ (ຫຼັງຈາກທັງຫມົດ, ວັດຈະນານຸກົມດັ່ງກ່າວບໍ່ສາມາດເປັນຕົວແທນໃນຮູບແບບສັ້ນກວ່າບັນຊີລາຍຊື່ຄົບຖ້ວນຂອງ Mn bits ທັງຫມົດ, ເຖິງວ່າຈະມີຄວາມຈິງທີ່ວ່າ n ແລະ M ມີຂະຫນາດໃຫຍ່ຫຼາຍ)!

ການແກ້ໄຂລະຫັດຜິດພາດຫຼີກເວັ້ນການລໍຖ້າຂໍ້ຄວາມຍາວຫຼາຍແລະຫຼັງຈາກນັ້ນການເຂົ້າລະຫັດແລະຖອດລະຫັດມັນຜ່ານ codebooks ຂະຫນາດໃຫຍ່ຫຼາຍເພາະວ່າພວກເຂົາຫລີກລ້ຽງ codebooks ຕົວເອງແລະໃຊ້ຄອມພິວເຕີ້ທໍາມະດາແທນ. ໃນທາງທິດສະດີງ່າຍໆ, ລະຫັດດັ່ງກ່າວມີແນວໂນ້ມທີ່ຈະສູນເສຍຄວາມສາມາດໃນການເຂົ້າຫາຄວາມອາດສາມາດຂອງຊ່ອງທາງແລະຍັງຮັກສາອັດຕາຄວາມຜິດພາດທີ່ຕໍ່າ, ແຕ່ເມື່ອລະຫັດແກ້ໄຂຂໍ້ຜິດພາດຈໍານວນຫລາຍ, ພວກເຂົາປະຕິບັດໄດ້ດີ. ໃນຄໍາສັບຕ່າງໆອື່ນໆ, ຖ້າທ່ານຈັດສັນຄວາມອາດສາມາດຂອງຊ່ອງທາງບາງຢ່າງເພື່ອແກ້ໄຂຂໍ້ຜິດພາດ, ຫຼັງຈາກນັ້ນທ່ານຕ້ອງໃຊ້ຄວາມສາມາດໃນການແກ້ໄຂຂໍ້ຜິດພາດໃນທຸກເວລາ, i.e. ຈໍານວນຄວາມຜິດພາດຫຼາຍຕ້ອງໄດ້ຮັບການແກ້ໄຂໃນແຕ່ລະຂໍ້ຄວາມທີ່ສົ່ງ, ຖ້າບໍ່ດັ່ງນັ້ນທ່ານຈະສູນເສຍຄວາມສາມາດນີ້.

ໃນ​ເວ​ລາ​ດຽວ​ກັນ​, theorem ໄດ້​ພິ​ສູດ​ຂ້າງ​ເທິງ​ແມ່ນ​ຍັງ​ບໍ່​ມີ​ຄວາມ​ຫມາຍ​! ມັນສະແດງໃຫ້ເຫັນວ່າລະບົບສາຍສົ່ງທີ່ມີປະສິດທິພາບຈະຕ້ອງໃຊ້ລະບົບການເຂົ້າລະຫັດທີ່ສະຫລາດສໍາລັບສາຍບິດຍາວຫຼາຍ. ຕົວຢ່າງແມ່ນດາວທຽມທີ່ໄດ້ບິນເກີນດາວເຄາະຊັ້ນນອກ; ໃນຂະນະທີ່ພວກເຂົາເຄື່ອນຍ້າຍອອກໄປຈາກໂລກແລະດວງອາທິດ, ພວກເຂົາຖືກບັງຄັບໃຫ້ແກ້ໄຂຂໍ້ຜິດພາດຫຼາຍຂື້ນໃນບລັອກຂໍ້ມູນ: ດາວທຽມບາງດວງໃຊ້ແຜງແສງອາທິດ, ເຊິ່ງສະຫນອງພະລັງງານປະມານ 5 W, ຄົນອື່ນໃຊ້ແຫຼ່ງພະລັງງານນິວເຄຼຍ, ເຊິ່ງສະຫນອງພະລັງງານດຽວກັນ. ພະລັງງານຕ່ໍາຂອງການສະຫນອງພະລັງງານ, ຂະຫນາດນ້ອຍຂອງຖ້ວຍເຄື່ອງສົ່ງແລະຂະຫນາດຈໍາກັດຂອງຈານຮັບເທິງໂລກ, ໄລຍະທາງອັນໃຫຍ່ຫຼວງທີ່ສັນຍານຕ້ອງເດີນທາງ - ທັງຫມົດນີ້ຮຽກຮ້ອງໃຫ້ມີການນໍາໃຊ້ລະຫັດທີ່ມີລະດັບສູງຂອງການແກ້ໄຂຄວາມຜິດພາດເພື່ອສ້າງເປັນ. ລະບົບການສື່ສານທີ່ມີປະສິດທິພາບ.

ໃຫ້ກັບຄືນໄປຫາຊ່ອງ n-dimensional ທີ່ພວກເຮົາໃຊ້ໃນຫຼັກຖານຂ້າງເທິງ. ໃນການສົນທະນາມັນ, ພວກເຮົາໄດ້ສະແດງໃຫ້ເຫັນວ່າເກືອບທັງຫມົດປະລິມານຂອງຜ່ານແມ່ນສຸມໃສ່ການຢູ່ໃກ້ກັບດ້ານນອກ - ດັ່ງນັ້ນ, ມັນເກືອບແນ່ນອນວ່າສັນຍານທີ່ສົ່ງຈະຕັ້ງຢູ່ໃກ້ກັບຫນ້າດິນຂອງຮູບຊົງທີ່ສ້າງຂຶ້ນປະມານສັນຍານທີ່ໄດ້ຮັບ, ເຖິງແມ່ນວ່າມີຂ້ອນຂ້າງຂ້ອນຂ້າງ. ລັດສະໝີນ້ອຍໆຂອງຮູບຊົງດັ່ງກ່າວ. ດັ່ງນັ້ນ, ມັນບໍ່ແປກໃຈທີ່ສັນຍານທີ່ໄດ້ຮັບ, ຫຼັງຈາກການແກ້ໄຂຄວາມຜິດພາດຈໍານວນຫລາຍ, nQ, ກາຍເປັນຄວາມໃກ້ຊິດກັບສັນຍານທີ່ບໍ່ມີຄວາມຜິດພາດ. ຄວາມສາມາດໃນການເຊື່ອມຕໍ່ທີ່ພວກເຮົາໄດ້ສົນທະນາກ່ອນຫນ້ານີ້ແມ່ນກຸນແຈສໍາຄັນໃນການເຂົ້າໃຈປະກົດການນີ້. ໃຫ້ສັງເກດວ່າ spheres ທີ່ຄ້າຍຄືກັນທີ່ສ້າງຂຶ້ນສໍາລັບລະຫັດ Hamming ແກ້ໄຂຂໍ້ຜິດພາດຈະບໍ່ທັບຊ້ອນກັນ. ຈໍານວນຂະຫນາດໃຫຍ່ຂອງຂະຫນາດເກືອບ orthogonal ໃນຊ່ອງ n-dimensional ສະແດງໃຫ້ເຫັນວ່າເປັນຫຍັງພວກເຮົາສາມາດເຫມາະ M spheres ໃນອາວະກາດທີ່ມີການທັບຊ້ອນເລັກນ້ອຍ. ຖ້າພວກເຮົາອະນຸຍາດໃຫ້ມີການຊ້ອນກັນຂະຫນາດນ້ອຍ, ໂດຍຕົນເອງ, ເຊິ່ງສາມາດນໍາໄປສູ່ຄວາມຜິດພາດພຽງເລັກນ້ອຍໃນລະຫວ່າງການຖອດລະຫັດ, ພວກເຮົາສາມາດໄດ້ຮັບການຈັດວາງທີ່ຫນາແຫນ້ນຂອງ spheres ໃນອາວະກາດ. Hamming ຮັບປະກັນການແກ້ໄຂຄວາມຜິດພາດໃນລະດັບໃດຫນຶ່ງ, Shannon - ຄວາມເປັນໄປໄດ້ຕ່ໍາຂອງຄວາມຜິດພາດ, ແຕ່ໃນເວລາດຽວກັນຮັກສາ throughput ຕົວຈິງ arbitrarily ໃກ້ກັບຄວາມສາມາດຂອງຊ່ອງທາງການສື່ສານ, ທີ່ລະຫັດ Hamming ບໍ່ສາມາດເຮັດໄດ້.

ທິດສະດີຂໍ້ມູນຂ່າວສານບໍ່ໄດ້ບອກພວກເຮົາວິທີການອອກແບບລະບົບປະສິດທິພາບ, ແຕ່ມັນຊີ້ໃຫ້ເຫັນວິທີການໄປສູ່ລະບົບການສື່ສານປະສິດທິພາບ. ມັນເປັນເຄື່ອງມືທີ່ມີຄຸນຄ່າສໍາລັບການກໍ່ສ້າງລະບົບການສື່ສານຂອງເຄື່ອງຈັກກັບເຄື່ອງຈັກ, ແຕ່, ດັ່ງທີ່ໄດ້ລະບຸໄວ້ກ່ອນຫນ້ານີ້, ມັນມີຄວາມກ່ຽວຂ້ອງຫນ້ອຍກັບວິທີການທີ່ມະນຸດສື່ສານກັບກັນແລະກັນ. ຂອບເຂດທີ່ການສືບທອດທາງຊີວະວິທະຍາແມ່ນຄ້າຍຄືລະບົບການສື່ສານດ້ານວິຊາການແມ່ນບໍ່ຮູ້ງ່າຍໆ, ດັ່ງນັ້ນໃນປັດຈຸບັນມັນບໍ່ຊັດເຈນວ່າທິດສະດີຂໍ້ມູນນໍາໃຊ້ກັບພັນທຸກໍາແນວໃດ. ພວກເຮົາບໍ່ມີທາງເລືອກທີ່ຈະພະຍາຍາມ, ແລະຖ້າຄວາມສໍາເລັດສະແດງໃຫ້ເຫັນພວກເຮົາລັກສະນະຄ້າຍຄືເຄື່ອງຈັກຂອງປະກົດການນີ້, ຫຼັງຈາກນັ້ນຄວາມລົ້ມເຫຼວຈະຊີ້ໃຫ້ເຫັນເຖິງລັກສະນະທີ່ສໍາຄັນອື່ນໆຂອງຂໍ້ມູນ.

ຂໍ​ໃຫ້​ເຮົາ​ບໍ່​ຄ່ອຍ​ເກີນ​ໄປ. ພວກເຮົາໄດ້ເຫັນວ່າຄໍານິຍາມຕົ້ນສະບັບທັງຫມົດ, ໃນຂອບເຂດທີ່ໃຫຍ່ກວ່າຫຼືຫນ້ອຍ, ຕ້ອງສະແດງເຖິງຄວາມສໍາຄັນຂອງຄວາມເຊື່ອຕົ້ນສະບັບຂອງພວກເຮົາ, ແຕ່ພວກມັນມີລັກສະນະບິດເບືອນໃນລະດັບໃດຫນຶ່ງແລະດັ່ງນັ້ນຈຶ່ງໃຊ້ບໍ່ໄດ້. ມັນໄດ້ຖືກຍອມຮັບຕາມປະເພນີວ່າ, ໃນທີ່ສຸດ, ຄໍານິຍາມທີ່ພວກເຮົາໃຊ້ຕົວຈິງແມ່ນກໍານົດຄວາມສໍາຄັນ; ແຕ່, ນີ້ພຽງແຕ່ບອກພວກເຮົາວິທີການປຸງແຕ່ງສິ່ງຕ່າງໆແລະໃນທາງທີ່ບໍ່ມີຄວາມຫມາຍໃດໆກັບພວກເຮົາ. ວິທີການ postulational, ນິຍົມຢ່າງແຂງແຮງໃນວົງຄະນິດສາດ, ເຮັດໃຫ້ຫຼາຍທີ່ຈະຕ້ອງການໃນການປະຕິບັດ.

ໃນປັດຈຸບັນພວກເຮົາຈະເບິ່ງຕົວຢ່າງຂອງການທົດສອບ IQ ທີ່ຄໍານິຍາມແມ່ນເປັນວົງຕາມທີ່ທ່ານຕ້ອງການແລະ, ດັ່ງນັ້ນ, ຄວາມເຂົ້າໃຈຜິດ. ການ​ທົດ​ສອບ​ໄດ້​ຖືກ​ສ້າງ​ຕັ້ງ​ຂຶ້ນ​ທີ່​ຄວນ​ຈະ​ວັດ​ແທກ​ຄວາມ​ສະ​ຫຼາດ​. ຫຼັງຈາກນັ້ນ, ມັນໄດ້ຖືກປັບປຸງເພື່ອເຮັດໃຫ້ມັນສອດຄ່ອງເທົ່າທີ່ເປັນໄປໄດ້, ແລະຫຼັງຈາກນັ້ນມັນຖືກພິມອອກແລະ, ໃນວິທີການງ່າຍດາຍ, calibrated ດັ່ງນັ້ນ "ປັນຍາ" ທີ່ວັດແທກໄດ້ຫັນອອກມາເປັນປົກກະຕິ (ຕາມເສັ້ນໂຄ້ງການປັບທຽບ, ແນ່ນອນ). ຄໍານິຍາມທັງຫມົດຕ້ອງໄດ້ຮັບການກວດກາຄືນໃຫມ່, ບໍ່ພຽງແຕ່ໃນເວລາທີ່ພວກເຂົາຖືກສະເຫນີຄັ້ງທໍາອິດ, ແຕ່ຍັງຫຼາຍຕໍ່ມາ, ໃນເວລາທີ່ພວກເຂົາຖືກນໍາໃຊ້ໃນບົດສະຫຼຸບທີ່ໄດ້ແຕ້ມ. ຂອບເຂດກໍານົດຂອບເຂດໃດທີ່ເຫມາະສົມກັບບັນຫາທີ່ຖືກແກ້ໄຂ? ນິຍາມທີ່ໃຫ້ໄວ້ໃນການຕັ້ງຄ່າອັນໜຶ່ງມັກຈະຖືກນຳໃຊ້ໃນການຕັ້ງຄ່າທີ່ແຕກຕ່າງກັນຫຼາຍເທົ່າໃດ? ອັນນີ້ເກີດຂຶ້ນເລື້ອຍໆ! ໃນມະນຸດ, ທີ່ທ່ານ inevitably ຈະພົບໃນຊີວິດຂອງທ່ານ, ນີ້ເກີດຂຶ້ນເລື້ອຍໆ.

ດັ່ງນັ້ນ, ຫນຶ່ງໃນຈຸດປະສົງຂອງການນໍາສະເຫນີທິດສະດີຂໍ້ມູນນີ້, ນອກເຫນືອຈາກການສະແດງໃຫ້ເຫັນເຖິງຜົນປະໂຫຍດຂອງມັນ, ແມ່ນເພື່ອເຕືອນທ່ານກ່ຽວກັບອັນຕະລາຍນີ້, ຫຼືສະແດງໃຫ້ທ່ານເຫັນວິທີການນໍາໃຊ້ມັນເພື່ອໃຫ້ໄດ້ຜົນທີ່ຕ້ອງການ. ມັນໄດ້ຖືກສັງເກດເຫັນດົນນານວ່າຄໍານິຍາມເບື້ອງຕົ້ນກໍານົດສິ່ງທີ່ທ່ານຊອກຫາໃນທີ່ສຸດ, ໃນຂອບເຂດທີ່ໃຫຍ່ກວ່າທີ່ມັນເບິ່ງຄືວ່າ. ຄໍານິຍາມໃນເບື້ອງຕົ້ນຮຽກຮ້ອງໃຫ້ມີຄວາມສົນໃຈຫຼາຍຈາກທ່ານ, ບໍ່ພຽງແຕ່ໃນສະຖານະການໃຫມ່, ແຕ່ຍັງຢູ່ໃນຂົງເຂດທີ່ທ່ານໄດ້ເຮັດວຽກເປັນເວລາດົນນານ. ນີ້ຈະຊ່ວຍໃຫ້ທ່ານເຂົ້າໃຈເຖິງສິ່ງທີ່ຜົນໄດ້ຮັບທີ່ໄດ້ຮັບແມ່ນ tautology ແລະບໍ່ແມ່ນສິ່ງທີ່ເປັນປະໂຫຍດ.

ເລື່ອງທີ່ມີຊື່ສຽງຂອງ Eddington ເລົ່າເຖິງຄົນທີ່ຫາປາໃນທະເລດ້ວຍຕາຫນ່າງ. ຫຼັງ​ຈາກ​ການ​ສຶກ​ສາ​ຂະ​ຫນາດ​ຂອງ​ປາ​ທີ່​ເຂົາ​ເຈົ້າ​ຈັບ​ໄດ້​, ພວກ​ເຂົາ​ເຈົ້າ​ກໍາ​ນົດ​ຂະ​ຫນາດ​ຕໍາ​່​ສຸດ​ທີ່​ຂອງ​ປາ​ທີ່​ພົບ​ໃນ​ທະ​ເລ​! ການສະຫລຸບຂອງພວກເຂົາຖືກຂັບເຄື່ອນໂດຍເຄື່ອງມືທີ່ໃຊ້, ບໍ່ແມ່ນໂດຍຄວາມເປັນຈິງ.

ຕິດ​ຕາມ​ຕອນ​ຕໍ່​ໄປ…

ຜູ້ທີ່ຕ້ອງການຊ່ວຍໃນການແປພາສາ, ຮູບແບບແລະການພິມຫນັງສື - ຂຽນໃນຂໍ້ຄວາມສ່ວນບຸກຄົນຫຼືອີເມລ໌ [email protected]

ໂດຍວິທີທາງການ, ພວກເຮົາຍັງໄດ້ເປີດຕົວການແປພາສາຂອງຫນັງສືເຢັນອີກ - "ເຄື່ອງຈັກໃນຄວາມຝັນ: ເລື່ອງຂອງການປະຕິວັດຄອມພິວເຕີ")

ພວກເຮົາກໍາລັງຊອກຫາໂດຍສະເພາະ ຜູ້​ທີ່​ຈະ​ຊ່ວຍ​ໃຫ້​ການ​ແປ​ພາ​ສາ​ ບົດໂບນັດ, ເຊິ່ງມີພຽງແຕ່ຢູ່ໃນວິດີໂອ. (ໂອນສໍາລັບ 10 ນາທີ, 20 ທໍາອິດໄດ້ຖືກປະຕິບັດແລ້ວ)

ເນື້ອໃນຂອງປຶ້ມ ແລະບົດທີ່ແປຄໍາອະທິຖານ

1. Intro to The Art of Doing Science and Engineering: ການຮຽນຮູ້ເພື່ອຮຽນຮູ້ (28 ມີນາ 1995) ການແປ: ບົດທີ 1
2. "ພື້ນຖານຂອງການປະຕິວັດດິຈິຕອລ (ບໍ່ເປັນລະບຽບ)" (30 ມີນາ 1995) ບົດທີ 2. ພື້ນຖານຂອງການປະຕິວັດດິຈິຕອລ
3. "ປະຫວັດຂອງຄອມພິວເຕີ - ຮາດແວ" (31 ມີນາ 1995) ບົດທີ 3. ປະຫວັດຄວາມເປັນມາຂອງຄອມພິວເຕີ-ຮາດແວ
4. "ປະຫວັດສາດຂອງຄອມພິວເຕີ - ຊອບແວ" (4 ເມສາ 1995) ບົດທີ 4. ປະຫວັດຄວາມເປັນມາຂອງຄອມພິວເຕີ-ຊອບແວ
5. "ປະຫວັດຂອງຄອມພິວເຕີ - ຄໍາຮ້ອງສະຫມັກ" (6 ເມສາ 1995) ບົດທີ 5: ປະຫວັດຄວາມເປັນມາຂອງຄອມພິວເຕີ - ການນຳໃຊ້ຕົວຈິງ
6. "ປັນຍາທຽມ - ພາກທີ I" (7 ເມສາ 1995) ບົດທີ 6. ປັນຍາປະດິດ - 1
7. "ປັນຍາທຽມ - ພາກທີ II" (11 ເມສາ 1995) ບົດທີ 7. ປັນຍາປະດິດ - II
8. "Artificial Intelligence III" (13 ເມສາ 1995) ບົດທີ 8. Artificial Intelligence-III
9. "n-Dimensional Space" (14 ເມສາ 1995) ບົດທີ 9. N-dimensional space
10. "ທິດສະດີການຂຽນລະຫັດ - ການເປັນຕົວແທນຂອງຂໍ້ມູນ, ພາກທີ I" (18 ເມສາ 1995) ບົດທີ 10. ທິດສະດີການຂຽນລະຫັດ - I
11. "ທິດສະດີການຂຽນລະຫັດ - ການເປັນຕົວແທນຂອງຂໍ້ມູນ, ພາກທີ 20" (1995 ເມສາ XNUMX) ບົດທີ 11. ທິດສະດີການເຂົ້າລະຫັດ - II
12. "ລະຫັດການແກ້ໄຂຂໍ້ຜິດພາດ" (21 ເມສາ 1995) ບົດທີ 12. ລະຫັດການແກ້ໄຂຂໍ້ຜິດພາດ
13. "ທິດສະດີຂໍ້ມູນຂ່າວສານ" (25 ເມສາ 1995) ບົດທີ 13. ທິດສະດີຂໍ້ມູນຂ່າວສານ
14. "ຕົວກອງດິຈິຕອນ, ພາກທີ I" (27 ເມສາ 1995) ບົດທີ 14. ການກັ່ນຕອງດິຈິຕອລ - 1
15. "ຕົວກອງດິຈິຕອນ, ພາກທີ II" (28 ເມສາ 1995) ບົດທີ 15. ການກັ່ນຕອງດິຈິຕອລ - 2
16. "ຕົວກອງດິຈິຕອນ, ພາກທີ III" (2 ພຶດສະພາ 1995) ບົດທີ 16. ການກັ່ນຕອງດິຈິຕອລ - 3
17. "ຕົວກອງດິຈິຕອນ, ພາກທີ IV" (4 ພຶດສະພາ 1995) ບົດທີ 17. ການກັ່ນຕອງດິຈິຕອນ - IV
18. "ການຈຳລອງ, ພາກທີ 5" (1995 ພຶດສະພາ XNUMX) ບົດທີ 18. ການສ້າງແບບຈໍາລອງ - I
19. "ການຈຳລອງ, ພາກທີ II" (9 ພຶດສະພາ 1995) ບົດທີ 19. ການສ້າງແບບຈໍາລອງ - II
20. "ການຈຳລອງ, ພາກທີ III" (11 ພຶດສະພາ 1995) ບົດທີ 20. ການສ້າງແບບຈໍາລອງ - III
21. "Fiber Optics" (12 ພຶດສະພາ 1995) ບົດທີ 21. Fiber optics
22. "ຄໍາແນະນໍາຄອມພິວເຕີຊ່ວຍ" (16 ພຶດສະພາ 1995) ບົດທີ 22: ຄຳແນະນຳການນຳໃຊ້ຄອມພິວເຕີ (CAI)
23. "ຄະນິດສາດ" (18 ພຶດສະພາ 1995) ບົດທີ 23. ຄະນິດສາດ
24. "ກົນຈັກ Quantum" (19 ພຶດສະພາ 1995) ບົດທີ 24. ກົນຈັກ Quantum
25. "ຄວາມຄິດສ້າງສັນ" (23 ພຶດສະພາ 1995). ການແປ: ບົດທີ 25. ຄວາມຄິດສ້າງສັນ
26. "ຜູ້ຊ່ຽວຊານ" (25 ພຶດສະພາ 1995) ບົດທີ 26. ຜູ້ຊ່ຽວຊານ
27. "ຂໍ້ມູນທີ່ບໍ່ຫນ້າເຊື່ອຖື" (26 ພຶດສະພາ 1995) ບົດທີ 27. ຂໍ້ມູນທີ່ບໍ່ຫນ້າເຊື່ອຖື
28. "ວິສະວະກໍາລະບົບ" (ເດືອນພຶດສະພາ 30, 1995) ບົດທີ 28. ວິສະວະກຳລະບົບ
29. "ເຈົ້າໄດ້ສິ່ງທີ່ເຈົ້າວັດແທກ" (1 ມິຖຸນາ 1995) ບົດທີ 29: ເຈົ້າໄດ້ຮັບສິ່ງທີ່ທ່ານວັດແທກ
30. "ພວກເຮົາຮູ້ໄດ້ແນວໃດ" (ມິຖຸນາ 2, 1995) ແປເປັນ 10 ນາທີ
31. Hamming, “ເຈົ້າ ແລະການຄົ້ນຄວ້າຂອງເຈົ້າ” (ເດືອນມິຖຸນາ 6, 1995). ການແປ: ເຈົ້າແລະວຽກຂອງເຈົ້າ

ຜູ້ທີ່ຕ້ອງການຊ່ວຍໃນການແປພາສາ, ຮູບແບບແລະການພິມຫນັງສື - ຂຽນໃນຂໍ້ຄວາມສ່ວນບຸກຄົນຫຼືອີເມລ໌ [email protected]

ແຫຼ່ງຂໍ້ມູນ: www.habr.com