I've told you a bit about information.
Bits. Labels. Probabilities.
I is equal to minus the sum over i of
P sub i, log to the base 2 of P sub i
The fundamental formula of
information theory
I told you about mutual information
which is if I have two variables,
such as the input and output to a channel.
The mutual information tells you... is
equal to the amount of information that is
shared in common between input and output.
It is the information
that passes through
or gets through the channel.
And in fact, from Claude Shannon,
it's actually equal to
the practical channel capacity.
Or if I take the input probabilities, or
frequencies that maximize the mutual
information, that mutual information is the
rate at which information can be sent
reliably down this channel. You cannot
send information at a higher rate, and
you can send information at that rate.
This is a tremendously practical
application of information theory. Because
it tells us that if we have noisy channels
or lossy channels, channels where we're
using sound, channels where we're using light,
chanels if we're using electromagnetic
radiation, channels where we send information
through the mail, any such channel has
a capacity, and Shannon's theorem tells us
what that capacity is, it tells us that we
can't surpass it, and it tells us how to
achieve it. And this is at the basis of
the application of information theory to
practical communications, for instance via
fiber-optic cables.
So, there are some fun examples of this.
A nice way to look at this picture is that
here we have this channel. We have x in...
we have P of x sub i. Here we have
the output. We have P of y sub j,
y out, given x sub i in.
And then we have the associated mutual
information.
So here we have I(x), this is the
information in.
Here we have I(y), this is the
information that comes out.
The information that goes through
the channel like this is the mutual
information between the input and
the output. We can also look at
some things that I'm going to call "loss,"
and another thing that I'm going to call
"noise." So, what is loss? Loss is
information that goes into the channel,
but does not come out. Like the roaches
going into a roach motel. So, what is that?
It's information that we don't know about
the input, given that we know the output.
So, if we know the output, this is
residual stuff that went in, bits that
went in, that never came out. Similiarly,
the noise is information that came out
that didn't go in. So noise is stuff where
if we know exactly what went in, it's
residual bits of information that came
out that had no explanation in terms of
what went in. So we have a nice picture
in terms of the whole set of processes
that are going on in information. We have
the information going in, we have the
information going out. We have the loss,
which is information that goes in that
doesn't come out. We have noise, which is
informaiton that came from nowhere
that didn't go in - of course, it actually
comes from physical processes. And finally
we have the mutual information, which is
the information that actually goes through
the channel and that represents the
channel capacity.
So, I also talked a bit about computation.
So, if you have a digital computer. Here is
what digital computers looked like when
I was a kid... You had, like, a tape thing,
you had a bunch of little lights on the
front and switches, and then you
read the tape, and then it spewed out some
output, maybe on some paper tape -
you could even
put some input on paper tape - it would
have some memory like this. All a digital
computer is doing is
breaks up information
into bits which are the smallest chunks of
information, typically called 0 and 1, or
true and false, in a digital computer.
And then flips those bits
in a systematic fashion.
So for all their power and
all their stupidity, all that these
digital computers that we have, including
things like our smart phones, as well as
our desktops and supercomputers, all
they're doing is registering and storing
information as bits and then flipping
those bits in a systematic fashion.
And let me just remind you about this
fundamental theorem about computation
which is that any digital computation
can be written in some kind of
circuit diagram.
Here's x, here's y, here's z. Here's
something where I make a copy of x,
I take an OR gate... This is "OR",
you will recall.
Here's a copy of X, here's X here.
This is X or Y.
Also known as X or Y.
And here i can say
for example, take an AND gate, and
I can here send this through a NOT gate
And then I can combine them in another
AND gate, And in the end, I think that
what I have is NOT X AND Z AND
(X OR Y).
So, when I have a digital computer,
what happens is that it takes bits of
information, it performs simple AND, OR,
NOT, and copy operations, and
by doing these sequentially, in whatever
order you wanted to do it, you end uo
evaluating arbitrary logical expressions...
NOT X and Z AND X or Y... whatever
that means, I have no idea what it means.
But it is what it is, it means what it is.
So, if we talk about digital computation,
all digital computers are is taking
information and processing it.
And if we put together computation
and communication,
and probabilities,
what we find is that taking together
the idea of information, processing
information as computation,
sending information reliably from
one place to another is communication
this information refers at bottom to the
probabilities of events... being sunny,
being rainy. Probability that a photon
going into a channel makes it out the
other side. Probability of 0,
probability of 1, probability of heads,
probability of tails... but when we put
together these three pieces
interlocking, what we get is the theory
of information.
And I hope that in the course
of these brief lectures here, I've been
able to convince you that these remarkable
processes that are going on all
around us, the fault, or result of the
information processing revolution that began
in the mid-twentieth century and continues
in fact, continues at an accelerating rate
to this day, can be understood with
a simple set of mathematical ideas that
are interlinked with each other, and give
a set of ideas of very profound richness
and impact on human society with
implications for... I don't know what!
Thank you for your attention,
Do well on the homework,
Exam will be multiple choice, I am sure
you will all do well.
前回はインファーメション、ビッツ、レーブルなど話しまた。
例えば、"i" はマイナスリーマンサムのPのiかけログ2かけるPのi
これはインファメーション定理の基本的な式です
前回ムゥーチュウアル*インファメーションのことこそ話また
Tôi đã nói qua về thông tin
Bit. Nhãn. Xác suất.
I bằng logarit cơ số 2
của tổng Pi với mọi i
Đây là công thức căn bản
của lý thuyết thông tin
Tôi đã nói về
thông tin hai chiều
khi tôi có hai biến
ví dụ như là đầu vào và đầu ra
của một kênh
Những gì thông tin hai chiều
cho bạn biết
tương đương với thông tin được
chia sẻ giữa đầu vào và đầu ra.
Đó là thông tin
được truyền qua
hay đi qua kênh truyền.
Và thực tế là, Claude Shannon
cho ta biết
thực ra nó bằng với
dung lượng thực tế
của kênh truyền
Hoặc nếu tôi có xác suất đầu vào,
hay là
tần suất mà cực đại hóa
thông tin
hai chiều, thì thông tin hai chiều
này
chính là tốc độ mà thông tin có thể
được truyền
một cách tin cậy trên kênh. Bạn
không thể
truyền tin ở tốc độ cao hơn, mà
chỉ có thể gửi tin ở tốc độ
tối đa này thôi.
Đây là một ứng dụng
rất quan trọng
của lý thuyết thông tin, vì nó
cho ta ta biết là nếu ta có
một kênh bị nhiễu
hoặc kênh mà thông tin bị mất, như
là các kênh mà chúng ta sử dụng
âm thanh hay ánh sáng,
hay các kênh truyền sóng điện từ
kênh mà chúng ta gửi thông tin
qua thư, tất cả các kênh
đều có một dung lượng nhất định.
Và lý thuyết Shannon cho ta biết
dung lượng này là bao nhiêu
nó cho ta biết là ta
không thể vượt qua nó,
và nó cho ta biết
làm sao ta đạt được nó.
và đây là căn bản của việc
ứng dụng lý thuyết thông tin vào
các liên lạc thực tế, ví dụ như
qua cáp quang.
Có một số ví dụ vui của việc này.
Một cách tiếp cận vấn đề là
giả sử ta có một kênh ở đây.
Ta có x ở đầu vào
Ta có P của xi. Ở đây ta có
đầu ra. Chúng ta có P (yj|xi),
Và chúng ta có thông tin hai chiều
liên kết
Ở đây ta có I(x), là thông tin
đầu vào
Ở đây ta có I(y), là thông tin
đầu ra
Thông tin được truyền
qua kênh tương tự như thông tin
hai chiều
giữa đầu vào
và đầu ra. Chúng ta cũng có thể
xem xét cái mà tôi sẽ gọi là
"mất mát",
và một yếu tố khác mà tôi
sẽ gọi là
"nhiều". Vậy, "mất mát" là gì?
Mất mát là thông tin
đi vào kênh,
nhưng không tới được đâu ra.
Giống như một con bọ
chui vào bẫy. Vậy nó là cái gì?
Đó là thông tin mà chúng ta không
biết được đầu vào
giả sử là chúng ta biết đầu ra.
Vậy nếu chúng ta biết được đầu ra,
đã có một số thông tin hay bit ở đầu vào
không tới được đầu ra. Tương tự,
nhiễu là các thông tin ở đầu ra
nhưng không có ở đầu vào. Nhiễu
là các thông tin
mà chúng ta không biết
từ đâu xuất hiện, nó là
các bit thông tin sai lệch
tự dưng
xuất hiện mà không tồn tại
ở đầu vào. Vậy là chúng ta có bức tranh
toàn cảnh về quá trình
xử lý thông tin. Chúng ta có
thông tin đi vào, chúng ta có
thông tin đi ra. Chúng ta có
sự mất mát
là thông tin đi vào mà
không đi ra. Chúng ta có nhiễu, là
thông tin bỗng nhiên xuất hiện
mà không có ở đầu vào -
đương nhiên, các thông tin này
phải có nguồn gốc từ các
quá trình vật lý. Và cuối cùng
chúng ta có thông tin hai chiều, là
các thông tin thực sự được
truyền qua kênh và thể hiện
dung lượng kênh.
Tôi cũng đã trình bày qua về
quá trình tính toán.
Nếu bạn có một chiếc máy tính. Máy tính
trông như thế này khi
tôi còn bé .. Bạn có,
dạng như một băng đĩa
bạn có rất nhiều các bóng đèn nhỏ
trên các cổng và công tắc, và rồi bạn
đọc băng, và nó sẽ ghi lên
đầu ra, ví dụ như một băng giấy -
bạn thậm chí có thể
xác lập đầu vào trên một băng giấy khác -
nó sẽ
có bộ nhớ kiểu vậy. Một máy tính
điện tử sẽ chia nhỏ
thông tin
thành các bit là các đơn vị
thông tin
nhỏ nhất, thường được gọi là
0 và 1, hoặc
đúng và sai trong máy tính
điện tử
Và rồi máy tính sẽ đổi giá trị
các bit này
một cách có hệ thống.
Vậy với tất cả sức mạnh và
sự ngu ngốc của chúng, tất cả các
máy tính điện tử mà chúng ta có,
bao gồm
cả điện thoại thông minh,
cũng như
máy tính cá nhân và siêu máy tính,
tất cả
chúng đều ghi nhận và lưu trữ
thông tin dưới dạng bit và rồi
thay đổi các bit này
một cách có hệ thống.
Và chỉ nhắc bạn về
lý thuyết tính toán căn bản
rằng bất kỳ máy tính điện tử nào
cũng có thể được mô tả dưới
dạng các mạch điện.
Đây là x, đây là y, đây là z. Đây là
một thứ khi tôi tạo một bản sao của x,
tôi dùng cổng OR ... Đây là "OR",
bạn sẽ được nhắc lại.
Đây là bản sao của X, đây là X
Đây là X hoặc Y
Còn được gọi là X OR Y
Và ở đây tôi có thể nói
ví dụ, lấy cổng AND, và
ở đây tôi có thể truyền nó qua
cổng NOT
Và tôi có thể kết hợp chúng trong
một
cổng AND khác. Và cuối cùng, tôi
nghĩ
chúng ta có NOT X AND Z AND
(X OR Y)
Vậy, khi tôi có một máy tính điện tử,
nó sẽ nhận các bit
thông tin, thực hiện các phép
đơn giản AND, OR, NOT, copy và
bằng việc thực hiện tuần tự các phép này,
theo bất cứ
thứ tự nào bạn muốn, thì kết thúc bạn
có thể
tính toán bất kỳ biểu thức logic nào.
NOT X AND Z AND X OR Y ... bất kỳ
Nó có nghĩ gì .. tôi không biết
Nhưng nó là như vậy thôi.
Vậy, nếu chúng ta nói về
tính toán điện tử
tất cả các máy tính điện tử đều
nhận và xử lý thông tin
Và nếu chúng ta có tính toán
và truyền thông,
và xác suất,
chúng ta thấy rằng việc
tập hợp các ý tưởng
về thông tin, xử lý thông tin
dưới dạng tính toán
gửi thông tin tin cậy
từ nơi này tới nơi khác
là truyền thông
thông tin ở phía dưới
là
xác suất của các sự kiện ...
trời nắng,
trời mưa. Xác suất một
quang tử (photon)
đi vào đầu này của kênh sẽ
xuất hiện ở đầu kia. Xác suất của 0,
xác suất của 1, xác suất mặt ngửa,
xác suất mặt sấp ... nhưng khi chúng ta
đặt ba phần này
lại với nhau, chúng ta sẽ có
lý thuyết thông tin.
Và tôi hy vọng rằng trong
khóa học này
với những bài giảng ngắn gọn,
tôi đã có thể
thuyết phục bạn rằng tất cả
các quá trình
đáng kinh ngạc đang xảy ra
xung quanh ta, kết quả
cuộc cách mạng thông tin vốn
bắt đầu
từ giữa thế kỷ XX và đang
tiếp tục với vận tốc ngày càng lớn
cho tới ngày nay, có thể được hiểu
bằng một tập hợp đơn giản các
ý tưởng toán học có
liên kết với nhau, và cho phép
tập ý tưởng này có một sự phong phú
sâu sắc
và ảnh hưởng lên xã hội loài ngoài với
những thay đổi ... tôi không rõ là gì nữa!
Cảm ơn sự theo dõi của các bạn,
Chúc làm bài tập về nhà vui vẻ.
Bài thi sẽ là dạng đề trắc nghiệm,
tôi tin
các bạn sẽ làm tốt