关于算法:ECE3141信息与网络

ECE3141 Information and networks – short projects

Introduction

Students working in pairs will undertake a short project. The projects will involve writing MATLAB or other simulation programmes or perhaps analysing the outputs of network analysis tools, and communicating the results of the investigation in a short report and a short (5 minute) live presentation on the topic. The precise details will be confirmed closer to the submission deadline, but you can expect the following:

• As soon as your partner and topic are defined, you should start working with that

partner to define the project aims, do any necessary background research and carry out

the simulations or measurements you need

• A demonstrator will check in on you during the lab session in week 8, to see that you

understand your topic, have a plan in place and have started your simulations.

• Completion and submission of a brief (2-page) written report and presentation pack

(PowerPoint) by the end of week 10

• A short (5-minute) live presentation of your results during your scheduled lab time in

week 11 or 12. The audience for your live presentation will be other students from your

lab class, along with one or two demonstrators. (Online students will present via Zoom.)

• Each student is expected to speak for about equal time in the live presentation.
• After each presentation there will be a brief question-and-answer session, which will

allow you to demonstrate that BOTH students in the pair have a solid understanding of the topic, analysis and conclusions.

Aims of the projects

By undertaking these projects, students will

Develop an understanding of a specialised aspect of telecommunications,

Gain experience in using MATLAB and the functions available within the Communications Toolbox, or other analysis tools and techniques

Develop skills in exploring a technical topic without clearly defined objectives.

Develop skills in writing technical reports,

Develop skills in presenting talks on technical topics

Develop skills in collaboration with colleagues to achieve an agreed objective.

The topics are generally designed to take you beyond the range of topics discussed in lectures and practicals, so do not expect to find the answers there. The aim of the project is not to reinforce lecture material, but rather to allow you to explore an additional telecommunications topic, report on and present it.

Organisation

Students will work in pairs. Students can choose their own partners, but they must come

from within the same lab session (since you will be presenting together in that session). Student pairs will be able to select their topic from a list (see the pre-defined projects at the end of this document), or they can propose a topic (within constraints). Once a topic is selected by a student pair, it will not be available to anyone else in that lab class (i.e. each

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

The projects are worth 10% of the total assessment for the unit. This is equal to all the lab

classes combined, so you are expected to put in a commensurate amount of effort.

topic will be covered only once in each lab class). So those who organise themselves fastest will have most choice. Note that any topic proposed by students must be approved by the lecturer in charge. Keep in mind that the project must involve more than just a literature search; there must be experimentation, data collection, analysis and interpretation.

Details about the registration procedure will be advertised on Moodle.

Report

Each pair must write a short report on their topic. This should be written in your own words, without any AI assistance. Any sources (including any copied graphics used for figures) must be properly referenced. Use the IEEE style of referencing – see http://www.lib.monash.edu.au/tutorials/citing/ieee.html. The reports are due, with your PowerPoint presentation pack and Matlab (or other) programmes or scripts, at the end of week 10 (Sunday 14th May). Specific details will be provided on Moodle before then.

The main body of the report should be a maximum of two A4 pages (that is, two SIDES, not two sheets) using 10-point font. The main body must include at least one block diagram describing your topic and at least one graph or diagram illustrating your results.

You may put references on a third page if you wish. You must have at least one reference to a relevant book or paper. (You can also include references to Web sites but at least one reference must be to a published book or paper.)

If you believe that your particular project demands additional diagrams, plots or results that will not fit in the main body, then these, too, may be placed in an appendix. (The main body still has to include at least one diagram and graph or table of results as described earlier, though.) Add such extra material ONLY if it is essential to explain your key results; do not just include lots of plots to try to make it look like you were busy.

Simulation programmes or scripts should be uploaded as separate files. If any programme statement is copied from any source (including the Matlab Help files) these must be clearly labelled with comments which acknowledge the source.

Presentation

The presentations will be run at the scheduled laboratory times. Students must use PowerPoint to prepare their presentations, and must upload the PowerPoint file along with the report when you submit it. It is preferable that you draw your own figures or animations that you use in your talk. The use of figures or animations from other sources is discouraged but, if you choose to use these, the source(s) must be clearly acknowledged.

Each talk will last for five minutes plus approximately two minutes for questions. Both students in each pair must present some of the talk for approximately equal times. Students are also required to attend the talks of other students scheduled for the same session.

Assessment of short projects and expected level of achievements

The projects will be assessed based on a combination of the technical content, your ability to plan and execute an investigation into the topic, your demonstrated understanding and your ability to communicate the work presented as demonstrated in the report, presentation and responses to questions.

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

It will be a struggle to fit what you’d like to say in just two pages, but this is part of the

exercise; it is important to decide the right information to include.

Normally both students in a pair will receive the same mark, unless the standard of presentation of one student is very different from that of the other, or the response to questions indicates a substantial inequality of understanding or contribution to the project. It is important that you choose a partner who you believe will contribute equally to the task. You are generally expected to sort out any difficulties of working together, and only in the most extreme case bring a problem to the attention of a demonstrator or lecturer.

It is impossible to separate the marks for the technical content and for the presentation of the project results. For example, if the report and presentation are presented poorly, it may be difficult to determine the quality of the technical work. Similarly, it is much more difficult to write a clear report and give a talk on work with substantial technical content, than it is to give a talk on superficial matters. As a result, you will get a single mark that represents the overall quality of your work as presented.

Each student will receive a mark and a short, written comment on their project (via Moodle). Due to the number of reports and the workload involved, it will not be possible to provide detailed feedback.

Each of the projects is open-ended. There is no single correct answer. Examples of the type of performance which will earn different marks are given below, but a detailed marking rubric for both the presentation and report will be provided on Moodle.

Level of technical contribution and presentation Mark/10

 Students demonstrate clear understanding of their topic and demonstrate significant initiative in their solution. The programmes are clearly written and documented, with sensible, understandable variable names. The report meets all of the criteria for length, etc. and is clearly written and grammatically correct. The presentation is very clear, the students talk clearly, the slides are well prepared and make good use of diagrams, etc to illustrate the key points. The talk ends on time. The students can answer questions clearly and convincingly, showing a deep understanding of their topic.

10

Students demonstrate a clear understanding of their topic and the work presented meets that specified in the short project description. The report meets all the criteria for length, etc., but may have a few minor errors. The talk is clear and the slides are well prepared and make use of diagrams to illustrate the points. Students can answer the questions asked, but reveal that their understanding of the topic is limited.

7.5

Students demonstrate an understanding of the main points of the topic. The work almost meets the specification. The report or presentation have some limitations. For example, it may be over-length or have poor or confusing explanations. Students can answer simple questions but cannot answer more difficult ones.

5

Students do not understand the topic and present trivial /irrelevant results which do not meet the specification. The talk is clear and the presentation meets the guidelines for length, etc., but does not have adequate technical content.

3

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

3

The superficial nature of the talk and presentation slides, along with the inability of students to answer even quite simple questions on their topic, indicate a last-minute attempt to hide the fact that they have learned nothing and done very little in the project.

0

Note that the mark for this part of the unit will determine 10% of your total assessment for this subject; the same as for all the laboratories combined. You should take this into account when you decide how much effort and time to devote to it. It is our experience that it is very obvious when students decide to leave the project until the last minute and then rush through in a couple of hours trying to come up with something that looks convincing. But it is never convincing.

Hint: A major challenge in presenting what could be a lot of information in very few written words, or very few presentation minutes, is to choose the right information. If we are very proud of the code we have written or the problems we overcame in getting the result, it is natural that we want to tell others about it. But you need to apply a lot of discipline here. In communicating what you’ve done and conclusions you made, you need to accept that your audience is simply not interested in the lines of code you wrote. Rather, it is the telecommunications principle or process that should be the focus: what you were investigating, what you measured, how you interpreted the results and what you learned as a result.

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023
Project Topics

1. Convolutional Coding

Many practical systems use convolutional codes (rather than block codes) for error correction. With convolutional codes, the coder operates on a continuous input sequence rather than on blocks of data. Write programs in MATLAB to demonstrate the operation of a convolutional coder and a convolutional decoder. Demonstrate the performance when you introduce bit errors. Find information about the convolutional code used in some telecommunications equipment (e.g. digital television) and modify your program to implement that code. What variations can you try?

2. Interleaving

Interleaving is a method of spreading out bursts of errors so there is a better chance of correcting them using error correcting codes. In this project, you will use MATLAB to simulate and demonstrate how interleaving can be used to separate errors occurring in transmission before they reach the decoder. Your simulations will demonstrate the trade- offs between interleave depth and delay, and compare the two main categories of interleavers: block and convolutional. Interleavers work in conjunction with error correcting codes; which error correcting code will you choose for your demonstration and why? What error burst statistics will you use?

3. Cache lookup algorithms

Whether ARP (in IPv4 networks) or NDP (in IPv6 networks) are used to obtain the addresses, a host or router stores the IP-MAC address mapping in a local cache. When a packet is to be transmitted to a given IP address, the host searches this table to obtain the corresponding MAC address to be used.

In this project you will investigate alternative lookup algorithms that can be used for such cache lookup operations. You will also choose three algorithms, and write a MATLAB program to compare their performance (you will need to think about the performance criteria as well).

A useful book for the starting point is“Network Algorithmics”by G. Varghese. There is an online version of the book available through the Monash library.

(Note that the focus of this project is the efficiency of search algorithms, and not the use of the address information found.)

4. Image coding

The Discrete Cosine Transform (DCT) is a transform that has been used in image and video coding for many years – it is the basis of JPEG and variants of it are used in all common video coders. In this project, you will use your own or standard test images, segment them (i.e. chop them up) into blocks of 2n x 2n pixels and convert them using the “dct2” transform in Matlab. While doing this, think about why the segmentation is performed; why not just transform the whole image as one big array? Once transformed (that is,“in the DCT domain”), you can then explore the effect of quantising the coefficients in the DCT domain – that is, representing them only approximately, or even zeroing those with small magnitudes. This would save many bits when transmitting the remaining coefficients to a decoder (that would then perform an inverse transform operation on the quantised coefficients it receives), but if you throw away too much information, you will see the effect on the pictures! Can you plot the distortion (measured as sum squared error) against the number of DCT coefficients that you throw away or accuracy of quantisation? What is the

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

significance of the parameter“n”?

5. Motion Compensation in Video coding

When compressing video signals, one of the greatest savings in transmitted bits is achieved by estimating as accurately as possible each new video frame, based on previously transmitted frames. This is done by segmenting each new frame into blocks of 2n x 2n pixels and, for each of these blocks, searching for a set of nearby pixels in a frame that has already been transmitted (most obviously, the previous frame) to find the closest match. A motion vector tells us how to translate that closely-matching image segment to approximate (or predict) the block in the new frame. We then need to send only the difference (the“prediction error”) between our estimate and the actual new frame pixel data (along with the motion vector). This method of coding is called motion compensation (MC).

In this project, you will load a short video sequence into Matlab and then segment each frame into blocks of 2n x 2n pixels. You could then perform MC on one or several frames, and could compare the size of the prediction error signal both with and without MC. (“Without MC”means you use the same pixel locations from the previous frame to estimate those in the current frame; i.e. the motion vector is zero.) You could then compare search strategies (e.g. exhaustive search, logarithmic search) used to find the best match with some nearby part of the previous frame. Your analysis might consider such things as the processing complexity necessary for different search methods, the accuracy of each, the effect of the size (n) of the blocks used for matching, and the number and accuracy of motion vectors generated. (You are not expected to do the coding of the prediction error; your task is to focus on the performance and parameters of the MC. However, the average power in the prediction error is a measure of how effective the MC is.)

6. Psychoacoustic masking in Audio coding

Audio coders such as MP3, Dolby Digital and AAC are all based on a characteristic of the human psychoauditory system called “Psychoacoustic masking”. The existence of large magnitude frequency components in an audio signal means that we cannot hear, or cannot detect distortion in, other nearby frequencies. In this project, you will load a music file into Matlab, break it into time segments, take the FFT (Fast Fourier Transform) to obtain a frequency-domain representation, and explore what happens when you remove or coarsely quantise some of the lower power signal components (particularly if they are at frequencies near to high level components) before reconstructing the audio signal. You are not expected to build a whole psychoacoustic encoder/decoder pair, but you should consider what aspects of this process you can explore, draw conclusions on and present. You could plot the error in the audio (e.g. sum squared error) against the number of coefficients you delete. Are there coefficients you can delete which cause no audible difference? A suitable reference text on this topic is“Digital Audio Coding and Standards”, by Marina Bosi and Richard Goldberg (Springer, 2003), which is available online from the Monash library.

7. Packet queues in a router

Queueing Theory is useful to analyse a vast number of processes involving flows of material items (like components in a factory, people in supermarkets, vehicles on roads,…) or virtual items like data packets as they pass through a network. In particular, a router includes a switch fabric that sends packets towards their destination, but packets may arrive in a bunch, and must sit in a buffer until they can be dealt with; hence the “queue”. In this project, you will investigate the behaviour of queues under various arrival and processing

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

conditions. Using Matlab, you should simulate the arrival of packets arriving at a switch (using a Poisson distributed random number generator to tell you how many packets arrive in each time slot), and also empty that queue using a similar Poisson distributed server process. (Why Poisson?) How does the fullness of the buffer behave (particularly over the long term) as you vary the average arrival and server rates? What is the average delay experienced by a packet passing through this router/queue? How much does the average service rate have to change to (for example) halve the time that a packet spends in the system? Is the behaviour different if the server processes the same number of packets each time slot (i.e. the server rate is fixed instead of random)? You may like to explore other scenarios (such as multiple queues served by a single server, or multiple queues in series – modelling packets passing through multiple routers) in your investigation of queueing, as well as compare your experimental results with theory. (Don’t just make random combinations, though; try to relate your queues to real-world telecommunications scenarios.) You will do your own research to enable you to carry out this project, but a suitable starting point for queueing theory is Chapter 8 of “High Speed Networks and Internets: Performance and Quality of Service”, by William Stallings, Prentice Hall, 2nd Edition 2002 (available in the library).

8. Buffering and delays for compressedvideo

When video data is compressed efficiently, there is a variable data rate generated for each video frame; the encoder will generate E(i) bytes to represent frame i, but we might be using a constant transmission rate that transfers T(i)=T bytes (fixed) each video frame time. A buffer will be needed to allow these two processes to work together. Similarly, at the decoder, E(i) bytes will be needed to reconstruct frame i and this many bytes will be read out of a buffer that is filled at a constant T bytes/frame. In this project, you will use data about bit rates generated for sample video sequences to investigate how much buffering is required in the delivery chain for encoder and decoder, and therefore what unavoidable end-to-end delay is involved (no matter how fast the processors are that are doing the encoding and decoding). By using“frame trace”data (that is, a record of how many bytes are generated for each frame in a compressed video sequence) and recognising that the frames are both generated at the encoder and consumed at the decoder at fixed time intervals, you can simulate the buffers necessary at either end of a transmission link using Matlab or Excel. These buffers will allow for variable rates to be generated/consumed, even though a constant rate might be transmitted over the network connection. If the buffers are ever allowed to empty, your decoder will be fed blank data; to make sure this doesn’t happen, your simulation should allow them to partly fill before you read anything out of them. By how much should they be allowed to fill? How will you decide on the (fixed) bit rate that you simulate between encoder and decoder? How big do the buffers need to be? What delay is involved?

Suitable frame trace data is available on the web (see https://www.cse.wustl.edu/~jain/sam/index.html, or you may find an alternative source you prefer).

9. Phase shift keying (PSK) Modulation

Phase shift keying (PSK) is a digital modulation scheme for carrying information in the phase of a carrier signal. M-PSK modulation techniques have been widely used in WLAN, digital video broadcasting, and cellular communications. M-PSK carries one of M information symbols in each symbol period T, each with a distinct phase, where M=2, 4, …, and has spectral efficiency log! ??? bits/s/Hz. It is particularly suitable for bandwidth limited

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023
and fc represents carrier frequency, ???# denotes energy per &

symbol, and ??? denotes symbol duration.

2-, 4-, 8-PSK lead to the following bit error probability ??? and symbol error probability ??? in

digital communications systems, under the assumption of AWGN channel and Gray mapping.

2PSK error probability:
In Matlab, generate a frame of n=1024 random bits, and convert them into M-ary symbols, where M=2,4,8. Plot time domain 2-, 4- and 8-PSK waveforms for a few symbols to illustrate the PSK signalling and discuss the phase changes, assuming carrier frequency

Plot bit and symbol error probabilities of 2-, 4-, and 8-PSK as a function of )” , respectively,

where (! starts from 0 dB and ends at 10 dB (Note: convert dB to linear representation)”

and substitute this into the above error probability equations).

Discuss your observations about the error probability plots. For example, when M increases, what are the impacts on the bit and symbol error probabilities, and why? For BPSK (M=2), why are bit and symbol error probabilities the same? Compute spectral efficiencies of 2-, 4- and 8-PSK and explain why they are suitable for bandwidth limited systems. Under what circumstances would you choose a large M or a small M ?

A suitable reference for this topic might be the textbook by Bernard Sklar“Digital Communications. Fundamentals and Applications”, Prentice Hall.

10. Equalisation in a communication receiver

Inter symbol interference (ISI) caused by multipath distorts the transmitted signal causing bit errors at the receiver. Traditionally, a time domain equaliser is used to combat distortion induced by the ISI before recovering data bits. In this project, you will equalise a time dispersed (affected by ISI), noisy, digitally modulated signal (eg., BPSK or QPSK)

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

using Matlab!s built-in function objects lineareq (a linear equalizer) and dfe (Decision Feedback Equaliser (DFE) “#an example of a nonlinear equaliser). Consider at least two

signal to noise ratio (SNR) conditions around 10dB to 20dB, and generate scatterplots of digital signals before and after linear equalisation and decision feedback equalisation. What are the advantages and disadvantages of using a DFE over a linear equaliser?

11. CDMA (Code Division Multiple Access)

In CDMA, each message bit is represented by a pseudorandom series of much shorter bits when transmitted, and we rely on the orthogonality of these“spreading codes”to enable us to separate the messages again at the receiver. Write a program which uses a Walsh- Hadamard (WH) code to spread a binary sequence to create a CDMA signal. Demonstrate how a random data stream can be recovered by multiplying the received CDMA sequence with the correct WH code. Show how the orthogonality property of the code ensures that different transmissions can be recovered if power control and synchronisation is correct. You should demonstrate the operation of CDMA in a multi-user scenario, by using orthogonal spreading sequences to decode a required message while rejecting others. While you may wish to illustrate the principle (in your presentation) using short spreading codes, your simulation should use a spreading code that is at least 8 bits long for every input data bit. What is the effect of noise on the combined signal? What would be the effect of imperfect power control or imperfect synchronisation? You should consider not just integer bit shifts in your synchronisation simulation, but also shorter-term fractional bit offsets.

12. OFDM

Orthogonal frequency division multiplexing (OFDM) is a modulation scheme where many streams of data are transmitted in parallel on different orthogonal frequencies. Data sequences Ak and Bk are carried by the in-phase and quadrature components of the complex signal and represented by

Where, ??? denotes the OFDM symbol period in the time domain. For digital television in Australia, N = 8096 and T = 1ms. Ak and Bk for k = 0,1,..N-1 occupy independent sub- carriers and hence do not suffer from self-interference. This orthogonal condition across multiple sub carriers is used in the demodulation of Ak and Bk . To obtain Ak the received time domain waveform is multiplied by the cosine component of the kth subcarrier and is represented by

It can be seen in the above demodulation process that all integrals over the symbol period are zero except for the last term involving cos! . Similarly, demodulation of

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013 This update: Mike Biggar, 1 April 2023

Bk involves multiplication with the sinusoidal component of the kth sub-carrier and integration over the symbol period which is given by
Simulate the OFDM modulation in Matlab and plot the histogram of the amplitudes of the instantaneous signal values. Find information about another communication system using OFDM, adapt your program to use these values of ??? and ??? and repeat the plot. Plot the spectra and measure the Peak-to-Average power ratio of the transmitted signals and see how both of them change with N. Why do you think the peak-to-average power ratio is significant?

13. Bit synchronisation in radio systems

When a radio system commences sending some data (e.g. when a packet of data bits is transmitted over Wi-Fi), the receiver must be synchronised to start interpreting received bits as soon as the message begins. But transmission is asynchronous (there is no continuous transmission in between packets that would maintain synchronisation), so at the start of each message the receiver has to determine a) where the bit boundaries are, and b) when the actual message begins. This is achieved by transmitting a “training sequence” of a known bit pattern before the message payload. The receiver can try to correlate the received signal with the bit pattern it is expecting, to obtain its required timing information.

In this project, you will investigate the design of such training sequences. What are the desirable autocorrelation and cross-correlation features of such sequences? How long should a training sequence be, and what are the trade-offs when you make them longer or shorter? Perform a simulation using Matlab to investigate these things quantitatively. You do not need to modulate a carrier signal with the bit sequence, but you should experiment with what happens if the bit sequence is distorted or noisy. (Hint: One of the popular training sequences is the “Barker” family of bit sequences. This might be a good term to start searching for when you start your research.)

14. Project topic suggested by student and approved by staff

Or propose another topic and have it approved by Mike Biggar (Clayton) or Vineetha

Kalavally (Malaysia). Before suggesting it, make sure it satisfies the following criteria:

• It is not the same (or close to) another project in the list above (which you wanted to do,

but someone else got it first)

• It must involve some experimentation or simulation (e.g. Matlab)
• It must involve data collection and analysis
• You will still need to satisfy the other requirements of references, report length, etc.

ECE3141 Projects 2023 Original document: Jean Armstrong, April 2013